算法时间复杂度
最坏情况:O(n^2)
最好情况:O(nlogn)
平均情况:O(nlogn)
稳定性:不稳定排序
快速排序是考察次数最多的排序,无论是在大学专业课的期末考试,还是在公司的面试测试题目中,快速排序都极大的被使用,在实际中快速排序也极大的被使用,如STL中的sort底层就是一个快速排序。
首先在数组中选择一个基准点,然后分别从数组的两端扫描数组,设两个指示标志(low指向起始位置,high指向末尾),首先从后半部分开始,如果发现有元素比该基准点的值小,就交换low和high位置的值,然后从前半部分开始扫描,发现有元素大于基准点的值,就交换low和high位置的值,如此往复循环,直到low>=high,然后把基准点的值放到high这个位置。一次排序就完成了。
以后采用递归的方式分别对前半部分和后半部分排序,当前半部分和后半部分均有序时该数组就自然有序了。
可以看出,在第四躺时已经达到顺序,但是任还是会继续计算几趟直到完成全部运算
第一趟 | 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 |
#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; }
1716 | 数据结构-快速排序 |
知识点标签:排序
本文固定URL:https://www.dotcpp.com/course/165
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程