八种常用交换排序算法之快速排序

交换排序
所谓交换，就是序列中任意两个元素进行比较，根据比较结果来交换各自在序列中的位置，以此达到排序的目的。
快速排序
快速排序的思想很简单，就是先把待排序的数组拆成左右两个区间，左边都比中间的基准数小，右边都比基准数大。接着左右两边各自再做同样的操作，完成后再拆分再继续，一直到各区间只有一个数为止。
举个例子，现在我要排序 4、9、5、1、2、6 这个数组。一般取首位的 4 为基准数，第一次排序的结果是：
2、1、4、5、9、6
可能有人觉得奇怪，2 和 1 交换下位置也能满足条件，为什么 2 在首位？这其实由实际的代码实现来决定，并不影响之后的操作。
以 4 为分界点，对 2、1、4 和 5、9、6 各自排序，得到
1、2、4、5、9、6
不用管左边的 1、2、4 了，将 5、9、6 拆成 5 和 9、6，再排序，至此结果为
1、2、4、5、6、9
为什么把快排划到交换排序的范畴呢？因为元素的移动也是靠交换位置来实现的。
算法实现
大体思路已经有了，接下来就是具体实现。
相信大家已经看出来了，算法的实现需要用到递归（拆分区间之后再对每个区间作同样的操作）。所有关于算法实现的阐述仅以一次排序为例。
基准数一般取数组首位的数，而最终基准数是要放在中间位置的。我们使用一个临时变量 stard 来保存选取的基准值，其余元素根据比较结果决定是否交换位置。
我们分别得到数组的首元素和尾元素的下标，作为头指针和尾指针。先尾指针开始，如果对应的数比基准值大，尾指针向前移动，直到遇到比基准值小的为止。此时将尾指针和头指针对应的数值进行交换。轮到头指针，如果对应的数比基准值小，头指针向后移动，直到遇到比基准值大的为止。此时将尾指针和头指针对应的数值进行交换。再到尾指针，再到头指针，直到头尾指针重合为止。此时将 stard 的值赋给指针重合处下标，一趟排序完成。
用 Java 实现的快速排序如下
/**
* 快速排序
*
* @param arr 待排序的整型数组
* @param start 起始下标
* @param end 末尾下标
*/
public static void quicksort(int[] arr, int start, int end) {
if (start < end) {
// 把数组中第 0 个数字作为基准数
int stard = arr[start];
// 记录需要排序的下标
int low = start;
int high = end;
// 循环找到比基准数大的数和比基准数小的数
while (low < high) {
// 右边的数字比基准数大
while (low < high && arr[high] >= stard) {
high--;
}
// 使用右边的数替换左边的数
arr[low] = arr[high];
// 左边的数字比基准数小
while (low < high && arr[low] <= stard) {
low++;
}
// 使用左边的数替换右边的数
arr[high] = arr[low];
}
// 把标准值赋给下标重合的位置
arr[low] = stard;
// 处理所有小的数字
quicksort(arr, start, low);
// 处理所有大的数字
quicksort(arr, low + 1, end);
}
}
我还在网上看到另一种实现方式，个人觉得第二种虽然更符合交换这一概念，但在交换次数和空间消耗上有一丢丢逊色。
/**
* 快速排序
*
* @param arr 待排序的整型数组
* @param start 起始下标
* @param end 末尾下标
*/
public static void quicksort(int[] arr, int start, int end) {
if (start < end) {
// 把数组中第 0 个数字作为基准数
int stard = arr[start];
// 记录需要排序的下标
int low = start;
int high = end;
// 循环找到比基准数大的数和比基准数小的数
while (low < high) {
// 右边的数字比基准数大
while (low < high && arr[high] >= stard) {
high--;
}
// 左边的数字比基准数小
while (low < high && arr[low] <= stard) {
low++;
}
// 相等继续循环
if (low < high && arr[low] == arr[high]) {
low++;
} else {
// 左边的数和右边的数交换位置
int temp = arr[low];
arr[low] = arr[high];
arr[high] = temp;
}
}
// 处理所有小的数字
quicksort(arr, start, low);
// 处理所有大的数字
quicksort(arr, low + 1, end);
}
}
快速排序稳定性
快速排序是不稳定的算法，只要举出一个实例，即可说明它的不稳定性。所谓不稳定，即序列中如果存在多个相同的元素，经过排序后它们的顺序位置发生变化，就是不稳定的。
假设在数列中存在 a[i]=a[j]，若在排序之前，a[i]在a[j]前面，并且排序之后，a[i] 仍然在 a[j] 前面，则这个排序算法是稳定的。
快速排序性能
快速排序的一次划分算法从两头交替搜索，直到 low 和 high 重合，因此其时间复杂度是 O(n)。这里要注意时间复杂度的定义，常数是忽略不计的，可能第二次划分只有原长度的一半，即 (1/2)*n，但还是认为是 O(n)。
整个快速排序算法的时间复杂度与划分的趟数有关。理想的情况是，每次划分所选择的中间数恰好将当前序列几乎等分。第一次划分变成两个数组，第二次划分变成四个数组，最后一定会变成 n 个数组，划分次数即是 log2n 次，便可得到长度为1的子表。这样，整个算法的最优时间复杂度为 O(nlog2n)。
最坏的情况是，每次所选的中间数是当前序列中的最大或最小元素，这使得每次划分所得的子表中一个为空表，另一子表的长度为原表的长度减一。这样，长度为 n 的数据表的快速排序需要经过 n 趟划分，使得整个排序算法的时间复杂度为 O(n2)。
快速排序的平均时间复杂度也是 O(nlogn)。
从空间性能上看，尽管快速排序需要的辅助空间也就是个常数级 O(1) ，但用到了递归，每一次划分都需要开辟一块辅助空间。
因此最优的情况下空间复杂度为 O(log2n) ，最差的情况下空间复杂度为 O( n ) 。