c 快速排序算法 c實現快速排序

c 快速排序算法 c實現快速排序

日期:2023-03-20 19:48:00    编辑:网络投稿    来源:互联网

c++快速排序詳解  快速排序,實際中最常用的一種排序算法,速度快,效率高,下面是小編分享的c++快速排序詳解,一起來看一下吧。  基本思想:通過一趟排序將要排序的數據分割成獨立

c++快速排序詳解

  快速排序,實際中最常用的一種排序算法,速度快,效率高,下面是小編分享的c++快速排序詳解,一起來看一下吧。

  基本思想:通過一趟排序將要排序的數據分割成獨立的兩部分,其中一部分的所有數據都比另外一部分所有數據要小,然后再按此方法對這兩部分數據分別進行快速排序。整個排序過程可以遞歸進行,以此達到整個數據變成有序序列。

  將數列變成上述形式,這一步很關鍵,做好這一步,才能對主元左右的`部分進行遞歸調用。以下是實現這一部分的代碼:

  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;

  }

【c++快速排序詳解】相關文章:

C++ 排序插入排序詳解12-07

C++ this指針詳解11-26

C++歸并排序算法實例11-10

C++插入排序算法實例11-04

php如何實現快速排序09-02

C++ cin輸入流詳解12-08

C語言快速排序算法及代碼12-14

教你JAVA語言快速排序的原理11-13

c++ 中--declspec 的用法詳解12-14