这篇文章主要介绍“c++中如何实现快速排序”,在日常操作中,相信很多人在c++中如何实现快速排序问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”c++中如何实现快速排序”的疑惑有所帮助!接下来,请跟着小编一起来学习吧!
说一说快速排序
快速排序,实际中最常用的一种排序算法,速度快,效率高,在N*logN的同等级算法中效率名列前茅。·
基本思想:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分所有数据要小,然后再按此方法对这两部分数据分别进行快速排序。整个排序过程可以递归进行,以此达到整个数据变成有序序列。
将数列变成上述形式,这一步很关键,做好这一步,才能对主元左右的部分进行递归调用。以下是实现这一部分的代码:
int partition_sort(int arr[],int l,int r)//l是数组最左边,r为最右边 { int j=l;//设计标记 int t=arr[l];//设置主元 for(int i=l+1;i<=r;i++) { if(arr[i]上述代码中,我把最左边的元素当作主元,这样的代码对大多数排序都很高效,但是不排除个别情况(当数组近乎有序或者当数组内有大量重复元素),这时,我们的排序算法相比于归并排序显得并不是那么高效,这和我们的排序算法原理密不可分,细细分析,当数组近乎有序时,我们的快速排序竟然退化到了O(n^2)级别,这显然是非常不高效的。
要想实现上述不足的优化,我们可以将主元随机选择,或者采用其他方式的快速排序(双路快速排序,三路快速排序),本篇内容仅作为学习快排的基本思想和基本实现,不深入涉及,有兴趣的读者可查阅资料了解。
下面是全部的实现代码:
#include#include using namespace std; //实现函数,用于partition的递归 int partition_sort(int arr[],int l,int r)//l是数组最左边,r为最右边 { int j=l;//设计标记 int t=arr[l];//设置主元 for(int i=l+1;i<=r;i++) { if(arr[i] =r)return ; int p=partition_sort(arr,l,r); partition(arr,l,p-1); partition(arr,p+1,r); } int main() { int a[5]; for(int i=0;i<5;i++) { cin>>a[i]; } partition(a,0,4); for(int i=0;i<5;i++) { cout< 到此,关于“c++中如何实现快速排序”的学习就结束了,希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习,快去试试吧!若想继续学习更多相关知识,请继续关注创新互联网站,小编会继续努力为大家带来更多实用的文章!
标题名称:c++中如何实现快速排序-创新互联
文章源于:http://bjjierui.cn/article/doddih.html