【每周一算】十大经典排序算法之快速排序
排序的时间复杂度
| 算法名称 | 平均时间复杂度 | 空间复杂度 | 稳定性 |
| 快速排序 | O(nlogn) | O(logn) | 不稳定 |
快速排序过程
1. 从数列中挑出一个元素，称为 “基准”（pivot）;2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；
代码实现
public class QuickSortTest01 {
public static void quicksort(int[] arr, int left, int right) {
if (left >= right) {
return;
}
int flag = left;
int start = left;
int end = right;
while (left < right) {
while ((left < right) && (arr[right] >= arr[flag])) {
right--;
}
if (arr[right] < arr[flag]) {
int tmp = arr[right];
arr[right] = arr[flag];
arr[flag] = tmp;
flag = right;
}
while ((left < right) && (arr[left] <= arr[left])) {
left++;
}
if (arr[left] > arr[flag]) {
int tmp = arr[left];
arr[left] = arr[flag];
arr[flag] = tmp;
flag = left;
}
}
quicksort(arr, start, flag - 1);
quicksort(arr, flag + 1, end);
}
/**
* 占位法
*
* @param arr
* @param left
* @param right
*/
public static void quick_sort(int[] arr, int left, int right) {
if (left < right) {
//Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 参见注1
int i = left, j = right, x = arr[left];
while (i < j) {
while (i < j && arr[j] >= x) // 从右向左找第一个小于x的数
j--;
if (i < j) {
arr[i++] = arr[j];
}
while (i < j && arr[i] < x) // 从左向右找第一个大于等于x的数
i++;
if (i < j) {
arr[j--] = arr[i];
}
}
arr[i] = x;
quick_sort(arr, left, i - 1); // 递归调用
quick_sort(arr, i + 1, right);
}
}
public static void main(String[] args) {
int[] arr = new int[] {23, 100, 10, 5, 2, 200};
quick_sort(arr, 0, arr.length - 1);
System.out.println(arr);
}
}