算法思想：分而治之

1）選擇一個基準數，通常選擇第一個數或者最后一個數；

2）通過一趟排序將待排序的記錄分割成獨立的兩部分，即從數組兩頭向中心搜索，如果左邊發現大于基準值且右邊發現小于基準值的數，則這兩個數據交換位置；

3）左右兩側搜索指針相遇，當前值與基準值比較，如果小于基準值則互換位置，此時基準元素在其排好序后的正確位置，它左邊的數都比它小，右邊的都比它大；

4）然后分別對這兩部分記錄用同樣的方法繼續進行排序，直到整個序列有序。

? ? ? ?在平均狀況下，快速排序?n?個數據要Ο(n?log?n)次比較。在最壞狀況下則需要Ο(n²)次比較，但這種狀況并不常見。事實上，快速排序通常明顯比其他Ο(n?log?n) 算法更快，因為它的內部循環（inner loop）可以在大部分的架構上很有效率地被實現出來，且在大部分真實世界的數據，可以決定設計的選擇，減少所需時間的二次方項的可能性。

?

1 int main(int argc, _TCHAR* argv[]) 2 { 3 int a[10] = {3,2,8,7,4,1,9,6,10,5}; 4 5 printf("\r\n數據："); 6 print(a,10); 7 quicksort(a,0,9); 8 printf("\r\n結果："); 9 print(a,10); 10 getchar(); 11 return 0; 12 } 13 14 void print(int a[], int n){ 15 for(int j= 0; j<n; j++){ 16 printf(" %d ", a[j]); 17 } 18 printf(" \r\n "); 19 } 20 21 void quicksort(int v[], int left, int right) 22 { 23 if(left < right) 24 { 25 int tmp =0; 26 int key = v[left]; 27 int low = left; 28 int high = right; 29 while(low < high){ 30 while(low < high && v[high] > key){ 31 high--; 32 } 33 while(low < high && v[low] <= key){ 34 low++; 35 } 36 if(low!=high){ 37 tmp = v[low]; 38 v[low] = v[high]; 39 v[high] = tmp; 40 print(v,10); 41 } 43 } 44 45 if(key > v[low]) 46 { 47 v[left]= v[low]; 48 v[low]=key; 49 print(v,10); 50 } 51 52 quicksort(v,left,low-1); 53 quicksort(v,low+1,right); 54 } 55 }

運行結果：

轉載于:https://www.cnblogs.com/pingwen/p/4458604.html

總結

以上是生活随笔為你收集整理的算法--快速排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。