快速排序用到了分治思想，同样的还有归并排序。乍看起来快速排序和归并排序非常相似，都是将问题变小，先排序子串，最后合并。不同的是快速排序在划分子问题的时候经过多一步处理，将划分的两组数据划分为一大一小，这样在最后合并的时候就不必像归并排序那样再进行比较。但也正因为如此，划分的不定性使得快速排序的时间复杂度并不稳定。
快速排序的基本思想：通过一趟排序将待排序列分隔成独立的两部分，其中一部分记录的元素均比另一部分的元素小，则可分别对这两部分子序列继续进行排序，以达到整个序列有序。
算法步骤
快速排序使用 分治法（Divide and conquer）策略来把一个序列分为较小和较大的 2 个子序列，然后递归地排序两个子序列。具体算法描述如下：
- 从序列中随机挑出一个元素，做为 “基准”(
pivot)：选择不同位置的中心元素，快速排序就有不同的变体，比如可以选择：第一个元素、最后一个元素以及左端、右端和中心位置上的三个元素的中值作为中心元素 - 重新排列序列，将所有比基准值小的元素摆放在基准前面，所有比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个操作结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
- 递归地把小于基准值元素的子序列和大于基准值元素的子序列进行快速排序。
图解算法
代码实现
public static int partition(int[] array, int low, int high) {
// 取最后一个元素作为中心元素
int pivot = array[high];
// 定义指向比中心元素大的指针，首先指向第一个元素
int pointer = low;
// 遍历数组中的所有元素，将比中心元素大的放在右边，比中心元素小的放在左边
for (int i = low; i < high; i++) {
if (array[i] <= pivot) {
// 将比中心元素小的元素和指针指向的元素交换位置
// 如果第一个元素比中心元素小，这里就是自己和自己交换位置，指针和索引都向下一位移动
// 如果元素比中心元素大，索引向下移动，指针指向这个较大的元素，直到找到比中心元素小的元素，并交换位置，指针向下移动
swap(array, i, pointer);
pointer++;
}
//每次打印排序后结果
System.out.println(Arrays.toString(array));
}
// 将中心元素和指针指向的元素交换位置
swap(array, pointer, high);
return pointer;
}
public static void quickSort(int[] array, int low, int high) {
if (low < high) {
// 获取划分子数组的位置
int position = partition(array, low, high);
// 左子数组递归调用
quickSort(array, low, position - 1);
// 右子数组递归调用
quickSort(array, position + 1, high);
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 洗牌算法，将输入的数组随机打乱
private static void shuffle(int[] nums) {
Random rand = new Random();
int n = nums.length;
for (int i = 0 ; i < n; i++) {
// 生成 [i, n - 1] 的随机数
int r = i + rand.nextInt(n - i);
swap(nums, i, r);
}
}算法分析
- 稳定性：不稳定
- 时间复杂度：最佳：$O(nlogn)$， 最差：$O(n^2)$，平均：$O(nlogn)$
- 空间复杂度：$O(logn)$
由于可能在数组已经有序或基本有序的情况下，最差的时间复杂度。为了避免最坏情况发生，可以通过随机选择基准元素或者使用三数取中法等策略来提高快速排序的性能；或者可以先使用洗牌算法，将数据打乱。