數據結構筆記--排序(4)

4 人贊了文章

五.快速排序

快速排序是對冒泡排序演算法的改進，核心思想就是通過一趟排序把待排序序列分成兩部分，一部分比關鍵字（樞軸）大，一部分比關鍵字小，重複以上過程，直到排序完成

看看具體怎麼做

int a[] ={49 ,38 ,65 ,97 ,76 ,13 ,27 ,49}

• 以待排序序列的第一個元素49為關鍵字 第一趟：27 38 13 49 76 97 65 49
• 以待排序序列的第一個元素27 76為關鍵字 第二趟：13 27 38 49 49 65 76 97

是不是感覺非常快，有點不適應？那麼來個慢動作

第一趟排序

定義兩個指針，一個叫low ,一個叫high

low high

49 38 65 97 76 13 27 49 選擇關鍵字49，一般選擇待排序序列第一個元素為關鍵字

a[high]=49 high=high-1 a[high] = 27<49

49<--->27 交換位置

low high

27 38 65 97 76 13 49 49

a[low]=38<49 low+=1 a[low]=65

49<----->65交換位置

low high

27 38 49 97 76 13 65 49

a[high]=65>49 high-=1 a[high]=13<49

49<----->13交換位置

low high

27 38 13 97 76 49 65 49

a[low]=13<49 low+=1 a[low]=97>49

49<----->97交換位置

low high

27 38 13 49 76 97 65 49

a[high]=97>49 high-=1 a[high]=76>49

high-=1 a[high]=49 並且 low==high

我們發現，此時序列已經被分成兩個部分，一邊比49小，一邊比49大。

至此，第一趟排序已經完成

第二趟排序與第一趟排序步驟相同，這裡不再重複

下面我們來看看代碼實現

int partition(ElementType a[],int low,int high){ int key = a[low];//關鍵字 while(low<high){ while(low<high && a[high]>=key) --high;//在序列中找一個比關鍵字小的數 a[low] = a[high]; while(low<high && a[low]<=key) low++;//在序列中找一個比關鍵字大的數 a[high] = a[low]; if(low>=high) break; } a[low] = key;//插入關鍵字 return low;}void qSort(ElementType a[],int s,int r)//快速排序{ if(s<r){//若低位小於高位 int q = partition(a,s,r);//將待排序序列分成兩個序列，得到關鍵字的位置 qSort(a,s,q);//對關鍵字左邊的序列排序 qSort(a,q+1,r);//對關鍵字右邊的序列排序 }}

分析

快速排序的平均時間為k*n*ln(n) ，並且快速排序目前被認為是最好的一種內部排序方法

時間複雜度為O(n*ln(n))

T(N) = T(N)

如果初始序列為基本有序時，快速排序將退化為冒泡排序，時間複雜度為O（N^2）

六.堆排序