排序算法之快速排序算法

当初上算法课的时候没有太认真，加上平时用算法真的用得蛮少。这不，都快忘得差不多了。看了几遍维基百科，没有完全看懂。于是想作点笔记，用足够简单的文字描述清楚算法的具体工作方式与实现。以便在将来再次忘却时能够快速地回忆起来。

算法

快速排序算法（也叫作分区交换算法）是一种基于比较的不稳定排序算法，其采用分治（Divide and conquer）的方式对目标数组进行处理。总的说来它的排序方式是：先任意选取一个基准元素，然后重排数组，使得所有比基准小（或等于）的元素排在基准元素的左边（或右边），比基准大（或等于）的元素排在基准元素的右边（或左边），这样就得到了两个子数组，最后再对已分组的两个子数组递归地运用选基准、重排操作，最终得到的就是一个已排好序的完整数组。具体步骤如下：

1. 选基准元素

   基准元素位置的选取是任意的，就是说数组中的任意一个元素都可以作为基准元素。通常有三种选取方式：选择最左边的元素、选择最右边的元素、非处于两端的中间元素。最常用的是最右边的那个元素，这样做效率更高一些，参见：基准元素的选取。选取的基准元素的位置不同，会导致分区算法迥异，所以，不要过于追究为什么两个算法在某些方面几乎完全不同。要彻底明白的是那三个步骤，特别是分区操作！

2. 分区、重排、划分子数组

   这一步是关键操作。基于分治思想，结合基准元素，把整个数组分成两部分：在基准元素左边的元素都小于（或等于）基准元素，在基准元素右边的元素都大于（或等于）基准元素。这样一来就得到了两个子数组。具体图示如下：

   比如有这样一个（乱序）数组： -1 0 2 1 3 -3 -2

   基准元素选取得不同，会有以下三种结果（从小到大排序）：

   1. 若选最左边的 -1。分区算法完成后，应该得到这样的结果： -3 -2 -1 0 2 1 3

   2. 若选取最右边的 -2。则是这样的结果： -3 -2 -1 0 2 1 3

   3. 若选取中间任意的 0。则是这样的结果： -1 -3 -2 0 2 1 3

   以上的操作就明显已经能够看出此步骤（分区、重排）的目的，子数组就已经出现。

3. 对两个子数组递归运用前两步操作

   这一步就是分治算法的核心---分而治之。

   假设第2步采用第3种结果，接着我们再对基准元素（0）左边的子数组应用前面两个步骤（选取最右边的为本次的基准元素），那么将会得到以下结果： -3 -2 -1

   仔细观察已经可以发现，它已经排好序了！

   所以，递归地运用前面两个步骤，一定会得到一个最终排好序的整个数组！

   递归是有结束条件的，那就是当待排序的（子）数组只有一个元素时。无论多长的数组，此条件总会在递归递进多次后结束！

实现

这里我仅以C语言为例实现快速排序算法，并且，元素为整型，选取最右边的元素作为基准元素。

1. 快速排序算法

   也就是前面三个步骤的代码，但把分区操作独立出去了：

   int quick_sort(int a[], int lo, int hi) {
   	if(lo < hi) {
   		int p = partition(a, lo, hi); // 分区算法
   
   		quick_sort(a, lo, p-1);
   		quick_sort(a, p+1, hi);
   	}
   
   	return 0;
   }

   注意实现上的一些细节，数组的大小没有使用长度的形式来标识，而是用的上下边界（lo & hi），限定 lo < hi 也是必须的（若相等，也就是说数组只有一个元素，就没必要排序了）。其中调用了接下来马上将提到的分区算法。分区算法返回基准元素（在原数组中）的下标（基于边界，而非从0开始）。然后快速排序算法再对以基准元素划分的两个子数组递归地调用快速排序算法。

2. 分区算法

   前面已经把分区算法所作的操作描述得很清楚了。这里就按维基百科上面使用的伪代码那样，以最右边的元素作为基准元素，作从小到大排序。

   伪代码是这样的：

     // lo 是最左边的那个元素的下标
     // hi 是最右边的那个元素的下标（包含在内）
     partition(A, lo, hi)
        pivotIndex := choosePivot(A, lo, hi) // 先基准元素
        pivotValue := A[pivotIndex]
        // 把基准元素放到 A[hi]，这样一来，基准元素总是相当于选取的是最后一个元素
        // 同时方便了算法的实现：只需一个循环变量，操作完全在原数组中（in-place）进行
        swap A[pivotIndex] and A[hi] 
        storeIndex := lo // 储存索引
        // 把剩下的元素和基准元素对比，把小于基准元素的元素全部放到左边（储存索引为下标）
        for i from lo to hi−1, inclusive
            if A[i] < pivotValue
                swap A[i] and A[storeIndex]
                storeIndex := storeInd
        // 此时，储存索引前面的元素都比基准元素小（或相等），后面的都比基准元素大（或相等）
        // 所以应把基准元素放到正确的位置
        swap A[storeIndex] and A[hi]  
        return storeIndex // 返回基准元素的下标，完成分区操作

   实现代码：

   int partition(int a[], int lo, int hi) {
   	int storeIndex = lo;
   	int tmp;
   	int pivot = a[hi];
   
   	for(int i=lo; i <= hi-1; i++) {
   		if(a[i] < pivot) {
   			tmp = a[storeIndex];
   			a[storeIndex] = a[i];
   			a[i] = tmp;
   
   			storeIndex++;
   		}
   	}
   
   	tmp = a[storeIndex];
   	a[storeIndex] = a[hi];
   	a[hi] = tmp;
   
   	return storeIndex;
   }

   分区算法并不是唯一的，如果不把基准元素设置为两端的元素之一，那就需要两个循环变量。如果不采用储存索引的方式，还可能需要额外的存储空间。所以，维基百科上面采用的算法其实是很好的。

3. 测试算法

   int main() {
   	int a[7] = {-1, 0, 2, 1, 3, -3, -2};
   	quick_sort(a, 0, 6);
   	for(int i=0; i<7; i++)
   		printf("%d ", a[i]);
   
   	printf("\n");
   	return 0;
   }

至此，对快速排序算法的介绍就结束了！

参考

• Quicksort - Wikipedia, the free encyclopedia
• QUICKSORT (Java, C++) | Algorithms and Data Structures
• Quicksort - YouTube