基于快速排序的思考

Posted on | In

快速排序，听着名字就觉得他很快，为什么他要叫快排别的排序不叫快排呢？！因为他任何时候都特别快，只要你能给出两个元素的大小关系，就能比较(比如字母a小于字母b，就能对单词进行排序)。而且是原地排序，不需要额外的内存开销。听起来是不是很牛呢！！

再继续分析。快速排序的平均时间复杂度是nlogn，最坏的情况是原始数据已经排好了顺序，复杂度为n^2，所以他是越乱效率越高！因此一般快排都配合着随机数使用。

快速排序也是应用分治的思想，把数组分成两份，两份分成四份，如此分到最后只剩自己一个数据，然后再将所有数据合并起来，排序就完成了。怎么听起来快速排序跟归并排序一样呢？？？其实他们的基本原理是一样的，都是基于分治思想，但是两个非常不同的地方是：归并排序重点在合并，快速排序重点在分解。

先举一个生活中快排的例子！我们上第一节体育课的时候，老师往往会给同学们按身高整队。大家可能都不认识，自己找一个位置站好就行，这个位置是怎么找的呢？其实只要大家的位置都符合前边都比自己矮，后边都比自己高那么整个队就排好了！这就是快排的思想，算法来自生活。

再详细的说说，首先我们班的队伍是非常混乱的，我先从最前面的同学开始比，如果遇到比我高的就跟他换位置，换完一次位置之后，记住自己的位置end，马上从队尾开始跟自己比，比自己矮的跟他换位置，换完一次位置之后，记住自己的位置start，然后再跟前面end-1位置的同学开始比……这样到end<start为止。

可能有点抽象，让我们来看一组数据:

初始数据：46 59 22 86 70 48 11 9 12 88（key为46，end为88，start为59）
第1次处理结果：12 59 22 86 70 48 11 9 46 88
详解：46先跟后面的88比，46<88，不作处理，end–；
然后跟12比，46>12，交换位置；

第1次处理后的结果：12 59 22 86 70 48 11 9 46 88(此时key为46，end为46，start为59)
第2次处理结果：12 46 22 86 70 48 11 9 59 88 详解：46先跟前面的59比，46<59，交换位置；
然后再跟9比，46>9，交换位置；
处理结果为：12 9 22 86 70 48 11 46 59 88
再跟22比，46>22，不作处理，再跟86比，交换位置12 9 22 46 70 48 11 86 59 88 ………………
如此继续，最后结果为：12 9 22 11 41 48 70 86 59 88

不知道能不能看懂？？看不懂的话，直接看代码吧~~~！！ 以下代码用C++编写

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
40
41
42
43
44
45
46
using namespace std; //快速排序
void quickSort(int a[999], int first, int last)
{  
 int i = first, j =last;  
 int key = a[first];  
 int temp = 0;  
 if(first<last)  
 {  
 while(i<j)  
 {  
 while(i<j&&a[j]>key)  
 {  
 j--;  
 }  
 temp = a[j];  
 a[j] = a[i];  
 a[i] = temp;  
 while(i<j&&a[i]<key)  
 {  
 i++;  
 }  
 temp = a[j];  
 a[j] = a[i];  
 a[i] = temp;   
 }  
 quickSort(a,first,i-1);  
 quickSort(a,i+1,last);  
 }  
}  
int main()  
{ //test data:46 59 22 86 70 48 11 9 12 88 int n = 0,i = 0;  
 int a[999];  
 cin>>n;  
 for(i = 0;i<n;i++)  
 {  
 cin>>a[i];  
 }  
 quickSort(a,0,n-1);  
 cout<<"最终排序结果：";  
 for(i = 0;i<n;i++)  
 {  
 cout<<a[i]<<" ";  
 }  
 cout<<endl;  
 return 0;  
}

重点来了，快速排序的速度真的快的没话说，而且还能通过随机数让数据更混乱。所以大部分语言的内置排序函数都是快速排序。比如C语言内置的sort函数，PHP的sort函数。去面试的时候经常会考排序算法，比如给你10W个数字，要你自己写算法给他们排序。一般快速排序就适合用在这种场合。下面我们用PHP实现快速排序：

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
function quickSort(&$a,$first,$last)  
{  
if($first<$last)  
{  
$i = $first;  
$j =$last;  
$key = $a[$first];  
while($i<$j)  
{  
while($i<$j&&$a[$j]>$key)  
{  
$j--;  
}  
//$temp = $a[$i];  
//$a[$i] = $a[$j];  
//$a[$j] = $temp;  
list($a[$i],$a[$j]) = array($a[$j],$a[$i]);  
while($i<$j&&$a[$i]<$key)  
{  
$i++;  
}  
 list($a[$i],$a[$j]) = array($a[$j],$a[$i]);   
}  
quickSort($a,$first,$i-1);  
quickSort($a,$i+1,$last);  
}  
}

我们用xhprof测试一下性能。对100W个数字排序。

1
2
3
4
5
6
7
8
9
10
// cpu:XHPROF_FLAGS_CPU 内存:XHPROF_FLAGS_MEMORY  
// 如果两个一起：XHPROF_FLAGS_CPU + XHPROF_FLAGS_MEMORY   
xhprof_enable(XHPROF_FLAGS_CPU + XHPROF_FLAGS_MEMORY);  
$number = 1000000;  
// 要测试的php代码  
$arr=range(1,$number);  
shuffle($arr);  
quickSort($arr,0,$number-1);  
//sort($arr);  
$data = xhprof_disable();  //返回运行数据

结果花了27S,……这个时间太不理想。面试官会直接pass。那就优化一下，找了半天只有把为了省事通过list实现两个数据交换的功能优化。替换掉之后，速度变成21S了。所以这件事告诉我们写代码莫装逼，弄些稀奇古怪的招数就是找死……

我们直接和PHP内置的sort对比看看，结果2.6S，整整10倍的差距。不过我们的快速排序写的没错啊？为什么速度差这么多？因为PHP内置的函数采用C语言编程，被直接编译成了机器语言。而且通过几代人的优化，PHP的这些内置函数完全可以逆天了。因此我们遇到复杂的数据结构时应该想想有没有相应的内置函数，实在没办法再自己写算法。