大話數據結構讀書筆記-排序

1.排序的基本概念與分類

定義:假設含有n個記錄的序列為\({r_1, r_2,...,r_n}\),其相應的關鍵字分別為\({k_1,k_2,...,k_n}\),需要確定1, 2, ..., n的一種序列\(p_1,p_2,...,p_n\),使得其對應的關鍵字滿足\(k_{p1},k_{p2},...k_{pn}\)(非遞減或非遞增)關系,即使得序列成為一個按關鍵字有序得序列\({r_{p1},r_{p2},...,r_{pn}}\),這樣得操作稱為排序。

在排序問題中,通常將數據元素稱為記錄。輸入是一個記錄集合,輸出也是一個記錄集合,所以可以將排序看作是排序表得一種操作。關鍵字\(k_i\)可以是記錄r的主關鍵字,也可以是次關鍵字,甚至是若干數據項的組合。

1.1 排序的穩定性

由于待排序記錄序列中可能存在兩個或兩個以上的關鍵字相等的記錄,排序結果可能存在不唯一的情況。

定義:假設\(k_i=k_j(1<=i<=n,1<=j<=n,i!=j)\),且在排序前的序列中\(r_j\)領先于\(r_j\)(i<j)。如果排序后\(r_i\)仍領先于\(r_j\),則稱所用的排序方法是穩定的;反之,不穩定。

1.2 內排序與外排序

根據是否在排序過程中待排序的記錄是否全部被放置在內存中,排序分為:內排序外排序。

內排序是在排序整個過程中,待排序的所有記錄全部被放置在內存中。外排序是由于排序的記錄個數太多,不能同時放置在內存中,整個排序過程需要在內外存之間多次交換數據才能進行。

對于內排序,排序算法的性能主要受3個方面影響:

  1. 時間性能

    排序算法的時間開銷是衡量其好壞的最重要標志。在內排序中,主要進行兩種操作:比較和移動。高效的排序算法應該具有盡可能少的關鍵字比較次數和盡可能少的移動次數。

  2. 輔助空間

    評價排序算法的另一個標準是執行算法所需要的輔助存儲空間,即除存放待排序所占用的存儲空間之外,執行算法所需要的其他存儲空間。

  3. 算法的復雜性

    這里指算法本身的復雜度。

根據排序過程中借助的主要操作,可以把內排序分為:插入排序、交換排序、選擇排序歸并排序。本文講解的七種排序算法,按照算法的復雜度可以分為兩大類:冒泡排序、簡單選擇排序和直接插入排序屬于簡單算法,希爾排序、堆排序、歸并排序和快速排序屬于改進算法。

? 圖1. 7種內排序算法總覽

2.交換排序

冒泡排序與快速排序屬于交換排序

2.1 冒泡排序

冒泡排序(Bubble Sort)是一種交換排序,基本思想為:兩兩比較相鄰記錄的關鍵字,如果反序則交換,直到沒有反序的記錄為止。

2.1.1 冒泡排序算法

class Sort:  
    # 冒泡排序
    def BubbleSort(self, array):
        length = len(array)
        i = 0
        while i < length-1:
            j = length - 1
            while j > i:
                if array[j-1] > array[j]:
                    array[j-1], array[j] = array[j], array[j-1]
                j -= 1
            i += 1
        return array

假設待排序關鍵字序列為:{9, 1, 5, 8, 3, 7, 4, 6, 2},當i=0時,變量j由8反向循環到1,逐個比較,將較小值交換到前面,直到最后找到最小值放置在第1個位置。如圖2所示

圖2. 冒泡排序模擬

當i=1時,變量j由8反向循環到2,逐個比較,在將關鍵字2交換到第二位置時,也使得關鍵字4與3有所提升。后面不多做贅述。圖中較小的數字如同氣泡慢慢浮到上面,因此該算法命名為冒泡算法。

2.1.2 冒泡排序優化

上面的冒泡排序還可優化,試想一下,待排序列為{2, 1, 3, 4, 5, 6, 7, 8, 9},即除了第一第二關鍵字需要交換外,別的都是正常排序。但算法仍然將i=1到7以及每個循環的j都執行一遍,盡管沒有交換但比較仍顯多余。當i=2時,我們已經對9與8, 8與7, ..., 3 與2作了比較,沒有任何數據交換,這說明數據已經有序,不需要再繼續后面的循環判斷工作。為實現這一想法,改進一下算法,增加一個標記變量flag來實現這一算法的改進。

    def BubbleSort_2(self, array):
        length = len(array)
        flag = True
        i = 0
        while i < length - 1 and flag:
            flag = False
            j = length - 1
            while j > i:
                if array[j-1] > array[j]:
                    array[j-1], array[j] = array[j], array[j-1]
                    flag = True
                j -= 1
            i += 1
        return array

