基本思想
時(shí)間復(fù)雜度: $logN^N$ 或者 $N*logN$
采用分治的方法
- 從數(shù)組中找出一個(gè)數(shù)作為基數(shù)
- 將大于這個(gè)基數(shù)的數(shù)放在右邊哥谷，小于基數(shù)的數(shù)放在左邊
- 重復(fù)上述步驟，直到各區(qū)間只有一個(gè)數(shù)
采用挖坑填數(shù)的思想
- i=L，j=R屉佳；講基數(shù)挖出形成第一個(gè)坑a[i]
- j--后向前找比他小的數(shù)谷朝，找到后將此數(shù)填到a[i]中
- i++從前往后找比基數(shù)大的，找到后將此數(shù)填到a[j]中
- 重復(fù)上述步驟忘古，直到i==j
核心代碼
挖坑法
public int AdJust(int arr[],int l,int r){
int i = l,j=r;
int standard = arr[l];
while (i<j) {
while (i < j && arr[j] > standard)
j--;
if (i < j) {
arr[i] = arr[j];
i++;
}
while (i < j && arr[i] < standard)
i++;
if (i < j) {
arr[j] = arr[i];
j--;
}
}
arr[i] = standard;
return i;
};
再采用分治法
void quickSort(int arr[],int l,int r){
if (l<r){
int x = AdJust(arr,l,r);
quickSort(arr,l,x-1);//中間的不用再排序
quickSort(arr,x+1,r);
}
}
整合上面2個(gè)代碼
void QuickSort(int arr[], int l, int r) {
if (l < r) {
int i = l, j = r;
int standard = arr[l];
while (arr[j] >= standard && i < j) {
j--;
}
if (i < j) {
arr[i++] = arr[j];
}
while (arr[i] < standard && i < j) {
i++;
}
if (i < j) {
arr[j--] = arr[i];
}
arr[i] = standard;
QuickSort(arr, l, i - 1);
QuickSort(arr, i + 1, r);
}
}
