程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> c++快速排序詳解

c++快速排序詳解

編輯:關於C++

c++快速排序詳解。本站提示廣大學習愛好者:(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]<t){
       swap(arr[j+1],arr[i]);
       j++;
     }
   }
   
   swap(arr[l],arr[j]);
   return j;
 }

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

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

下面是全部的實現代碼:

 #include <iostream>
 #include <math.h>
 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]<t){
       swap(arr[j+1],arr[i]);
       j++;
     }
   }
   
   swap(arr[l],arr[j]);
   return j;
 }
 //實現遞歸的調用函數 
 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;  
 } 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved