基本思想

设当前待排序的数组无序区为R[low..high]，利用分治法可将快速排序的基本思想描述为：

• 分解：

在R[low..high]中任选一个记录作为基准（Pivot），以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1)和R[pivotpos+1..high]，并使左边子区间中所有记录的关键字均小于等于基准记录（不妨记为pivot）的关键字pivot.key，右边的子区间中所有记录的关键字均大于等于pivot.key，而基准记录pivot则位于正确的位置（pivotpos）上，它无需参加后续的排序。
注意：划分的关键是要求出基准记录所在的位置pivotpos，划分的结果可以简单地表示为（注意pivot=R[pivotpos]）：
R[low..pivotpos-1].keys ≤ R[pivotpos].key ≤ R[pivotpos+1..high].keys
其中low≤pivotpos≤high。

• 求解：

通过递归调用快速排序对左、右子区间R[low..pivotpos-1]和R[pivotpos+1..high] 快速排序。

• 组合：

因为当“求解”步骤中的两个递归调用结束时，其左、右两个子区间已有序。对快速排序而言， “组合”步骤不需要做什么，可看作是空操作。

算法实现

快速排序算法，Java实现，代码如下所示：

01	public abstract class Sorter {

02	public abstract void sort(int[] array);

03

}

04

05	public class QuickSorter extends Sorter {

06

07

@Override

08	public void sort(int[] array) {

09	quickSort(array, 0, array.length - 1);

10

}

11

12

/**

13	* 通过划分，基于分治思想，递归执行子任务排序最后合并

14	* @param low 数组首位置索引

15	* @param high 数组末位置索引

16

*/

17	private void quickSort(int[] array, int low, int high) {

18	int pivotPos; // 划分基准元素索引

19	if (low < high) {

20	pivotPos = partition(array, low, high);

21	quickSort(array, low, pivotPos - 1); // 左划分递归快速排序

22	quickSort(array, pivotPos + 1, high); // 右划分递归快速排序

23

}

24

}

25

26

/**

27

* 简单划分方法

28	* @param i

29	* @param j

30

* @return

31

*/

32	private int partition(int[] array, int i, int j) {

33	Integer pivot = array[i]; // 初始基准元素，如果quickSort方法第一次调用，pivot初始为数组第一个元素

34	while (i < j) { // 两个指针从两边向中间靠拢，不能相交

35	// 右侧指针向左移动

36	while (j > i && array[j] >= pivot) {

37

j--;

38

}

39	if (i < j) { // 如果在没有使指针i和j相交的情况下找到了array[j] >= 基准元素pivot

40	array[i] = array[j]; // 基准元素放到了j指针处

41	i++; // 左侧i指针需要向右移动一个位置

42

}

43	// 左侧指针向右移动

44	while (i < j && array[i] <= pivot) {

45

i++;

46

}

47	if (i < j) { // 如果在没有使指针i和j相交的情况下找到了array[i] <= 基准元素pivot

48	array[j] = array[i]; // 基准元素放到了i指针处

49	j--; // 右侧j指针需要向左移动一个位置

50

}

51

}

52	array[i] = pivot; // 将基准元素放到正确的排序位置上

53

return i;

54

}

55

}

快速排序算法，Python实现，代码如下所示：

01	class Sorter:

02

'''

03	Abstract sorter class, which provides shared methods being used by

04	subclasses.

05

'''

06	__metaclass__ = ABCMeta

07

08	@abstractmethod

09	def sort(self, array):

10

pass

11

12	class QuickSorter(Sorter):

13

'''

14	Quick sorter

15

'''

16	def sort(self, array):

17	length = len(array)

18	self.__quick_sort(array, 0, length - 1)

19

20	def __quick_sort(self, array, low, high):

21	if low<high:

22	pivotPos = self.__partition(array, low, high)

23	self.__quick_sort(array, low, pivotPos - 1)

24	self.__quick_sort(array, pivotPos + 1, high)

25

26	def __partition(self, array, i, j):

27	pivot = array[i]

28	while i<j:

29	# right side pointer moves to left

