快速排序(Quick Sort)详解代码、例程

概述

快速排序(Quick Sort)是一种有效的排序算法。虽然算法在最坏的情况下运行时间为O(n^2)，但由于平均运行时间为O(nlogn)，并且在内存使用、程序实现复杂性上表现优秀，尤其是对快速排序算法进行随机化的可能，使得快速排序在一般情况下是最实用的排序方法之一。
快速排序被认为是当前最优秀的内部排序方法。
实现

快速排序的实现基于分治法，具体分为三个步骤。假设待排序的序列为L[m..n]。
分解：序列L[m .. n]被划分成两个可能为空的子序列L[m .. pivot-1]和L[pivot+1 .. n]，使L[m .. pivot-1]的每个元素均小于或等于L[pivot]，同时L[pivot+1.. n]的每个元素均大于L[pivot]。其中L[pivot]称为这一趟分割中的主元（也称为枢轴、支点）。
解决：通过递归调用快速排序，对子序列L[m .. pivot-1]和L[pivot+1 .. r]排序。
合并：由于两个子序列是就地排序的，所以对它们的合并不需要操作，整个序列L[m .. n]已排好序。
性质

内部排序
快速排序是一种内部排序方法。也就是说快速排序的排序对象是读入内存的数据。
比较排序
快速排序确定元素位置的方法基于元素之间关键字大小的比较。
所有基于比较方法的排序方法的时间下界不会低于O(nlgn)。这个结论的具体证明，请参考有关算法的书籍，例如《算法导论》第8章。
快速排序在理想情况下，能严格地达到O(nlgn)的下界。一般情况下，快速排序与随机化快速排序的平均情况性能都达到了O(nlgn)。
不稳定性
快速排序是一种不稳定的排序方法。简单地说，元素a1, a2的关键字有a1.key=a2.key，则不稳定的排序方法不能保证a1, a2在排序后维持原来的位置先后关系。
原地排序
在排序的具体操作过程中，除去程序运行实现的空间消费（例如递归栈），快速排序算法只需消耗确定数量的空间（即S(1)，常数级空间）。
这个性质的意义，在于在内存空间受到限制的系统（例如MCU）中，快速排序也能够很好地工作。
时空复杂度

快速排序每次将待排序数组分为两个部分，在理想状况下，每一次都将待排序数组划分成等长两个部分，则需要logn次划分。
而在最坏情况下，即数组已经有序或大致有序的情况下，每次划分只能减少一个元素，快速排序将不幸退化为冒泡排序，所以快速排序时间复杂度下界为O(nlogn)，最坏情况为O(n^2)。在实际应用中，快速排序的平均时间复杂度为O(nlogn)。
快速排序在对序列的操作过程中只需花费常数级的空间。空间复杂度S(1)。
但需要注意递归栈上需要花费最少logn 最多n的空间。
随机化算法

快速排序的最坏情况基于每次划分对主元的选择。基本的快速排序选取第一个元素作为主元。这样在数组已经有序的情况下，每次划分将得到最坏的结果。一种比较常见的优化方法是随机化算法，即随机选取一个元素作为主元。这种情况下虽然最坏情况仍然是O(n^2)，但最坏情况不再依赖于输入数据，而是由于随机函数取值不佳。实际上，随机化快速排序得到理论最坏情况的可能性仅为1/(2^n)。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度。一位前辈做出了一个精辟的总结：“随机化快速排序可以满足一个人一辈子的人品需求。”
随机化快速排序的唯一缺点在于，一旦输入数据中有很多的相同数据，随机化的效果将直接减弱。对于极限情况，即对于n个相同的数排序，随机化快速排序的时间复杂度将毫无疑问的降低到O(n^2)。
减少递归栈使用的优化

快速排序的实现需要消耗递归栈的空间，而大多数情况下都会通过使用系统递归栈来完成递归求解。在元素数量较大时，对系统栈的频繁存取会影响到排序的效率。
一种常见的办法是设置一个阈值，在每次递归求解中，如果元素总数不足这个阈值，则放弃快速排序，调用一个简单的排序过程完成该子序列的排序。这样的方法减少了对系统递归栈的频繁存取，节省了时间的消费。
一般的经验表明，阈值取一个较小的值，排序算法采用选择、插入等紧凑、简洁的排序。一个可以参考的具体方案：阈值T=10，排序算法用选择排序。
阈值不要太大，否则省下的存取系统栈的时间，将会被简单排序算法较多的时间花费所抵消。
另一个可以参考的方法，是自行建栈模拟递归过程。但实际经验表明，收效明显不如设置阈值。
C++例程

以下是一个用C++编写的快速排序程序。虽然C标准库中提供了快速排序，但作为快速排序的介绍，原理程序的代码更加有助于对快速排序运行过程的分析。
在这个例程中，对于数组x[]的0~n-1号元素的排序，初始调用为：quicksort(x, 0, n-1);
int quicksort_partition(int L[], int Lbb, int Ubb)
{
//随机化
int iRndPivID;
srand(unsigned(time(0)));
iRndPivID = (rand() % (Ubb - Lbb + 1)) + Lbb;
swap(L[iRndPivID], L[Ubb]);
//快排
int iPivValue;
int i;
int iPivPos;
iPivValue = L[Ubb];
iPivPos = Lbb - 1;
for (i=Lbb; i<=Ubb-1; i++)
{
if (L[ i ] <= iPivValue)
{
iPivPos++;
swap(L[iPivPos], L[ i ]);
}
}
iPivPos++;
swap(L[iPivPos], L[Ubb]);
return iPivPos;
}
void quicksort(int L[], int Lbb, int Ubb)
{
int iPiv;
if (Lbb < Ubb)
{
iPiv = quicksort_partition(L, Lbb, Ubb);
quicksort(L, Lbb, iPiv - 1);
quicksort(L, iPiv + 1, Ubb);
}
return;
}
使用C++标准库的快速排序函数

C++的标准库stdlib.h中提供了快速排序函数。
请在使用前加入对stdlib.h的引用：#include <cstdlib> 或 #include <stdlib.h>
qsort(void* base, size_t num, size_t width, int(*)compare(const void* elem1, const void* elem2))
参数表
*base: 待排序的元素（数组，下标0起）。
num: 元素的数量。
width: 每个元素的内存空间大小（以字节为单位）。可用sizeof()测得。
int(*)compare: 指向一个比较函数。*elem1 *elem2: 指向待比较的数据。
比较函数的返回值
返回值是int类型，确定elem1与elem2的相对位置。
elem1在elem2右侧返回正数，elem1在elem2左侧返回负数。
控制返回值可以确定升序/降序。
一个升序排序的例程：
int Compare(const void *elem1, const void *elem2)
{
return *((int *)(elem1)) - *((int *)(elem2));
}
int main()
{
int a[100];
qsort(a, 100, sizeof(int), Compare);
return 0;
}
PASCAL例程

1. 基本思想：
　　在当前无序区R[1..H]中任取一个数据元素作为比较的"基准"(不妨记为X)，用此基准将当前无序区划分为左右两个较小的无序区：R[1..I- 1]和R[I+1..H]，且左边的无序子区中数据元素均小于等于基准元素，右边的无序子区中数据元素均大于等于基准元素，而基准X则位于最终排序的位置上，即R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H)，当R[1..I-1]和R[I+1..H]均非空时，分别对它们进行上述的划分过程，直至所有无序子区中的数据元素均已排序为止。
2. 排序过程：
【示例】：
初始关键字 [49 38 65 97 76 13 27 49］
第一次交换后 ［27 38 65 97 76 13 49 49］
第二次交换后 ［27 38 49 97 76 13 65 49］
J向左扫描，位置不变，第三次交换后 ［27 38 13 97 76 49 65 49］
I向右扫描，位置不变，第四次交换后 ［27 38 13 49 76 97 65 49］
J向左扫描 ［27 38 13 49 76 97 65 49］
（一次划分过程）
初始关键字 ［49 38 65 97 76 13 27 49］
一趟排序之后 ［27 38 13］ 49 ［76 97 65 49］
二趟排序之后 ［13］ 27 ［38］ 49 ［49 65］76 ［97］
三趟排序之后 13 27 38 49 49 ［65］76 97
最后的排序结果 13 27 38 49 49 65 76 97
各趟排序之后的状态
Procedure Parttion(Var R : FileType; L, H : Integer; Var I : Integer);
//对无序区R[1,H]做划分，I给以出本次划分后已被定位的基准元素的位置 //
Begin
  I := 1; J := H; X := R[I] ;//初始化，X为基准//
  Repeat
    While (R[J] >= X) And (I < J) Do
      begin
       J := J - 1 //从右向左扫描，查找第1个小于 X的元素//
       If I < J Then //已找到R[J] 〈X//
         begin
          R[I] := R[J]; //相当于交换R[I]和R[J]//
          I := I + 1
         end;
       While (R[I] <= X) And (I < J) Do
          I := I + 1 //从左向右扫描，查找第1个大于 X的元素///
      end;
If I < J Then //已找到R[I] > X //
       begin         R[J] := R[I]; //相当于交换R[I]和R[J]//
        J := J - 1
       end
  Until I = J;
  R[I] := X //基准X已被最终定位//
End; //Parttion //
Procedure QuickSort(Var R :FileType; S,T: Integer); //对R[S..T]快速排序//
Begin
  If S < T Then //当R[S..T]为空或只有一个元素是无需排序//
    begin
      Partion(R, S, T, I); //对R[S..T]做划分//
      QuickSort(R, S, I-1);//递归处理左区间R[S,I-1]//
      QuickSort(R, I+1,T);//递归处理右区间R[I+1..T] //
    end;
End; //QuickSort//