排序算法3｜快速排序（比较、交换类）（附动图）

各类排序方法在时间、空间复杂度及稳定性方面各有优势：

快速排序(Quick Sort)是对冒泡排序的一种改进，基本思想是选取一个值作为枢轴，经过一趟排序，将整段序列分为两个部分，其中一部分的值都小于枢轴，另一部分都大于枢轴。然后继续对这两部分继续进行排序，从而使整个序列达到有序。

实践证明，快速排序是所有排序算法中最高效的一种。它采用了分治(Divide and Conquer)的思想：先保证列表的前半部分都小于后半部分，然后分别对前半部分和后半部分排序，这样整个列表就有序了。这是一种先进的思想，也是它高效的原因。因为在排序算法中，算法的高效与否与列表中数字间的比较次数有直接的关系，而”保证列表的前半部分都小于后半部分”就使得前半部分的任何一个数从此以后都不再跟后半部分的数进行比较了，大大减少了数字间不必要的比较。但查找数据得另当别论了。

它的工作看起来仍然象一个二叉树。首先我们选取一个值作为枢轴，然后把比它小的放在左边，大的放在右边（具体的实现是从两边找，找到一对后交换）。然后对两边分别使用这个过程（最容易的方法——递归）。

如何选择枢轴？可以选择列表第一个元素，也可以选择列表最后一个元素，也可以选择列表的中间值。枢轴选择完成后，如何分组，也有多种方法，如：

左右指针法

I 选取一个枢轴(pivot)作为枢轴，一般取整组记录的第一个数/最后一个，这里采用选取序列最后一个数为枢轴。

II 设置两个变量lo = 0; hi = N – 1;

III 从lo一直向后走，直到找到一个大于key的值，hi从后至前，直至找到一个小于pivot的值，然后交换这两个数。

IV 重复第三步，一直往后找，直到lo和hi相遇，这时将pivot放置在lo的位置即可。

代码：

选取第一个元素做为枢轴的左右指针法：

代码：

挖坑法

选取一个关键字(key)作为枢轴，一般取整组记录的第一个数/最后一个，这里采用选取序列最后一个数为枢轴，也是初始的坑位。

设置两个变量left = 0;right = N – 1;

从left一直向后走，直到找到一个大于key的值，然后将该数放入坑中，坑位变成了array[left]。

right一直向前走，直到找到一个小于key的值，然后将该数放入坑中，坑位变成了array[right]。

重复3和4的步骤，直到left和right相遇，然后将key放入最后一个坑位。

当left >= right时，将key放入最后一个坑，就完成了一次排序。

注意，left走的时候right是不动的，反之亦然。因为left先走，所有最后一个坑肯定在array[right]。

控坑法举例说明：

当前：数组元素为：45 38 65 97 76 13 27 49 20 54；10个数字，前文已经选定了基数为45。

第一步，我们把45单独挖出来，其所在的位置，就形成了一个坑（__符号表示此处是坑，没有萝卜（数字））；挖掉之后的效果如下：注：上面一行是索引值；这里以0为开始索引。

0 1 2 3 4 5 6 7 8 9

__ 38 65 97 76 13 27 49 20 54

第二步，从右侧开始遍历，寻找第一个比基数，就是我们定义的那个基数45小的数字，我们从右向左走，找到的数字是20，这是第一个遇到的比45小的数字，接着，将其挖掉，则原地就留下了另一个坑，这时候，效果如下：

0 1 2 3 4 5 6 7 8 9

__ 38 65 97 76 13 27 49 __ 54 :注意，目前图中有了两个深坑。

第三步，把拿出来的20放入到原先45所在的位置，实质就是从右侧找到第一个小于基数的数字，与基数交换，这一步执行后的结果如下：

0 1 2 3 4 5 6 7 8 9

20 38 65 97 76 13 27 49 __ 54 ：注意，目前45，也就是基数，还未放入坑。

第四步，从左侧开始遍历，寻找第一个比基数45更大的数，找到的数字是65，然后把该数字放入右边空着的坑里；执行结果如下：

0 1 2 3 4 5 6 7 8 9

20 38 __ 97 76 13 27 49 65 54 ：注意，这时候65的位置留下了一个坑；这时候，45依旧保持悬空状态，没有放坑里；此时左侧索引到达的位置为2；即原先65所在的位置

第五步，再次从右侧开始遍历，注意：这时候要以第二步骤为基础，因为第二步已经遍历到了倒数第二个位置；此次要在此基础上，继续往左走：然后找到了数字27；把该数字拿出来，放入第四步的坑里：执行结果如下：

0 1 2 3 4 5 6 7 8 9

20 38 27 97 76 13 __ 49 65 54 :注意，此次操作是在前面操作的基础之上的，逻辑跟第二步是一样的，但是在第二步基础上后续操作；此时，右侧索引到达的位置为6，即原先27所在的位置。

第六步：第二次右侧遍历操作结束，现在开始第二次左侧遍历操作，按照第四步的逻辑，找到了数字97；这里，也是在第四步操作基础上执行的，把97挖出来，然后放在第五步形成的坑里；执行结果如下：

0 1 2 3 4 5 6 7 8 9

20 38 27 __ 76 13 97 49 65 54 ：注意，这时候左侧索引所在的位置为3

第七步：第三次右侧遍历，记住，每次遍历的操作都是从右边找小于基数的元素，从左边找大于基数的元素，而且操作都是在原先遍历操作后的位置继续操作的；然后找到了13，放到第六步形成的坑里：执行结果如下：

0 1 2 3 4 5 6 7 8 9

20 38 27 13 76 __ 97 49 65 54 :注意，这时候右侧遍历到了索引为5；左侧遍历到的位置为3，两个索引还未曾相遇，所以可以继续遍历，如果索引相遇，则代表左边全部是小于45的数字，右边全部是大于45的数字，则遍历停止了

