내 연락처 정보
우편메소피아@프로톤메일.com
2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
서문: 이 글에서는 퀵 정렬 알고리즘의 초기 학습에 대한 몇 가지 의구심에 대한 자세한 답변을 제공하고 기본 퀵 정렬 알고리즘의 최적화된 버전을 제공합니다.
퀵 정렬 알고리즘의 핵심은分治思想,분할 정복 전략은 다음 세 단계로 구분됩니다.
빠른 정렬 알고리즘에 적용됩니다.
퀵 정렬의 키 코드는 다음과 같습니다.如何根据基准元素划分数组区间(parttion), 분해 방법은 여러 가지가 있지만 여기서는 한 가지 방법만 제공됩니다.挖坑法
암호:
class Solution {
public int[] sortArray(int[] nums) {
quick(nums, 0, nums.length - 1);
return nums;
}
private void quick(int[] arr, int start, int end) {
if(start >= end) return;// 递归结束条件
int pivot = parttion(arr, start, end);
// 递归解决子问题
quick(arr, start, pivot - 1);
quick(arr, pivot + 1, end);
}
// 挖坑法进行分解
private int parttion(int[] arr, int left, int right) {
int key = arr[left];
while(left < right) {
while(left < right && arr[right] >= key) right--;
arr[left] = arr[right];
while(left < right && arr[left] <= key) ++left;
arr[right] = arr[left];
}
arr[left] = key;
return left;
}
}
자세한 답변:
1.왜start>=end재귀의 종료조건인가요?
하위 문제를 연속적으로 분해합니다. 즉, 요소가 하나만 있으면 시작 포인터와 끝 포인터가 동시에 요소를 가리킬 필요가 없습니다. 시간.
2. 왜 왼쪽 대신 오른쪽이 먼저 가야 합니까?
누가 먼저 가느냐에 따라 다르죠
基准元素的位置,위 코드에서는 기본 요소(키)가 먼저 이동하면 가장 왼쪽 요소입니다.left, 왼쪽은 먼저 기본 요소보다 큰 요소를 만난 다음 실행합니다.arr[right] = arr[left],저장하지 않아서arr[right], 이 요소는 손실됩니다
오른쪽으로 먼저 가면 오른쪽은 기본 요소보다 작은 요소를 먼저 만난 후 실행됩니다.arr[left]=arr[right], 이때 왼쪽은 움직이지 않았기 때문에 여전히 피벗이지만 키를 사용하여 피벗을 저장했습니다.
3.왜 arr[right]>=key인가요?>안되나요?
크거나 같음은 주로 처리용입니다.
重复元素问题
예를 들어 배열이 있습니다.[6,6,6,6,6]>이면 오른쪽 포인터도 움직이지 않고, 왼쪽 포인터도 움직이지 않아 무한 루프에 빠지게 됩니다.
4. 왜 구덩이파기 공법이라 불리는가?
r 포인터가 첫 번째 포인터를 만났을 때
arr[r] = arr[l], 이때 l 위치는 비어 있어 피트(pit)를 형성한다.
두 가지 주요 최적화 방향이 있습니다.
O(N*logN)즉, 최고의 시간 복잡도数组分三块동시에 특별한 테스트 사례(순차 배열 또는 역배열)가 발생하면 시간 복잡도가O(N^2)먼저, 질문을 바탕으로 (색상별로 정렬) 무엇인지 이해数组分三块
분석하다
암호:
class Solution {
public void sortColors(int[] nums) {
// 分治 --
// 1.定义三指针
int i = 0;// 遍历整个数组
int l = -1, r = nums.length;
while(i < r) {
if(nums[i] == 0) swap(nums,++l,i++);
else if(nums[i] == 1) i++;
else swap(nums,--r,i);
}
return;
}
private void swap(int[] nums,int x,int y) {
int tmp = nums[x]; nums[x] = nums[y]; nums[y] = tmp;
}
}
l,r的起始位置, 첫 번째 요소와 마지막 요소는 다음에 속합니다.未处理状态, 따라서 `l, r은 이 두 요소를 가리킬 수 없으며 간격 외부에 있어야 합니다.三个指针去分别维护四个区间, 간격 중 하나는 다음과 같습니다.未处理区间, 현재 포인터가 계속 이동함에 따라 모든 간격이 처리되고 최종적으로 3개의 간격만 남게 됩니다.위의 아이디어를 적용해 보세요.快速排序的parttion中, 최종 결과는 세 개의 간격으로 나뉩니다.
암호:
class Solution {
// 快速排序优化版
// 分解--解决--合并
public int[] sortArray(int[] nums) {
qsort(nums, 0, nums.length - 1);
return nums;
}
private void qsort(int[] nums, int start, int end) {
if(start >= end) return;// 递归结束条件
// 分解
int pivot = nums[start];
int l = start - 1, r = end + 1, i = start;
while(i < r) {
int cur = nums[i];
if(cur < pivot) swap(nums, ++l, i++);
else if(cur == pivot) ++i;
else swap(nums, --r, i);
}
// [start, l] [l+1, r-1] [r, end]
// 递归解决
qsort(nums, start, l);
qsort(nums, r, end);
}
private void swap(int[] nums,int i, int j) {
int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp;
}
}
2. 기준값을 무작위로 선택
무작위 숫자를 사용하여 기준 값을 무작위로 선택
int pivot = nums[start + new Random().nextInt(end - start + 1)];
// 起始位置 随机产生的偏移量
개선된 코드 완성:
class Solution {
// 快速排序优化版
// 分解--解决--合并
public int[] sortArray(int[] nums) {
qsort(nums, 0, nums.length - 1);
return nums;
}
private void qsort(int[] nums, int start, int end) {
if(start >= end) return;// 递归结束条件
// 分解
int pivot = nums[start + new Random().nextInt(end - start + 1)];
int l = start - 1, r = end + 1, i = start;
while(i < r) {
int cur = nums[i];
if(cur < pivot) swap(nums, ++l, i++);
else if(cur == pivot) ++i;
else swap(nums, --r, i);
}
// [start, l] [l+1, r-1] [r, end]
// 递归解决
qsort(nums, start, l);
qsort(nums, r, end);
}
private void swap(int[] nums,int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
빠른 선택 알고리즘은 다음과 같습니다.基于快速排序优化版本시간 복잡도는O(N)선택 알고리즘, 사용 시나리오는 다음과 같습니다.第K大/前K大같은 선택 문제
01.배열에서 K번째로 큰 요소
링크: https://leetcode.cn/problems/kth-largest-element-in-an-array/
분석하다
sort정렬한 다음 K번째로 큰 것으로 반환O(N*logN)O(logN)재귀로 생성된 스택 호출다음으로 빠른 선택 알고리즘을 사용하여 구현합니다.O(N)시간복잡도
암호:
class Solution {
public int findKthLargest(int[] nums, int k) {
return qsort(nums, 0, nums.length - 1, k);
}
private int qsort(int[] nums, int start, int end, int k) {
if(start >= end) return nums[start];
int pivot = nums[start + new Random().nextInt(end - start + 1)];
// 数组分三块 <pivot ==pivot >pivot
int l = start - 1, r = end + 1, i = start;
while(i < r) {
if(nums[i] < pivot) swap(nums, ++l, i++);
else if(nums[i] == pivot) ++i;
else swap(nums, --r, i);
}
// [start, l] [l+1, r - 1] [r, end]
int c = end - r + 1, b = r - 1 - (l + 1) + 1, a = l - start + 1;
// 分情况讨论 进行选择
if(c >= k) return qsort(nums, r, end, k);
else if(b + c >= k) return pivot;
else return qsort(nums, start, l, k - b - c);// 找较小区间的第(k-b-c)大
}
private void swap(int[] arr, int i, int j) {
int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
}
}
O(N)
그는 30년 이상 기술 연구에 전념해 왔으며, java, linux, javascript, php, css 등 다양한 언어에 능숙하며, 오픈 소스 분야에서 많은 공헌을 했습니다. 나중에 참조할 수 있도록 기술 개발의 일부 문제를 공유하는 개발자 문서 스테이션입니다.
우편메소피아@프로톤메일.com