快速排序算法，C语言代码实例详解
1. 复杂度与稳定性
算法时间复杂度
最坏情况：O(n^2)
最好情况：O(nlogn)
平均情况：O(nlogn)
稳定性：不稳定排序
2. 过程介绍
快速排序是考察次数最多的排序，无论是在大学专业课的期末考试，还是在公司的面试测试题目中，快速排序都极大的被使用，在实际中快速排序也极大的被使用，如STL中的sort底层就是一个快速排序。
首先在数组中选择一个基准点，然后分别从数组的两端扫描数组，设两个指示标志（low指向起始位置，high指向末尾)，首先从后半部分开始，如果发现有元素比该基准点的值小，就交换low和high位置的值，然后从前半部分开始扫描，发现有元素大于基准点的值，就交换low和high位置的值，如此往复循环，直到low>=high,然后把基准点的值放到high这个位置。一次排序就完成了。
以后采用递归的方式分别对前半部分和后半部分排序，当前半部分和后半部分均有序时该数组就自然有序了。
3.图示过程
可以看出，在第四躺时已经达到顺序，但是任还是会继续计算几趟直到完成全部运算
| 第一趟 | 70 | 50 | 30 | 20 | 10 | 70 | 40 | 60 |
| 第二趟 | 60 | 50 | 30 | 20 | 10 | 40 | 70 | 70 |
| 第三趟 | 40 | 50 | 30 | 20 | 10 | 60 | 70 | 70 |
| 第四趟 | 10 | 20 | 30 | 40 | 50 | 60 | 70 | 70 |
| 第五趟 | 10 | 20 | 30 | 40 | 50 | 60 | 70 | 70 |
4. 相关的代码
|
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
|
#include<iostream>using namespace std; void qucik_sort(int a[],int low,int high) { int i,j,temp; i=low; j=high; if(low<high) { temp=a[low]; //设置枢轴 while(i!=j) { while(j>i&&a[j]>=temp) { --j; } if(i<j) { a[i]=a[j]; ++i; } while(i<j&&a[i]<temp) { ++i; } if(i<j) { a[j]=a[i]; --j; } } a[i]=temp; qucik_sort(a,low,i-1); qucik_sort(a,i+1,high); }} int main() { int a[8]= {70,50,30,20,10,70,40,60}; int n=8; qucik_sort(a,0,n-1); for(int i=0; i<n; i++) { cout<<a[i]<<' '; } return 0;} |
THE END
