快速排序及STL中的sort算法

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

快速排序基本思想是，对待排序序列进行划分（Partition），一次划分，选择一个元素作为枢轴，然后将所有比枢轴小的元素放到枢轴的左边，将比枢轴大的元素放到枢轴的右边。然后对该枢轴划分的左右子序列分别再进行划分，如此递归。Partition是一个非常重要的概念，因为它只需要O（n）的时间复杂度就可以将待排序序列划分为两块具有大小关系的区间，可以根据这一特性求解待排序序列中最大的k个数、第k大的数等类似问题。

快速排序算法复杂度O(nlogn).

就平均时间而言，快速排序是目前被认为是最好的一种内部排序方法，其平均时间是O(nlogn)，最坏情况是O(n^2)，最坏的情况就是如下倒序完后再正序排的情况。

C++代码如下：

#include "stdafx.h"#define MAXSIZE 20typedef struct{
int r[MAXSIZE+];
int len;
}SqList;int Partition(SqList &L, int low, int high)
{
L.r[] = L.r[low]; // 以第一个元素作为枢轴
int pivotkey = L.r[low];// 记录枢轴关键字
while (low < high)
{
while(low<high && L.r[high]>=pivotkey)
--high;// 找到从high位置开始向前第一个比枢轴小的元素
L.r[low] = L.r[high];// 将找到的比枢轴小的元素放到前边的空闲位置
while(low<high && L.r[low]<=pivotkey)
++low;// 找到从low位置开始向后第一个比枢轴大的元素
L.r[high] = L.r[low];// 将找到的比枢轴大的元素放到后边的空闲位置
}
L.r[low] = L.r[];// 将枢轴放回中间的空闲位置，由while{}循环可知，low最后空闲 return low;
}void QSort(SqList &L, int low, int high)
{
if (low < high)
{
int pivotloc = Partition(L, low, high);
QSort(L, low, pivotloc-);
QSort(L, pivotloc+, high);
}
}int _tmain(int argc, _TCHAR* argv[])
{
SqList sqList;
for (int i=; i<MAXSIZE+; i++)
{
sqList.r[i] = MAXSIZE - i;
}
sqList.len = MAXSIZE; QSort(sqList, , sqList.len); return ;
}

// 附一次划分过程，第一行为index，第二行为待排序序列
// 0 1 2 3 4 5 6 7
// __ 49 38 65 97 76 13 27 // 开始时，0号位空闲(low:1, high:7)
// 49 __ 38 65 97 76 13 27 // 将第1号元素作为枢轴，放到0号位，1号位冗余(low:1, high:7)
// 49 27 38 65 97 76 13 __ // 发现27比49小，将7号位值放到1号位，7号位冗余(low:1, high:7)
// 49 27 38 __ 97 76 13 65 // 发现65比49大，将3号位值放到7号位，3号位冗余(low:3, high:7)
// 49 27 38 13 97 76 __ 65 // 发现13比49小，将6号位值放到3号位，6号位冗余(low:3, high:6)
// 49 27 38 13 __ 76 97 65 // 发现97比49大，将4号位值放到6号位，4号位冗余(low:4, high:5)
// __ 27 38 13 49 76 97 65 // low == high，将枢轴放到4号位，此时49左边的都比49小，右边的都比49大

STL的所有关系型容器都拥有自动排序的功能（底层采用RB-tree），所以不需要sort算法。序列式容器的中的stack、queue等都有特别的出入口，不允许用户对元素进行排序。剩下的vector、deque和list，前两者的迭代器属于RandomAccessIterators，适合sort算法。泛型算法一定要求迭代器是RandomAccessIterators。因为任何一个元素都可以被选作枢轴（pivot），但是其合适与否却会影响Quick Sort的效率。为了避免枢轴不够随机带来的恶化效应，最理想的方式是取整个序列的头、尾、中央三个位置的元素，以其中值作为枢轴，这种做法成为三点中值（Median-of-Three），为了能够快速取出中央位置的元素，显然迭代器必须能够随机定位，因此快速排序的泛型算法中迭代器必须是RandomAccessIterators。

STL的sort算法，数据量大时采用Quick Sort，分段递归排序。一旦分段后的数据量小于某个门槛，为避免Quick Sort的递归调用带来过大的额外负担，就改用Insertion Sort。Insertion Sort虽然时间复杂度是O（n^2），但是当数据量很小时，却有不错的效果。另外虽然STL有三点中值来防止枢轴选取不当的问题，还有introsort进行自我侦测，如果分割行为有恶化倾向时，会转而改用Heap Sort。