30	while j>i and array[j]>=pivot:

31

j = j - 1

32

if i<j:

33	array[i] = array[j]

34

i = i + 1

35	# left side pointer moves to right

36	while i<j and array[i]<=pivot:

37

i = i + 1

38

if i<j:

39	array[j] = array[i]

40

j = j - 1

41	# put the pivot element to the right position

42	array[i] = pivot

43

return i

排序过程

采用分治的思想对待排序数组进行划分。分治法的基本思想是：
将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。
快速排序，主要是求得一个合理的划分，从而基于此划分来分治排序。使用简单划分方法的思想是：
第一步：
设置两个指针i和j，它们的初值分别为区间的下界和上界，即i=low，i=high； 选取无序区的第一个记录R[i](即R[low])作为基准记录，并将它保存在变量pivot中；
第二步：

1. 首先，令j自high起向左扫描，直到找到第1个关键字小于pivot.key的记录R[j]，将R[j]移至i所指的位置上，这相当于R[j]和基准R[i]（即pivot）进行了交换，使关键字小于基准关键字pivot.key的记录移到了基准的左边，交换后R[j]中相当于是pivot；
2. 然后，令i指针自i+1 位置开始向右扫描，直至找到第1个关键字大于pivot.key的记录R[i]，将R[i]移到i所指的 位置上，这相当于交换了R[i]和基准R[j]，使关键字大于基准关键字的记录移到了基准的右边， 交换后R[i]中又相当于存放了pivot；
3. 接着，令指针j自位置j-1开始向左扫描，如此交替改变扫 描方向，从两端各自往中间靠拢，直至i=j时，i便是基准pivot最终的位置，将pivot放在 此位置上就完成了一次划分。

快速排序示例过程，如下所示：
假设待排序数组为array = {94,12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}，数组大小为20。
首先，根据数组下界和上界，求得一个划分，划分过程如下：

• 第一次划分：

初始化：i = 0，j=19，以第一个元素array[0] = 94为基准pivot = array[0] = 94。
首先指针j向前移动：
array[19] = 49<pivot = array[0] = 94，i = 0<j = 19，继续移动j指针；
array[18] = 76<pivot = array[0] = 94，i = 0<j = 18，继续移动j指针；
……
array[1] = 12<pivot = array[0] = 94，i = 0<j = 1，继续移动j指针；
i = 0pivotPos-1 = -1排序停止；右侧部分继续递归执行快速排序。

• 第二次划分：

