快速排序——高手登场

快速排序——高手登场

什么？你工作被问不会写快排？嘘！悄悄地，去找一下快排敲进电脑，别被笑话了哦！这个算法被列为20世纪十大算法之一。

如果说，希尔算法直接插入排序的升级，他们属于同一类，堆排序相当于简单排序的升级，他们属于同一类。而快速排序其实就是最慢的冒泡排序升级，它们都属于交换排序类。

快速排序的基本思想;通过每一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，已达到整个序列有序的目的。

从字面上我们感觉不出它的好处。假设现在要对数组{50,10,90,30,70,40,80,60,20}进行排序。结合代码我们溜达一遍。

	void QuickSort(SqList *L) {
		QuickSort(L,1,L->length);
	} // Of QuickSort

又是一句代码，和归并排序一样，由于需要递归调用，因此我们外封装了一个函数。现在我们来看Qsort的实现。

	void Qsort(SqList *L,int low,int high) {
		int pivot;
		if (lowr[low...high] 分为两部分
											// 计算出数轴值pivot
			Qsort(L,low,pivot-1);			// 对低子表递归排序
			Qsort(L,pivot+1,high);			// 对高子表递归排序
		} // Of if
	} // Of Qsort

从这里，我们应该能理解前面的代码“Qsort(L,1,L->length)”中1和L->length代码的意思了，他就是当前最小下标low和最大下标high。

这一段代码的核心是“pivot = Partition（L.low,high）;”在执行它之前，L.r数组值为{50,10,90,30,70,40,80,60,20}。Partition函数要做的，就是先选取当中的一个关键字，比如选择第一个关键字50，然后想办法将它放到一个位置，使得左边的值都比他小，右边的值都比它大，我们将这样的关键字称作枢轴（pivot）。

在经过 Partition（L，1,9）的执行后，数组变成{20,10,40,30,50,70,80,60,90},并返回值5给pivot，数字5表明50放在数组下标为5的位置。此时，计算机把原来的数组变成了两个位于50左和右小数组{20,10,40,30}和{70,80,60,90},然后递归调用“Qsort(L,1,5-1);”和“Qsort(L,5+1,9);”语句，其实就是在对{20,10,40,30}和{70,80,60,90},分别进行同样的Partition *** 作，直到顺序全部正确为止。

接下来看看Partition

	// 交换顺序表的记录，使枢轴记录到位，并返回其所在位置
	// 此时在它之前的记录都小于它，后面的记录都大于它。
    void Partition(SqList *L,int low,int high) 
{
		int pivotkey;
		pivotkey = L->r[low]; // 用表的第一个记录作为枢轴的记录
		while(lowr[high] >= pivotkey) 
				high--;
			swap(L,low,high); // 将比枢轴记录小的交换到低端
			while(lowr[low]<=pivotkey) 
				low++;
			swap(L,low,high); // 将比枢轴记录大的交换到高端
		} // Of while
		return low; // 返回枢轴所在的位置
	}

1.程序开始，此时 low = 1，high = 9.我们将L.r[low] = L.r[1]=50赋值给枢轴变量pivotkey.如图。

2.第 5-13 行为while循环，目前 low = 1 < high = 9,执行内部语句。

3.第 7 行，L.r[high] = L.r[9] = 20 不大于 pivotkey,因此不执行 第 8 行。

4.第 9 行，交换L.r[low] 与 L.r[high] 的值，使得L.r[1] = 20,L.r[9] = 50.为什么要交换呢？因为第 7 行的比较结果，high位置的值为20小于了枢轴值50，它应该在枢轴值的左边，所以要交换。如图。

 

 5.第 10 行，当L.r[low] = L.r[1] = 20,pivotkey = 50 ，L.r[low] < pivotkey,因此第 11 行low++，此时的 low = 2。继续循环，L.r[low] = L.r[2] = 10 < 50,low++,此时 low = 3.L.r[3] = 90 > 50,退出循环。

6.第 12 行，交换 L.r[low] = L.r[3] 与 L.r[high] = L.r[9] 的值，使得 L.r[3] = 50,L.r[9] = 90。此时，low已经指向了3，如图。

7.执行第 5 行，因为 low = 3 < high = 9,执行循环体。

8.第 7 行，当L.r[high] = L.r[9] = 90,L.r[high] > pivotkey,执行循环，high--，此时 high = 8.继续循环，L.r[8] = 60>50,high--，此时 high = 7. L.r[7] = 80 > 50,high--，此时 high = 6. L.r[6] =  40 < 50，退出循环。

9.第 9 行，交换 L.r[low] = L.r[3] = 50,L.r[high] = L.r[6] = 40 的值，使得L.r[3] = 40，L.r[6] = 50，如图。

 10.第 10 行，当L.r[low] =L.r[3] = 40，pivotkey = 50，L.r[low] = < pivotkey,因此第 11 行，low++，此时 low = 4.继续循环 L.r[4] = 30 < 50,low++，此时 low = 5，L.r[5] = 70 > 50,退出循环。

11.第 12 行，交换 L.r[low] = L.r[5] = 70 与 L.r[high] = L.r[6] = 50 的值，使得 L.r[5] = 50，L.r[6] = 70，如图。

12.再次大循环。因 low = 5 < high = 6,执行循环体后，low = high = 5，退出循环，如图。

 13.最后第 14 行，返回 low 的值为5.函数执行完成。接下来就是递归调用“Qsort（L,1,5-1）;” 和“Qsort（L,5+1,9）;” 语句，对数组{20,10,40,30}和{70,80,60,90}分别进行同样的Partition *** 作。知道顺序全部正确为止。

通过这段电脑式的运行，大家应该懂了吧！Partition 函数其实就是将选取的pivotkey不断交换，比他小的放左边，比他大的放右边，同时自己的位置不断地跳跃，直到完美为止。

时间复杂度是O（nlogn），已经很完美了，但是由于关键字是跳跃交换的，是一种不稳定的排序方法。