c++中怎么實現(xiàn)快速排序-創(chuàng)新互聯(lián)

這篇文章將為大家詳細講解有關(guān)c++中怎么實現(xiàn)快速排序，文章內(nèi)容質(zhì)量較高，因此小編分享給大家做個參考，希望大家閱讀完這篇文章后對相關(guān)知識有一定的了解。

成都創(chuàng)新互聯(lián)公司一直在為企業(yè)提供服務(wù)，多年的磨煉，使我們在創(chuàng)意設(shè)計，成都全網(wǎng)營銷推廣到技術(shù)研發(fā)擁有了開發(fā)經(jīng)驗。我們擅長傾聽企業(yè)需求，挖掘用戶對產(chǎn)品需求服務(wù)價值，為企業(yè)制作有用的創(chuàng)意設(shè)計體驗。核心團隊擁有超過10年以上行業(yè)經(jīng)驗，涵蓋創(chuàng)意，策化，開發(fā)等專業(yè)領(lǐng)域，公司涉及領(lǐng)域有基礎(chǔ)互聯(lián)網(wǎng)服務(wù)服務(wù)器托管、重慶APP開發(fā)公司、手機移動建站、網(wǎng)頁設(shè)計、網(wǎng)絡(luò)整合營銷。

說一說快速排序

快速排序，實際中最常用的一種排序算法，速度快，效率高，在N*logN的同等級算法中效率名列前茅?！?/p>

基本思想：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分所有數(shù)據(jù)要小，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序。整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列。

c++中怎么實現(xiàn)快速排序

將數(shù)列變成上述形式，這一步很關(guān)鍵，做好這一步，才能對主元左右的部分進行遞歸調(diào)用。以下是實現(xiàn)這一部分的代碼：

 int partition_sort(int arr[],int l,int r)//l是數(shù)組最左邊，r為最右邊 
 {
   int j=l;//設(shè)計標(biāo)記 
   int t=arr[l];//設(shè)置主元 
 
   for(int i=l+1;i<=r;i++)
   {
     if(arr[i]<t){
       swap(arr[j+1],arr[i]);
       j++;
     }
   }
   
   swap(arr[l],arr[j]);
   return j;
 }

上述代碼中，我把最左邊的元素當(dāng)作主元，這樣的代碼對大多數(shù)排序都很高效，但是不排除個別情況（當(dāng)數(shù)組近乎有序或者當(dāng)數(shù)組內(nèi)有大量重復(fù)元素），這時，我們的排序算法相比于歸并排序顯得并不是那么高效，這和我們的排序算法原理密不可分，細細分析，當(dāng)數(shù)組近乎有序時，我們的快速排序竟然退化到了O（n^2)級別，這顯然是非常不高效的。

要想實現(xiàn)上述不足的優(yōu)化，我們可以將主元隨機選擇，或者采用其他方式的快速排序（雙路快速排序，三路快速排序），本篇內(nèi)容僅作為學(xué)習(xí)快排的基本思想和基本實現(xiàn)，不深入涉及，有興趣的讀者可查閱資料了解。

下面是全部的實現(xiàn)代碼：

 #include <iostream>
 #include <math.h>
 using namespace std;
 //實現(xiàn)函數(shù)，用于partition的遞歸 
 int partition_sort(int arr[],int l,int r)//l是數(shù)組最左邊，r為最右邊 
 {
   int j=l;//設(shè)計標(biāo)記 
   int t=arr[l];//設(shè)置主元 
 
   for(int i=l+1;i<=r;i++)
   {
     if(arr[i]<t){
       swap(arr[j+1],arr[i]);
       j++;
     }
   }
   
   swap(arr[l],arr[j]);
   return j;
 }
 //實現(xiàn)遞歸的調(diào)用函數(shù) 
 void partition(int arr[],int l,int r)
 {
   if(l>=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<<a[i]<<" ";  
   } 
   return 0;  
 }

關(guān)于c++中怎么實現(xiàn)快速排序就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，可以學(xué)到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)建站www.muchs.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機、免備案服務(wù)器”等云主機租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

分享名稱：c++中怎么實現(xiàn)快速排序-創(chuàng)新互聯(lián)
分享網(wǎng)址：http://www.muchs.cn/article36/dpgepg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供用戶體驗、品牌網(wǎng)站設(shè)計、企業(yè)網(wǎng)站制作、動態(tài)網(wǎng)站、網(wǎng)站制作、小程序開發(fā)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)

網(wǎng)站優(yōu)化排名