基本思想
?

????冒泡排序的一種改進。通過一趟排序將待排記錄分割成獨立的兩部分，其中一部分關鍵字均比另一部分記錄的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序。

算法原理

????使用分治策略，將一個序列分為兩個子序列。

????步驟：

在待排序的n個記錄中任選一個進行記錄（通常選第一個），作為為基準（分區標準）。
進行分區，即：將所有比基準值小的元素放在基準左邊，所有比基準值大的元素放在基準的右邊，中間為所選的基準。

對左右兩個分區遞歸進行步驟1、2，遞歸結束條件是序列的大小是0或1。

特點
?

?數據結構：數組

?穩定性：不穩定

?

過程
??

?????

????????????????宏觀過程

?

復雜度與輔助空間
?

?最差時間復雜度：O(n^2)

?最優時間復雜度：O(nlog2n)

?平均時間復雜度：O(nlgn)

?所需輔助空間：O(log2n)~O(n)

?

源程序

void quickSort(int a[],int low, int high)//a:待排序數組，low:最低位的下標，high:最高位的下標 {int left=low,right=high;int key=a[left];//用數組的第一個記錄作為分區元素if(low>=high)return;while(left!=right){while(left<right&&a[right]>=key)//從右向左掃描，找第一個碼值小于key的記錄，并交換到keyright--;a[left]=a[right];while(left<right&&a[left]<=key)//從左向右掃描，找第一個碼值大于key的記錄，并交換到右邊left++;a[right]=a[left]; ? ?}a[left]=key;//分區元素放到正確位置quickSort(a,low,left-1);quickSort(a,left+1,high); }

?

總結

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

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