建站
咨詢
售后
建站咨詢
新聞中心
這篇文章主要介紹“c++中如何實現(xiàn)快速排序”，在日常操作中，相信很多人在c++中如何實現(xiàn)快速排序問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”c++中如何實現(xiàn)快速排序”的疑惑有所幫助！接下來，請跟著小編一起來學(xué)習(xí)吧！
說一說快速排序
快速排序，實際中最常用的一種排序算法，速度快，效率高，在N*logN的同等級算法中效率名列前茅?！?/p>
基本思想：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分所有數(shù)據(jù)要小，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序。整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列。
將數(shù)列變成上述形式，這一步很關(guān)鍵，做好這一步，才能對主元左右的部分進行遞歸調(diào)用。以下是實現(xiàn)這一部分的代碼：
int partition_sort(int arr[],int l,int r)//l是數(shù)組最左邊，r為最右邊
{
int j=l;//設(shè)計標記
int t=arr[l];//設(shè)置主元
for(int i=l+1;i<=r;i++)
{
if(arr[i]上述代碼中，我把最左邊的元素當作主元，這樣的代碼對大多數(shù)排序都很高效，但是不排除個別情況（當數(shù)組近乎有序或者當數(shù)組內(nèi)有大量重復(fù)元素），這時，我們的排序算法相比于歸并排序顯得并不是那么高效，這和我們的排序算法原理密不可分，細細分析，當數(shù)組近乎有序時，我們的快速排序竟然退化到了O（n^2)級別，這顯然是非常不高效的。
要想實現(xiàn)上述不足的優(yōu)化，我們可以將主元隨機選擇，或者采用其他方式的快速排序（雙路快速排序，三路快速排序），本篇內(nèi)容僅作為學(xué)習(xí)快排的基本思想和基本實現(xiàn)，不深入涉及，有興趣的讀者可查閱資料了解。
下面是全部的實現(xiàn)代碼：
#include
#include
using namespace std;
//實現(xiàn)函數(shù)，用于partition的遞歸
int partition_sort(int arr[],int l,int r)//l是數(shù)組最左邊，r為最右邊
{
int j=l;//設(shè)計標記
int t=arr[l];//設(shè)置主元
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<到此，關(guān)于“c++中如何實現(xiàn)快速排序”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識，請繼續(xù)關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編會繼續(xù)努力為大家?guī)砀鄬嵱玫奈恼拢?/p>
本文名稱：c++中如何實現(xiàn)快速排序-創(chuàng)新互聯(lián)
分享地址：http://fisionsoft.com.cn/article/doddih.html
