TODO:为什么时间复杂度为nlogn?
快排的实现分为两个函数
Partition和QuickSort
时间复杂度为O(nlogn)
实现如下:
//参数如下：
//i初始值为low - 1，指向传入数组的前一个位置；i表示的已经排好顺序且小于KEY的最后一个元素的index；
//j初始值为low，指向数组开始的位置；指向已排序的部分（包括大于key和小于key的部分）的下一个index
//j遍历数组，如果array[j]小于Key，i++；这时i指向的是大于KEY的元素，swap(array[i],array[j])将大于KEY的值（array[i]）
//与小于KEY的值(array[j])交换
|
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 |
int stPartition(int
* array, int
low, int
high){ int
key = array[high];//KEY为最后一个数组元素 int
i = low - 1; int
j = low; for(;j < high ; j++) { if(array[j] <= key) { i++;//指向大于KEY的第一个位置，同时是这次循环结束之后小于等于KEY的最后一个位置 swap(array[i] , array[j]); } } swap(array[++i],array[high]); return
i;}void
QuickSort(int
* array,int
low, int
high){ cout<<low<<" "<<high<<endl; if(low >= high) return; int
index = 0; index = stPartition(array,low,high); QuickSort(array,low,index - 1);//因为i指向的是KEY的位置，同时KEY是传入数组的最后一个元素，为了避免再次被选为KEY，传入index-1 QuickSort(array,index,high);}int
main(){ int
a[8] = {2,8,7,1,3,5,6,4}; QuickSort(a,0,7); for(int
i = 0 ; i < 8 ; i++) cout<<a[i]<<endl; return
0;} |
原文：http://www.cnblogs.com/next-ten-years-2023/p/3618210.html