1. 复杂度与稳定性文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25228.html
算法时间复杂度文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25228.html
最坏情况：O(n^2)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25228.html
最好情况：O(nlogn)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25228.html
平均情况：O(nlogn)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25228.html
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25228.html
稳定性：不稳定排序文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25228.html
2. 过程介绍文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25228.html
快速排序是考察次数最多的排序，无论是在大学专业课的期末考试，还是在公司的面试测试题目中，快速排序都极大的被使用，在实际中快速排序也极大的被使用，如STL中的sort底层就是一个快速排序。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25228.html
首先在数组中选择一个基准点，然后分别从数组的两端扫描数组，设两个指示标志（low指向起始位置，high指向末尾)，首先从后半部分开始，如果发现有元素比该基准点的值小，就交换low和high位置的值，然后从前半部分开始扫描，发现有元素大于基准点的值，就交换low和high位置的值，如此往复循环，直到low>=high,然后把基准点的值放到high这个位置。一次排序就完成了。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25228.html
以后采用递归的方式分别对前半部分和后半部分排序，当前半部分和后半部分均有序时该数组就自然有序了。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25228.html
3.图示过程文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25228.html
可以看出，在第四躺时已经达到顺序，但是任还是会继续计算几趟直到完成全部运算文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25228.html
| 第一趟 | 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;} |