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;
} |