說一說快速排序
快速排序，實際中最常用的一種排序算法，速度快，效率高，在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; } 新聞熱點
疑難解答
圖片精選