第八步：第三次左侧遍历，发现了大于45的数字，76，这时候，左侧索引为4，还未曾碰到右边的索引，所以可以继续进行，把76挖出来，放在第七步的坑里：执行结果如下：

0 1 2 3 4 5 6 7 8 9

20 38 27 13 __ 76 97 49 65 54 :注意，这时候左侧索引为4；而右侧索引为5

第九步：程序继续执行，开始第四次右侧遍历，结果，右侧索引为4，左侧索引同样为4，二者相遇了，代表这一次执行结束，而此时，数组中仍然有一个坑，这个坑，就放入我们选定的基数：45。

到此，第一趟排序完成。

快速排序，没有想象中的那么难，这第一趟排序，轻轻松松就完成了，接下来，要总结下这趟排序的要点，因为我们还要把这部分逻辑递归调用，提高快速排序的效率：

快速排序的实质：首先挖坑，然后遍历填坑；我们先取出一个基数，无论这个基数的位置在哪儿，拿出来之后就形成一个坑；然后遍历从右侧开始，寻找比基数更小的数，挖出来（留出一个坑），填到原先的坑里；然后从左侧寻找比基数大的数，填到上一步的坑里；这就是主体逻辑

仔细想一下第一步达到的结果，那就是最后整个数列以基数为标准，划分成了两部分？是不是呢，仔细想一下，右边小于基数的数字，现在都放到了左边；而左边大于基数的数字，都被放到了右边，达成了我们想要的效果。

执行的过程中，必须注意左右的索引是否相遇了，只有左右索引未曾相遇，才能继续执行；相遇了，一次循环就终止了。

好，现在，最复杂的一趟讲完了，然后呢？

前文说了，整个队列已经划分为两个部分了，然后，就是针对这两部分，再度调用快速排序算法，如此反复，很快，整个算法就执行完毕，而整个数列，也就变成完全有序的了。

写出代码：

前后指针法

定义变量cur指向序列的开头，定义变量pre指向cur的前一个位置。

当array[cur] < key时，cur和pre同时往后走，如果array[cur]>key，cur往后走，pre留在大于key的数值前一个位置。

当array[cur]再次 < key时，交换array[cur]和array[pre]。

通俗一点就是，在没找到大于key值前，pre永远紧跟cur，遇到大的两者之间才会拉开差距，中间差的肯定是连续的大于key的值，当再次遇到小于key的值时，交换两个下标对应的值就好了。

带着这种思想，看着图示应该就能理解了。

下面是实现代码：

可以递归实现：

也可以非递归实现：

递归的算法主要是在划分子区间，如果要非递归实现快排，只要使用一个栈来保存区间就可以了。 一般将递归程序改成非递归首先想到的就是使用栈，因为递归本身就是一个压栈的过程。

快速排序的特点：

分类：内部比较排序

数据结构：数组

最差时间复杂度：每次选取的基准都是最大（或最小）的元素，导致每次只划分出了一个分区，需要进行n1次划分才能结束递归，时间复杂度为O(n^2)

最优时间复杂度：每次选取的基准都是中位数，这样每次都均匀的划分出两个分区，只需要logn次划分就能结束递归，时间复杂度为O(nlogn)

平均时间复杂度：O(nlogn)

所需辅助空间：主要是递归造成的栈空间的使用(用来保存left和right等局部变量)，取决于递归树的深度，一般为O(logn)，最差为O(n)：：：

稳定性：不稳定

代码：

附代码：

#include <stdio.h> #include <stdlib.h> // 分类 ------------ 内部比较排序 // 数据结构 --------- 数组 // 最差时间复杂度 ---- 每次选取的基准都是最大（或最小）的元素，导致每次只划分出了一个分区，需要进行n-1次划分才能结束递归，时间复杂度为O(n^2) // 最优时间复杂度 ---- 每次选取的基准都是中位数，这样每次都均匀的划分出两个分区，只需要logn次划分就能结束递归，时间复杂度为O(nlogn) // 平均时间复杂度 ---- O(nlogn) // 所需辅助空间 ------ 主要是递归造成的栈空间的使用(用来保存left和right等局部变量)，取决于递归树的深度，一般为O(logn)，最差为O(n) // 稳定性 ---------- 不稳定 void Swap(int A[], int i, int j) { int temp = A[i]; A[i] = A[j]; A[j] = temp; } int Partition(int A[], int left, int right) // 划分函数 { int pivot = A[right]; // 这里每次都选择最后一个元素作为基准 int tail = left - 1; // tail为小于基准的子数组最后一个元素的索引 for (int i = left; i < right; i++) // 遍历基准以外的其他元素 { if (A[i] <= pivot) // 把小于等于基准的元素放到前一个子数组末尾 { Swap(A, ++tail, i); } } Swap(A, tail + 1, right); // 最后把基准放到前一个子数组的后边，剩下的子数组既是大于基准的子数组 // 该操作很有可能把后面元素的稳定性打乱，所以快速排序是不稳定的排序算法 return tail + 1; // 返回基准的索引 } void QuickSort(int A[], int left, int right) { if (left >= right) return; int pivot_index = Partition(A, left, right); // 基准的索引 QuickSort(A, left, pivot_index - 1); QuickSort(A, pivot_index + 1, right); } int main() { int A[] = { 5, 2, 9, 4, 7, 6, 1, 3, 8 }; // 从小到大快速排序 int n = sizeof(A) / sizeof(int); QuickSort(A, 0, n - 1); printf("快速排序结果："); for (int i = 0; i < n; i++) { printf("%d ", A[i]); } printf("\n"); system("pause"); return 0; } 

－End－