排序算法——快速排序

2014-01-10

快速排序

快速排序是一种广为使用的排序算法，其算法复杂度为O(NlogN)，从效率上来说是很不错的。

刚接触排序算法的新手可能没有办法很快地把它实现出来，但其实在对它的原理有了透彻的了解后，这一步是不难做到的。

不记得是在哪里看到的了，说熟悉算法的最好办法，就是反复地去实现它，写完删掉重写，知道能够不怎么思考就把它写出来就算是掌握了。我就是通过这个方法来掌握排序算法的。

原理

快速排序采用了“分治法”，关于分治法不想说太多，更多的细节可以参考维基百科。具体来说，快速排序的思想是很简单的，分为两步：

将数组划分为以某个值为分界的两部分
对划分好的两部分各自又进行快速排序

其中第二步就是“分治法”的体现，即所谓“分而治之”。而快速排序的实现工作大多花费在“划分”上。

下面是快速排序的算法描述(python描述)

1: def qsort(array, low, high):
2:     if low < high:
3:         mid = partition(array, low, high)
4:         qsort(array, low, mid - 1)
5:         qsort(array, mid + 1, high)
6:     return array

数组划分

我对这一部分是非常感兴趣的，因为我发现这一部分不仅仅可以用在快速排序中。

划分首先要选定一个值作为分界线。选取这个值的方法有随机选取和固定选取两种，随机选取就不说了，顾名思义；固定选取就是选取当前要划分的区域上特定位置的元素，比如第一个元素或者最后一个元素。本文以选取最后一个元素为例来进行说明。

划分的思想就是，遍历数组，遇到比关键值小的元素，就放到数组前面。在这样的处理过程中，数组前部会有连续的一段空间，其中的所有元素都比关键值小，因此在处理的过程中通常要用一个游标来记录这段空间的最后一个位置，遇到新的小于关键值的元素要放过来时，就将其放到游标后面的位置，并更新游标。如下图所示

当然，我这里说的是将比关键值小的元素交换到数组前部，也有将大于关键值的元素交换到数组尾部以及结合这两种做法的。

数组划分的算法描述为：

 1: def partition(array, low, high):
 2:     cur = low - 1
 3:     key = array[high]
 4: 
 5:     for index in range(low, high):
 6:         elem = array[index]
 7:         if elem < key:
 8:             cur = cur + 1;
 9:             array[index], array[cur] = array[cur], array[index]
10: 
11:     cur = cur + 1;
12:     array[cur], array[high] = array[high], array[cur]
13: 
14:     return cur;

完整实现

下面是一个完整的实现，以及对给定数组进行排序的示例。注明一下，这里的结果是通过org-babel对下面的代码块求值得到的。

 1: # -*- coding: utf-8 -*-
 2: def partition(array, low, high):
 3:     cur = low - 1
 4:     key = array[high]
 5: 
 6:     for index in range(low, high):
 7:         elem = array[index]
 8:         if elem < key:
 9:             cur = cur + 1
10:             array[index], array[cur] = array[cur], array[index]
11: 
12:     cur = cur + 1;
13:     array[cur], array[high] = array[high], array[cur]
14: 
15:     return cur;
16: 
17: def qsort(array, low, high):
18:     if low < high:
19:         mid = partition(array, low, high)
20:         qsort(array, low, mid - 1)
21:         qsort(array, mid + 1, high)
22: 
23:     return array
24: 
25: L = [5, 2, 7, 6, 3, 1, 8, 4]
26: print "排序前: %r" %(L)
27: qsort(L, 0, 7)
28: print "排序后: %r" %(L)

结果

排序前: [5, 2, 7, 6, 3, 1, 8, 4]
排序后: [1, 2, 3, 4, 5, 6, 7, 8]

发散

之前说了，快速排序算法中的数组划分其实不仅仅可用于快速排序，那么，它还可以用于什么地方呢？从我的认识来看，很多需要将数据一分为二的情境中都可以使用到这个算法，比如说 删除字符串中的特定字符 以及这个问题的变形 删除字符串中的重复字符 。将快速排序算法中的划分算法稍作修改，就能得到这两个问题的线性复杂度的解决办法。

附上这两个问题的C语言代码

删除字符串中特定字符

这里的结果同样是通过org-babel对下面的代码块求值得到的

 1: #include <stdio.h>
 2: #include <string.h>
 3: 
 4: int del_char(char *str, char del)
 5: {
 6:     int cur = -1;
 7:     int index = 0;
 8:     char temp = '\0';
 9:     for (; index < strlen(str); ++index) {
10:         if (str[index] != del) {
11:             ++cur;
12:             temp = str[cur];
13:             str[cur] = str[index];
14:             str[index] = str[cur];
15:         }
16:     }
17:     ++cur;
18:     str[cur] = '\0';
19:     return cur;
20: }
21: 
22: int main()
23: {
24:     char s[] = "abcdaaaaab";
25:     del_char(s, 'a');
26:     printf("%s\n", s);
27:     return 0;
28: }

得到的结果为：

bcdb

删除字符串中的重复字符，如将"aabbccdd"处理后得到"abcd"