當前位置:
首頁 > 知識 > 深入淺出數據結構C語言版——有關排序演算法的分析

深入淺出數據結構C語言版——有關排序演算法的分析

與排序演算法有關的定理,這些定理將解釋插入排序博文中提出的疑問(為什麼冒泡排序與插入排序總是執行同樣數量的交換操作,而選擇排序不一定),同時為講述高級排序演算法做鋪墊(高級排序為什麼會更快)。

在討論相關定理之前,我們必須先掌握一個與順序有關的概念:逆序數。

所謂逆序數,就是「逆序組合的個數」,假設我們希望的順序為從小到大(反之同理):

設有元素互異數列X0,X1,X2……Xn-1,(元素互異即數列中任取兩數均不相等)從中任取兩數作為組合(Xa,Xb),若a<b(即Xa在數列中位於Xb之前)且Xa>Xb,則(Xa,Xb)逆序,若a<b且Xa<Xb,則(Xa,Xb)不是逆序。整個數列的逆序數即數列中所有逆序組合(Xa,Xb)的個數。(不難發現,若數列有n個數,則任取兩數的組合(Xa,Xb)共有n(n-1)/2個,n為元素個數。)

下面我們來舉幾個計算逆序數的例子(依然假設我們希望的順序為從小到大):

1.設有數列1,2,3,4,5,因為從中任取兩數(Xa,Xb)且a<b,均有Xa<Xb,即任一組合(Xa,Xb)均非逆序,所以數列1,2,3,4,5的逆序數為:逆序組合的個數=0

2.設有數列5,4,3,2,1,因為從中任取兩數(Xa,Xb)且a<b,均有Xa>Xb,即任一組合(Xa,Xb)均為逆序,所以數列1,2,3,4,5的逆序數為:逆序組合的個數=n(n-1)/2=5*4/2=10

2.設有數列2,3,4,5,1,從中任取兩數(Xa,Xb),a<b且Xa>Xb的組合有(2,1),(3,1),(4,1),(5,1)共4個,即逆序組合共4個,所以數列2,3,4,5,1的逆序數為:逆序組合的個數=4

從例1我們可以推出定理1:若數列為有序,則其逆序數為0。例1的計算過程即本定理的證明。

而從定理1我們又可以得出定理2:若數列非有序,則其逆序數必大於0。證明過程類似於定理1,略

從定理1和定理2我們又可以得出定理3:將數列從非有序轉換為有序(即排序)的過程,就是減少數列逆序數的過程。

明白了什麼是逆序數,以及排序演算法的「本質」之後,我們開始討論定理4:

設有元素互異數列X0,X1,X2……Xn-1,其反數列為Xn-1,Xn-2,……X0,則這兩個數列的逆序數之和必為n*(n-1)/2

因為數列元素互異,所以任取兩數Xa,Xb且a<b,要麼Xa>Xb,要麼Xa<Xb。也就是說組合(Xa,Xb)若在原數列中非逆序,則必在反數列中逆序,反之則反。而元素個數為n的數列中組合(Xa,Xb)的個數共為n*(n-1)/2個,任一組合要麼在原數列逆序,要麼在反數列逆序,所以原數列與反數列的逆序數之和即組合(Xa,Xb)的個數:n*(n-1)/2

有了定理4,我們就可以給出定理5:

有n個互異元素的數列,其平均逆序數為n*(n-1)/4

從定理4可知,給定的數列與其反數列的逆序數之和為n*(n-1)/2,所以該數列的平均逆序數即兩者之和的一半n*(n-1)/2。

接下來是簡單的定理6:

對於元素互異數列,交換其中相鄰的兩個數Xn,Xn+1的位置,則數列的逆序數要麼+1,要麼-1。

假設(Xn,Xn+1)為逆序,則交換兩者將使該組合變為非逆序,但不會影響其他組合如(Xa,Xn)(Xn,Xb)的順序,從而數列逆序數-1

假設(Xn,Xn+1)為非逆序,則交換兩者將使該組合變為逆序,但不會影響其他組合如(Xa,Xn)(Xn,Xb)的順序,從而數列逆序數+1

根據

定理3:將數列從非有序轉換為有序(即排序)的過程,就是減少數列逆序數直至0的過程。

定理5:有n個互異元素的數列,其平均逆序數為n*(n-1)/4

定理6:對於元素互異數列,交換其中相鄰的兩個數Xn,Xn+1的位置,則數列的逆序數要麼+1,要麼-1。

我們可以得出定理7:

通過交換相鄰元素來完成排序的演算法,其平均時間複雜度為Ω(n2)

對於n元素互異的數列,其平均逆序數為n*(n-1)/4,而排序即減少逆序數至0的過程,因為交換相鄰元素最多使逆序數-1,所以必須有n*(n-1)/4次交換才能使數列逆序數為0,即交換相鄰元素的排序演算法平均需要執行n*(n-1)/4次交換操作,也就是說平均時間複雜度為Ω(n*(n-1)/4),即Ω(n2)。雖然我們一直強調元素互異看起來有所不妥,但排序演算法必然要可以處理元素互異情況,而且Ω(n)也只是平均時間複雜度,沒有考慮任何具體情形。

至此,本篇博文對於排序演算法的定理就算是介紹完畢了。但有關排序演算法的分析尚未結束。

我們先來回答插入排序博文中的問題:為什麼冒泡排序和插入排序執行的交換操作總是一樣多。其原因如下:

這兩個演算法都是通過交換相鄰元素來排序的,而且它們都不會執行使數列逆序數+1的交換,也就是說它們每執行一次交換就會且只會使數列的逆序數-1。所以對於給定數列,若其逆序數為n,則兩者都將執行n次交換操作。

那麼,選擇排序有時候只需要更少的交換次數的原因也就出來了,因為選擇排序並不是通過交換相鄰元素來排序的演算法,比如數列5,4,3,2,1,選擇排序第一次「實質交換」後,數列變為了1,4,3,2,5,也就是說它這一次交換就使得數列的逆序數-7。所以選擇排序可以使用更少的「實質交換」來完成排序,當然這並不意味著選擇排序就會很快,原因不再贅述。

接下來,根據前面的定理(3、5、6)。我們可以推出本文最後一個定理,也就是定理7的推理,也是所有高級排序演算法的根本:

要令排序演算法的時間複雜度低於O(n2),必須令演算法執行「遠距離的元素交換」,使得平均每次交換減少不止1逆序數。

文章摘自博客園


中公優就業 幫你成就職業夢:

IT教育專業培訓:https://www.ujiuye.com/

IT職業在線教育:https://xue.ujiuye.com/

大數據時代下做java開發工程師:https://www.ujiuye.com/zt/java/?wt.bd=lsw44106tt

喜歡這篇文章嗎?立刻分享出去讓更多人知道吧!

本站內容充實豐富,博大精深,小編精選每日熱門資訊,隨時更新,點擊「搶先收到最新資訊」瀏覽吧!


請您繼續閱讀更多來自 IT優就業 的精彩文章:

Spark運算元講解(上)
Spark運算元講解(下)
盤點互聯網黑色產業
慶祝優就業甘肅分校UI設計微課堂圓滿成功
Python函數

TAG:IT優就業 |