对于{12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}：
初始化：i = 1，j=19，以第二个元素（除了第一次划分的基准元素）array[1] = 12为基准pivot = array[1] = 12。
首先指针j向前移动：
array[19] = 49>=pivot = array[1] = 12成立，并且j = 19>i = 1，j指针继续移动；
array[18] = 76>=pivot = array[1] = 12成立，并且j = 18>i = 1，j指针继续移动；
array[17] = 65>=pivot = array[1] = 12成立，并且j = 17>i = 1，j指针继续移动；
array[16] = 12>=pivot = array[1] = 12成立，并且j = 16>i = 1，j指针继续移动；
array[15] = 37>=pivot = array[1] = 12成立，并且j = 15>i = 1，j指针继续移动；
array[14] = 90>=pivot = array[1] = 12成立，并且j = 14>i = 1，j指针继续移动；
array[13] = 83>=pivot = array[1] = 12成立，并且j = 13>i = 1，j指针继续移动；
array[12] = 68>=pivot = array[1] = 12成立，并且j = 12>i = 1，j指针继续移动；
array[11] = 5>=pivot = array[1] = 12不成立，j指针停止移动：
此时i = 1<j = 11，将j指针处的元素移动到i指针处：array[1] = 5（基准元素的拷贝为pivot = 12），同时i指针向后移动一次：i++，即i = 2；
子数组变为（下面左边的12表示基准元素，实际j指针移动后并没有移动基准元素，而是pivot变量持有它的拷贝，12 处仍然是5）：
{5,34,76,26,9,0,37,55,76,37,12,68,83,90,37,12,65,76,49}。
指针i向后移动：
array[2] = 34<=pivot = 12不成立，i指针停止移动：
此时i = 2<j = 11，将i指针处的元素移动到j指针处：array[11] = 34（基准元素的拷贝为pivot = 12），同时j指针向前移动一次：j–，即j = 10；
子数组变为：
{5,12,76,26,9,0,37,55,76,37,34,68,83,90,37,12,65,76,49}。
判断i与j：i = 2= pivot = 12成立，并且j = 10>i = 2，j指针继续移动；
array[9] = 76>= pivot = 12成立，并且j = 9>i = 2，j指针继续移动；
array[8] = 55>= pivot = 12成立，并且j = 8>i = 2，j指针继续移动；
array[7] = 37>= pivot = 12成立，并且j = 7>i = 2，j指针继续移动；
array[6] = 0>= pivot = 12不成立，j指针停止移动：
此时j = 6>i = 2，将j指针处的元素array[6] = 0移动到i指针处：array[2] = array[6] = 0（基准元素的拷贝为pivot = 12），同时i指针向后移动一次：i++，即i = 3；
子数组变为（下面左边的12表示基准元素，实际j指针移动后并没有移动基准元素，而是pivot变量持有它的拷贝，12处仍然是0）：
{5,0,76,26,9,12,37,55,76,37,34,68,83,90,37,12,65,76,49}。
指针i第2次向后移动：
array[3] = 76i = 3，将i指针处的元素array[3] = 76移动到j指针处：array[6] = array[3] = 0（基准元素的拷贝为pivot = 12），同时j指针向前移动一次：j–，即j = 5；
子数组变为：
{5,0,12,26,9,76,37,55,76,37,34,68,83,90,37,12,65,76,49}。
判断i与j：i = 3=pivot = 12不成立，j指针停止移动：
此时j = 5>i = 3，将j指针处的元素array[5] = 9移动到i指针处：array[3] = array[5] = 9（基准元素的拷贝为pivot = 12），同时i指针向后移动一次：i++，即i = 4；
子数组变为（下面左边的12表示基准元素，实际j指针移动后并没有移动基准元素，而是pivot变量持有它的拷贝，12处仍然是9）：
{5,0,9,26,12,76,37,55,76,37,34,68,83,90,37,12,65,76,49}。
指针i第3次向后移动：
array[4] = 26i = 4，将i指针处的元素array[4] = 26移动到j指针处：array[5] = array[4] = 26（基准元素的拷贝为pivot = 12），同时j指针向前移动一次：j–，即j = 4；
子数组变为：
{5,0,9,12,26,76,37,55,76,37,34,68,83,90,37,12,65,76,49}。
判断i与j：i = 4<j = 4不成立，条件不满足：
将基准元素放到i指针处，array[4] = pivot = 12；并返回基准元素的索引i = 4。
划分结束。
根据得到的基准元素的索引，递归快速排序。

算法分析

• 时间复杂度

最好情况
在最好情况下，每次划分所取的基准都是当前无序区的”中值”记录，划分的结果是基准的左、右两个无序子区间的长度大致相等，总的关键字比较次数：0(nlgn)。
最坏情况
最坏情况是每次划分选取的基准都是当前无序区中关键字最小（或最大）的记录，划分的结果是基准左边的子区间为空（或右边的子区间为空），而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。
因此，快速排序必须做n-1次划分，第i次划分开始时区间长度为n-i+1，所需的比较次数为n-i(1≤i≤n-1)，故总的比较次数达到最大值：
n(n-1)/2 = O(n^2)
如果按上面给出的划分算法，每次取当前无序区的第1个记录为基准，那么当文件的记录已按递增序（或递减序）排列时，每次划分所取的基准就是当前无序区中关键字最小（或最大）的记录，则快速排序所需的比较次数反而最多。

• 空间复杂度

快速排序在系统内部需要一个栈来实现递归。若每次划分较为均匀，则其递归树的高度为O(logn)，故递归后需栈空间为O(logn)。最坏情况下，递归树的高度为O(n)，所需的栈空间为O(n)。

• 排序稳定性

快速排序是不稳定的。