2.1.3 冒泡排序復雜度分析

最好的情況下,即本身有序,需要n-1次比較,無數據交換,時間復雜度為\(O(n)\);最壞的情況下,即待排序序列為逆序,需要比較\(\frac{n(n-1)}{2}\)次,并作等數量級的記錄移動.因此,總的時間復雜度為\(O(n^2)\)。

2.2 快速排序

快速排序是冒泡排序的升級,它們都屬于交換排序類。即它也是通過不斷比較和移動交換來實現排序的,只不過它的實現,增大了記錄的比較和移動的距離,將關鍵字較大的記錄從前面直接移動到后面,關鍵字較小的的記錄從后面直接移動到前面,從而減少了總的比較次數和移動交換次數。

2.2.1 快速排序

快速排序的基本思想是:通過一趟排序將待排記錄分割成獨立的兩部分,其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小,則可分別對這兩部分記錄繼續進行排序,以達到整個序列有序的目的。

話不多說,直接上代碼:

    def QuickSort(self, array):
        length = len(array)
        self.Qsort(array, 0, length-1)
        return array

    def QSort(self, array, low, high):
        if low < high:
            pivot = self.Partition(array, low, high)
            self.QSort(array, low, pivot-1)
            self.QSort(array, pivot+1, high)

    def Partition(self, array, low, high):
        pivotKey = array[low]
        while low < high:
            while low < high and array[high] >= pivotKey:
                high -= 1
            array[low], array[high] = array[high], array[low]
            while low < high and array[low] < pivotKey:
                low += 1
            array[low], array[high] = array[high], array[low]
        return low	

核心代碼為函數Partition,即選定一個關鍵字作為樞軸,將比它小的關鍵字放到左邊,比它大的關鍵字放到右邊。程序開始執行,low=0,high=8, pivotkey=array[low](50),第一輪快排如圖3所示:
圖3. 快排模擬

2.2.2 快速排序優化

1.優化選取樞軸

如果選取的pivotkey是處于整個序列的中間位置,那么我們可以將整個序列分為小數集合和大數集合。但如果選取的樞軸不是中間數,則可能整個序列在一輪pivot=self.Partition后整個序列并沒有實質性的變化,由此pivot=array[low]就變成了一個潛在的性能瓶頸。于是,有了三數取中法,即取三個關鍵字先進行排序,將中間數作為樞軸,一般取左端、中端和右端三個數。

def Partition(self, array, low, high):
    	m = low + (high - low) / 2
        if array[low]>array[high]:
            array[low], array[high] = array[high], array[low]
        if array[m]>array[high]:
            array[m], array[high] = array[high], array[m]
        if array[low] > array[m]:
            array[low], array[m] = array[m], array[low]
        pivotKey = array[low] 
        while low < high:
            while low < high and array[high] >= pivotKey:
                high -= 1
            array[low], array[high] = array[high], array[low]
            while low < high and array[low] < pivotKey:
                low += 1
            array[low], array[high] = array[high], array[low]
        return low	

2.優化不必要的交換

如圖3所示,我們發現,50這個關鍵字,其位置變換是0->8->2->5->4,它的最終目標是4,當中的交換時不需要的。因此可以對Partition函數的代碼再次優化:

    def Parition(self, array, low, high):
        m = low + (high - low) // 2
        print(low, high, m)
        if array[low] > array[high]:
            array[low], array[high] = array[high], array[low]
        if array[m] > array[high]:
            array[m], array[high] = array[high], array[m]
        if array[low] > array[m]:
            array[low], array[m] = array[m], array[low]
        pivotKey = array[low]
        tmp = pivotKey
        while low < high:
            while low < high and array[high] >= pivotKey:
                high -= 1
            array[low] = array[high]
            while low < high and array[low] < pivotKey:
                low += 1
            array[high] = array[low]
        array[low] = tmp
        return low

3.優化小數組時的排序方案

