快速排序算法介绍

快速排序(QuickSort)是对冒泡排序的一种改进。由 C. A. R. Hoare 在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

算法过程

设要排序的数组是 A[0] …… A[N-1],首先任意选取一个数据(通常选用第一个数据)作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序。值得注意的是,快速排序不是一种稳定的排序算法,也就是说,多个相同的值的相对位置也许会在算法结束时产生变动。

一趟快速排序的算法是:

  1. 设置两个变量 I、J,排序开始的时候:I = 0,J = N - 1;
  2. 以第一个数组元素作为关键数据,赋值给 key,即 key = A[0];
  3. 从 J 开始向前搜索,即由后开始向前搜索( J = J - 1),找到第一个小于 key 的值 A[ J ] ,并与 A[ I ] 交换;
  4. 从 I 开始向后搜索,即由前开始向后搜索( I = I + 1 ),找到第一个大于 key 的 A[ I ],与 A[ J ] 交换;
  5. 重复第3、4、5步,直到 I = J; (3,4步是在程序中没找到时候 j = j - 1,i = i + 1,直至找到为止。找到并交换的时候 i, j 指针位置不变。另外当 i = j这过程一定正好是i+或j-完成的最后另循环结束)

上面这种算法的描述理解起来有点绕(通过Java代码做了示例),但是这种算法通过交换的方式节省了空间。在现在内存空间比较大的情况下,可以考虑下面这种算法(通过Python代码做了示例):

  1. 从数组 A 中取一个中间值 t,创建两个数组B、C,一个(B)用来存放小于 t 的数据,另一个(C)用来存放大于 t 的数据。
  2. 遍历数组 A 并与中间值 t 进行比较,将小于中间值的数据放入数组 B,将大于中间值的数据放入数组 C。
  3. 对数组 B、C 按照1、2步进行排序。
  4. 将 B、t、C组合后输出为排序后的结果。

Java示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class QuickSort {
public static int[] qsort(int arr[], int start, int end){
int refNumber = arr[start];
int i = start;
int j = end;

while( i < j ){
while( (i < j) && (arr[j] > refNumber) ){
j--;
}
while( (i < j) && (arr[i] < refNumber) ){
i++;
}

if( (arr[i] == arr[j]) && (i < j)){
i++;
}else{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}

if( i - 1 > start) arr = qsort(arr, start, i - 1);
if( j + 1 < end ) arr = qsort(arr, j + 1 ,end);

return arr;
}

public static void main(String[] args){
int arr[] = new int[]{ 5, 10, 2, 15, 21, 99, 3, 1, 17, 23, 1, 35};
int len = arr.length - 1;
arr = qsort(arr, 0, len);

for(int i:arr){
System.out.print(i + "\t");
}
}
}

Python示例

这个算法使用的数组支持不定长,对于其他语言来说不一定适用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# -*- coding: utf-8 -*-
def quick_sort(data):
if len(data) >= 2: # 递归入口及出口
mid = data[0] # 选取基准值,也可以选取第一个或最后一个元素
left, right = [], [] # 定义基准值左右两侧的列表
data.remove(mid) # 从原始数组中移除基准值
for num in data:
if num >= mid:
right.append(num)
else:
left.append(num)
return quick_sort(left) + [mid] + quick_sort(right)
else:
return data

array = [2,3,5,7,1,4,6,15,5,2,7,9,10,15,9,17,12]
print(quick_sort(array))
# 输出为[1, 2, 2, 3, 4, 5, 5, 6, 7, 7, 9, 9, 10, 12, 15, 15, 17]

算法变种

快速排序(Quicksort)有几个值得一提的变种算法,这里进行一些简要介绍:

  • 随机化快排:快速排序的最坏情况基于每次划分对主元的选择。基本的快速排序选取第一个元素作为主元。这样在数组已经有序的情况下,每次划分将得到最坏的结果。一种比较常见的优化方法是随机化算法,即随机选取一个元素作为主元。这种情况下虽然最坏情况仍然是O(n^2),但最坏情况不再依赖于输入数据,而是由于随机函数取值不佳。实际上,随机化快速排序得到理论最坏情况的可能性仅为1/(2^n)。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度。一位前辈做出了一个精辟的总结:“随机化快速排序可以满足一个人一辈子的人品需求。”
  • 平衡快排(Balanced Quicksort):每次尽可能地选择一个能够代表中值的元素作为关键数据,然后遵循普通快排的原则进行比较、替换和递归。通常来说,选择这个数据的方法是取开头、结尾、中间3个数据,通过比较选出其中的中值。取这3个值的好处是在实际问题(例如信息学竞赛……)中,出现近似顺序数据或逆序数据的概率较大,此时中间数据必然成为中值,而也是事实上的近似中值。万一遇到正好中间大两边小(或反之)的数据,取的值都接近最值,那么由于至少能将两部分分开,实际效率也会有2倍左右的增加,而且利于将数据略微打乱,破坏退化的结构。
  • 外部快排(External Quicksort):与普通快排不同的是,关键数据是一段buffer,首先将之前和之后的M/2个元素读入buffer并对该buffer中的这些元素进行排序,然后从被排序数组的开头(或者结尾)读入下一个元素,假如这个元素小于buffer中最小的元素,把它写到最开头的空位上;假如这个元素大于buffer中最大的元素,则写到最后的空位上;否则把buffer中最大或者最小的元素写入数组,并把这个元素放在buffer里。保持最大值低于这些关键数据,最小值高于这些关键数据,从而避免对已经有序的中间的数据进行重排。完成后,数组的中间空位必然空出,把这个buffer写入数组中间空位。然后递归地对外部更小的部分,循环地对其他部分进行排序。
  • 三路基数快排(Three-way Radix Quicksort,也称作Multikey Quicksort、Multi-key Quicksort):结合了基数排序(radix sort,如一般的字符串比较排序就是基数排序)和快排的特点,是字符串排序中比较高效的算法。该算法被排序数组的元素具有一个特点,即multikey,如一个字符串,每个字母可以看作是一个key。算法每次在被排序数组中任意选择一个元素作为关键数据,首先仅考虑这个元素的第一个key(字母),然后把其他元素通过key的比较分成小于、等于、大于关键数据的三个部分。然后递归地基于这一个key位置对“小于”和“大于”部分进行排序,基于下一个key对“等于”部分进行排序。

参考资料

  1. http://baike.baidu.com/view/19016.htm

cocowool

A FULL STACK DREAMER!