基本思想
时间复杂度: $logN^N$ 或者 $N*logN$
采用分治的方法
- 从数组中找出一个数作为基数
- 将大于这个基数的数放在右边，小于基数的数放在左边
- 重复上述步骤，直到各区间只有一个数
采用挖坑填数的思想
- i=L，j=R；讲基数挖出形成第一个坑a[i]
- j--后向前找比他小的数，找到后将此数填到a[i]中
- i++从前往后找比基数大的，找到后将此数填到a[j]中
- 重复上述步骤，直到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个代码
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);
}
}