當數組非常小的時候,快速排序反而不如直接插入排序來得更好(直接插入排序是簡單排序中性能最好的)。原因在于快排用了遞歸操作,在大量數據排序時,這點性能影響相對于它整體算法優勢而言可以忽略,但是如果數組很小,就成了大炮打蚊子的大問題。因此,我們需要改進QSort函數。

 	# 設置一個常數, MAX_LENGTH_INSERT_SORT
    def QSort(self, array, low, high):
        if high-low > MAX_LENGTH_INSERT_SORT:
            pivot = self.Parition(array, low, high)
            self.QSort(array, low, pivot-1)
            self.QSort(array, pivot+1, high)
        else:
            # 小于等于常數時用直接插入排序
            InsertSort(array) 

4.優化遞歸操作

遞歸對性能有一定的影響,QSort在尾部有兩次遞歸操作,如果待排序序列化分極端不平衡,遞歸深度趨近于n,而不是平衡時的logn。棧的大小是有限的,每次遞歸掉調用都會耗費一定的??臻g,函數的參數越多,每次遞歸耗費的空間也越多。是故減少遞歸,可以大大的提高性能。這里,對QSort實施尾遞歸,

    def QSort_1(self, array, low, high):
        while low < high:
            pivot = self.Parition(array, low, high)
            self.QSort_1(array, low, pivot-1)
            low = pivot + 1

這里,將if改為while,第一次遞歸后,變量low就沒有用處了,故將pivot+1賦值給low,再循環,來一次Partition(array, low, high),效果等同于QSort(array, pivot+1, high),結果相同,但因采用迭代而不是遞歸的方法可以縮減堆棧深度,從而提高整體性能。

2.2.3 快速排序復雜度分析

在最優的情況下,快速排序算法的時間復雜度為\(O(nlongn)\),在最壞的情況下,集待排序的序列為正序或逆序,每次劃分只得到一個比上一次劃分少一個記錄的子序列,此時需要執行n-1次遞歸調用,比較次數為\(\frac{n(n-1)}{2}\),最終時間復雜度為\(O(n^2)\),平均情況下為\(O(nlogn)\)??臻g復雜度上,為\(O(logn)\),最壞的情況下為\(O(n)\).排序不穩定。

3. 選擇排序

交換排序的思想就是在不斷的交換,通過交換完成最終的排序;選擇排序則是在每一趟\(n-i+i(i=1,2,...,n-1)\)個記錄種選取關鍵字最小的記錄作為有序序列的第i個記錄。

3.1 簡單選擇排序

3.1.1 簡單選擇排序算法

簡單選擇排序法就是通過n-1次關鍵字間的比較,從n-i+1個記錄中選出關鍵字最小的記錄,并和第i(i<=i<=n)個記錄交換之

來看代碼:

    def SimpleSelectionSort(self, array):
        length = len(array)
        for i in range(length-1):
            minv = i
            for j in range(i+1, length):
                if array[minv] > array[j]: # 較小的值位置賦給minv
                    minv = j
            if minv != i: # minv 不等于 i,則說明找到最小值,交換
                array[i], array[minv] = array[minv], array[i]
        return array

3.1.2 簡單選擇排序復雜度分析

時間復雜度為\(O(n^2)\),盡管與冒泡同為\(O(n^2)\),但簡單選擇排序的性能要略優于冒泡排序

3.2 堆排序

前面講到簡單選擇排序時,它在待排序的n個記錄中選擇一個最小的記錄需要比較n-1次,但是第一次查找后沒有將每一趟的比較結果保存下來,在后一趟比較中,有許多比較已經做過,但是由于前面一趟未保存這些比較結果,所以后一趟排序時又重復這些比較操作,因而記錄的比較次數較多。如果可以做到每次選擇到最小記錄的同時,并根據結果對其他記錄做出相應調整,那樣排序的總體效率就就能提高。堆排序是對簡單選擇排序進行的一種改進,并且改進的效果非常明顯。

3.2.1 堆

堆是具有下列性質的完全二叉樹:每個結點的值都大于或等于其做右孩子結點的值,稱為大頂堆(如圖4左圖所示);或者每個結點的值都小于或等于其左右孩子結點的值,稱為小頂堆(如圖4右圖所示)。

圖4 堆

