快速排序
快速排序
快速排序由 C. A. R. Hoare 在 1962 年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
核心思想:
- 在待排序的元素任取一个元素作为基准(通常选第一个元素，称为基准元素）
- 将待排序的元素进行分块，比基准元素大的元素移动到基准元素的右侧，比基准元素小的移动到作左侧，从而一趟排序过程，就可以锁定基准元素的最终位置
- 对左右两个分块重复以上步骤直到所有元素都是有序的（递归过程）
复杂度与稳定性
代码实现
Java
public static int partition(int[] arr, int left, int right) {
// 选定左侧的为标杆
int pivotKey = arr[left];
while (left < right) {
// 从右侧开始,寻找到第一个小于标杆的数
while (left < right && arr[right] >= pivotKey)
right--;
// 把小的移动到左边
arr[left] = arr[right];
// 从左侧开始,寻找到第一个大于标杆的数
while (left < right && arr[left] <= pivotKey)
left++;
// 把大的移动到右边
arr[right] = arr[left];
}
// 到这里 left 和 right 必然重合
assert left == right;
// 最后把 pivot 赋值到中间
arr[left] = pivotKey;
return left;
}
// QuickSort.sort(arr);
public static void quickSort(int[] arr, int left, int right) {
// 判断是否只剩下最后一个数了
if (left >= right)
return;
// 如果还有多个数,则先进行划分,划分的结果即是左侧肯定比右侧小
int pivotPos = partition(arr, left, right);
// 对于左侧进行排序
quickSort(arr, left, pivotPos - 1);
// 对于右侧进行排序
quickSort(arr, pivotPos + 1, right);
}