c++中如何实现快速排序
导读:本文共1389字符,通常情况下阅读需要5分钟。同时您也可以点击右侧朗读,来听本文内容。按键盘←(左) →(右) 方向键可以翻页。
摘要: 说一说快速排序快速排序,实际中最常用的一种排序算法,速度快,效率高,在N*logN的同等级算法中效率名列前茅。·基本思想:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分所有数据要小,然后再按此方法对这两部分数据分别进行快速排序。整个排序过程可以递归进行,以此达到整个数据变成有序序列。将数列变成上述形式,这一步很关键,做好这一步,... ...
目录
(为您整理了一些要点),点击可以直达。说一说快速排序
快速排序,实际中最常用的一种排序算法,速度快,效率高,在N*logN的同等级算法中效率名列前茅。·
基本思想:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分所有数据要小,然后再按此方法对这两部分数据分别进行快速排序。整个排序过程可以递归进行,以此达到整个数据变成有序序列。
将数列变成上述形式,这一步很关键,做好这一步,才能对主元左右的部分进行递归调用。以下是实现这一部分的代码:
intpartition_sort(intarr[],intl,intr)//l是数组最左边,r为最右边{intj=l;//设计标记intt=arr[l];//设置主元for(inti=l+1;i<=r;i++){if(arr[i]<t){swap(arr[j+1],arr[i]);j++;}}swap(arr[l],arr[j]);returnj;}
上述代码中,我把最左边的元素当作主元,这样的代码对大多数排序都很高效,但是不排除个别情况(当数组近乎有序或者当数组内有大量重复元素),这时,我们的排序算法相比于归并排序显得并不是那么高效,这和我们的排序算法原理密不可分,细细分析,当数组近乎有序时,我们的快速排序竟然退化到了O(n^2)级别,这显然是非常不高效的。
要想实现上述不足的优化,我们可以将主元随机选择,或者采用其他方式的快速排序(双路快速排序,三路快速排序),本篇内容仅作为学习快排的基本思想和基本实现,不深入涉及,有兴趣的读者可查阅资料了解。
下面是全部的实现代码:
#include<iostream>#include<math.h>usingnamespacestd;//实现函数,用于partition的递归intpartition_sort(intarr[],intl,intr)//l是数组最左边,r为最右边{intj=l;//设计标记intt=arr[l];//设置主元for(inti=l+1;i<=r;i++){if(arr[i]<t){swap(arr[j+1],arr[i]);j++;}}swap(arr[l],arr[j]);returnj;}//实现递归的调用函数voidpartition(intarr[],intl,intr){if(l>=r)return;intp=partition_sort(arr,l,r);partition(arr,l,p-1);partition(arr,p+1,r);}intmain(){inta[5];for(inti=0;i<5;i++){cin>>a[i];}partition(a,0,4);for(inti=0;i<5;i++){cout<<a[i]<<"";}return0;}
</div> <div class="zixun-tj-product adv-bottom"></div> </div> </div> <div class="prve-next-news">
c++中如何实现快速排序的详细内容,希望对您有所帮助,信息来源于网络。