從堆的定義可知,根結點一定是所有結點最大(?。┱?,較大(?。┑慕Y點靠近根結點(但也不絕對)。如果按照層序遍歷的方式給結點從1開始編號,則結點之間滿足如下的關系:

\[\begin{cases} k_i \geq k_{2i} \\ k_i \geq k_{2i+1} \end{cases} 或 \begin{cases} k_i \leq k_{2i} \\ k_i \leq k_{2i+1} \end{cases} 1\leq i \leq \lfloor{\frac{n}{2}}\rfloor \]

若將圖4的大頂堆和小頂堆用從層序遍歷存入數組,則一定滿足上面的關系表達式。

3.2.2 堆排序算法

堆排序就是利用堆(假設大頂堆)進行排序的方法?;舅枷胧牵簩⒋判虻男蛄性斐梢粋€大頂堆,此時整個序列的最大值就是堆頂的根節點。將它移走(即將其與堆數組的末尾元素交換,此時末尾元素就是最大值),然后將剩余的n-1個序列重新構造一個堆,這樣就會得到n個元素中的次小值。如此反復,便能得到一個有序序列

實現堆排序需要解決兩個問題:

  1. 如何由一個無序序列構建一個堆?
  2. 在輸出堆頂元素后,如何調整剩余元素成為一個新的堆?

先看代碼:

    def HeapSort(self, array):
        length = len(array)
        i = length // 2
        while i >= 0:
            self.HeapAdjust(array, i, length-1)
            i -= 1
        i = length-1
        while i > 0:
            array[i], array[0] = array[0], array[i] # 將當前堆頂元素與第i個元素交換,實現
            self.HeapAdjust(array, 0, i-1)          # 將0~i的序列的根節點放到末尾
            i -= 1
        return array

    def HeapAdjust(self, array, s, m):
        if m == 0: # m == 0 時好跳出循環
            return
        temp = array[s]
        j = 2 * s
        while j <= m:
            if j < m and array[j] < array[j+1]: # 調整位置s的元素,將其作為它后面元素的堆根	
                j += 1						    # 結點
            if temp > array[j]:
                break
            array[s] = array[j]
            s = j
            j = j*2
        array[s] = temp

3.2.3 堆排序復雜度分析

堆排序運行的主要時間消耗在初始構建堆和在重建堆時的反復篩選上。在構建堆的過程中,因為是在完全二叉樹的最下層最右邊的非終端結點開始構建,將它與孩子進行比較和若有必要的交換,對于每個非終端結點來說,最多進行兩次比較和交換操作,因此構建整個堆的時間復雜度為\(O(n)\)

在正是排序時,第i次取堆頂記錄重建堆需要用\(O(logi)\)的時間并且需要取n-1次堆頂記錄,故重建堆的時間復雜度為\(O(nlogn)\)

總體來說,堆排序的時間復雜度為\(O(nlogn)\),由于其對原始記錄的排序狀態不敏感,因此無論最好、最壞和平均時間復雜度均為\(O(nlogn)\)

空間復雜度上,需用一個用來交換的暫存單元,也非常不錯。不過由于舉幾的比較與交換時跳躍式進行的,故堆排序是一種不穩定的排序方法。另外,由于初始構建堆所需的比較次數較多,因此不適合待排序序列個數較少的情況。

4.插入排序

4.1 直接插入排序

4.1.1 直接插入排序算法

直接插入排序的基本操作是將記錄插入到已經排好序的有序表中, 從而得到一個新的、記錄數增1的有序表

先看直接插入排序的代碼:

   def InsertSort(self, array):
        length = len(array)
        for i in range(1, length):
            if array[i] < array[i-1]:
                tmp = array[i]
                j = i-1
                while array[j] > tmp and j >= 0:
                    array[j+1] = array[j] # 
                    j -= 1
                array[j+1] = tmp
        return array

4.1.2 直接插入排序復雜度分析

空間復雜度方面,它只需要一個記錄的輔助空間。時間復雜度,在最好的情況,即排序的表本身就是有序的。比如待排序序列為{2, 3, 4, 5, 6},那么比較次數共比較了\(n-1(\sum_{i=2}^{n}1)\)次,并且沒有移動的記錄,時間復雜度為\(O(n)\)

當最壞的情況,即待排序序列是逆序的情況,比如{6, 5, 4, 3, 2},此時比較\(\sum_{i=2}^{n}{i=2+3+...+n}=\frac{(n+2)(n-1)}{2}\)次,而移動記錄的次數也達到最大值\(\sum_{i=2}^{n}{i+1}=\frac{(n+4)(n-1)}{2}\)

若待排序記錄是隨機的,那么根據概率相同的原則,平均比較和移動次數約為\(\frac{n^2}{4}\)次。因此,直接插入排序算法的時間復雜度為\(O(n^2)\)。雖然同樣的\(O(n^2)\)時間復雜度,直接插入排序法比冒泡和簡單選擇排序的性能要好一些。

4.2 希爾排序

4.2.1 希爾排序算法

希爾排序算法代碼如下:

    def ShellSort(self, array):
        length = len(array)
        increment = length
        while increment > 1:
            increment = increment // 3 + 1
            for i in range(increment, length): # 相隔 increment進行直接插入排序
                if array[i] < array[i-increment]:
                    temp = array[i]
                    j = i - increment
                    while j >= 0 and temp < array[j]:
                        array[j+increment] = array[j]
                        j -= increment
                    array[j+increment] = temp
        return array


希爾排序是直接插入排序的升級版本,直接插入排序在記錄數量少或者記錄基本有序的情況下效率很高,但是這兩種情況都比較特殊。所以條件不存在時,效率就會變低?!拌F人”王進喜有句話說的好,“有條件要上,沒有條件創造條件也要上?!蹦侨绾巫尨判蛴涗涊^少呢?很容易想到的是分組,將待排序序列分割成若干子序列,此時每個子序列的待排序記錄就較少了,然后在這些子序列內分別直接插入排序,整個序列都基本有序時,再對全體記錄進行一次直接插入排序。

需要注意,基本有序指的是:小的關鍵字基本在前面,大的基本在后面,不大不小的基本在中間。比如序列{2, 1, 3, 6, 7, 5, 8, 9}就是基本有序,而序列{1, 5, 9, 3 ,7, 8, 2, 4 ,6}這樣9在第三位,2在倒數第三位就不是基本有序。

為達到基本有序,希爾排序采取使用一個增量將整個序列依次間隔增量劃分子序列,這樣每個子序列排好序后,整個序列便能夠達到基本有序。

4.2.2 希爾排序復雜度分析

由于采用“增量”實現跳躍移動,使得排序效率提高,希爾排序算法是不穩定的排序算法?!霸隽俊钡倪x取十分關鍵,應該選取什么樣的增量才是最好,目前還是一個數學難題。但是大量的研究表明,當增量序列為\(dlta[k]=2^{t-k}-1(0\leq k \leq t \leq \lfloor{log_2 (n+1)}\rfloor)\)時,可以獲得不錯的效果,時間復雜度為\(O(n^{3/2})\),要好于直接排序的\(O(n^2)\)。需要注意,增量序列的最后一個增量必須等于1。

5.歸并排序

5.1 歸并排序算法

歸并排序就是利用歸并的思想實現的排序方法。原理是假設初始序列含有n個記錄,則可以看成是n個有序的子序列,每個子序列的長度為1,然后兩兩歸并,得到\(\lceil{n/2}\rceil\)個長度為2或為1的有序子序列;再兩兩歸并,......,如此重復,直至得到一個長度為n的有序序列為止,這種排序方法稱為2路歸并排序。

代碼:

 def MergeSort(self, array):
        self.MSort(array, 0, len(array))
        return array

    def MSort(self, array, s, t):
        if s == t:
            return
        else:
            m = (s+t) // 2
            self.MSort(array, s, m)
            self.MSort(array, m+1, t)
            self.Merge(array, s, m+1, t)

    def Merge(self, SR, s, m, n):

        left = []
        right = []
        for i in range(s, m):
            left.append(SR[i])
        for i in range(m, n):
            right.append(SR[i])
        left_size = m - s
        right_size = n - m
        i = 0
        j = 0
        k = s
        while i<left_size and j < right_size:
            if left[i] < right[j]:
                SR[k]=left[i]
                i+=1
            else:
                SR[k]=right[j]
                j+=1
            k+=1
        while i<left_size:
            SR[k]=left[i]
            k+=1
            i+=1
        while j<right_size:
            SR[k]=right[j]
            k+=1
            j+=1

5.2 歸并排序復雜度分析

一趟歸并需要將SR[0]~SR[n-1]中相鄰的長度為h的有序序列進行兩兩歸并,并將結果放回,這需要將待排序序列中的所有記錄掃描一遍,因此耗費\(O(n)\)時間,而由完全二叉樹的深度可知,整個歸并排序需要進行\(\lceil log_2 n \rceil\)次,因此,總的時間復雜度為\(O(nlogn)\),這是歸并排序算法中最好、最壞、平均的時間性能。

歸并排序在歸并過程中需要與原始記錄序列同樣數量的存儲空間存放歸并結果及遞歸深度為\(log_2 n\)的??臻g,因此空間復雜度為\(O(n+long_2 n)\)。同時歸并排序是一種穩定的算法,總的來說,歸并排序是一種比較占用內存,但效率高且穩定的算法。

posted @ 2020-04-29 15:09  川南煙雨  閱讀(...)  評論(...編輯  收藏
美人江湖手游