排序演算法學習（一）：冒泡排序-有解無憂

所謂排序即按照一定的規律將一組資料進行排列，排序演算法的形式化定義如下：設存在一組無序序列 $\{x_1,x_2,...,x_n\}$ ? ,并且存在一個函式 $f(x)$ ?，在經過一系列對該序列中的元素位置調整后，使得新得到的序列滿足對于任意的 $0 \le i \le j \le n$ ?,均有 $f(x_i) \le f(x_j)$ ?（升序排序）或者 $f(x_i) \ge f(x_j)$ ?（降序排序），針對不同的資料源的不同特性，人們設計出了不同的排序演算法，以求對演算法的時間復雜度或者空間復雜度進行優化，常見的排序演算法有：冒泡排序，插入排序，快速排序，桶排序演算法等，下面對各種排序演算法的原理進行簡述，并分析其優缺點，（以下在對排序演算法的描述時，都假設將資料按照升序排序進行排列），

冒泡排序

冒泡演算法的步驟如下：比較相鄰兩個元素的大小，根據比較結果將兩個元素按照從小到大的順序排列，逐步向后移動，一直移動到末端，冒泡演算法中的一輪程序如圖1所示，每i輪的排序程序即是將第i個最大的元素移動到當前的陣列中最大的位置，在每一輪的排序程序中，右邊的已排序序列長度不斷增長，最終使得整個序列都成為已排序序列，冒泡排序的完整程序如下圖所示：

冒泡排序演算法執行程序

圖1 冒泡排序的完整程序

冒泡排序演算法的最基本實作

根據圖1所描述的程序，冒泡排序演算法的最基本的Python代碼實作如下：

[sourcecode language='python'  padlinenumbers='true']
	def bubbleSort(data:List[int])->List[int]:
		length = len(data)
		for i in range(0, length):
			for j in range (0, length - 1):
				if data[j] > data[j+1]:
					tmp = data[j]
					data[j] = data[j+1]
					data[j+1] = tmp
		return data
[/sourcecode]

對優化后的代碼分析可知，一共需要進行 $n$ 輪的排序，每一輪的排序中都需要進行 $n-1$ 次的大小比較，因此該演算法的演算法復雜度為 $O(n^2)$ ，空間復雜度為 $1$ ，

針對每輪比較次數的效率優化

通過對圖1的觀察，第1輪排序完成后，最右側的1個元素是一個已完成排序的序列，在第2輪的排序程序中，最后1次的比較沒有發生順序的改變；第2輪排序完成后，最右側的2個元素是一個已完成排序的序列，在第3輪的排序程序中，最后2次的比較沒有發生順序的改變，第 $i$ 輪排序完成后，最右側的 $i$ 個元素是一個已完成排序的序列，在第 $i+1$ 輪的排序程序中，最后 $i$ 次的比較沒有發生順序的改變，根據這個特點，我們可以對每一輪的排序程序中需要比較的次數進行優化，代碼如下：

def bubbleSort(data:List[int])->List[int]:
            length = len(data)
            for i in range(0, length):
                for j in range (0, length - i - 1):
                    if data[j] > data[j + 1]:
                        tmp = data[j]
                        data[j] = data[j+1]
                        data[j+1] = tmp
            return data

在進行優化之后，可以發現在每一輪的排序程序中需要比較的元素的數量得到了優化，在第 $i$ 輪中排序中進行了 $i-1$ 次大小比較，因此在整個排序程序中，一共需要進行 $\sum_{1}^{n}(i-1)$ 次比較運算，演算法復雜度為 $O(n^2)$ ，空間復雜度為 $1$ ，

針對演算法終止條件的效率優化

另外，還可以對冒泡排序演算法的終止條件進行優化，我們對圖1進行觀察，發現從第3輪開始，序列的順序已經達到排序完成的狀態，此后序列中元素的相對位置不再發生改變，因此我們可以根據此對排序的終止條件的判斷進行優化，代碼如下：

    def bubbleSort(data:List[int])->List[int]):
            length = len(data)
            changed = 0
            for i in range(0, length):
                for j in range (0, length - i - 1):
                    if data[j] > data[j + 1]:
                        tmp = data[j]
                        data[j] = data[j+1]
                        data[j+1] = tmp
                        changed = 1
                    if changed == 0:
                        return data
            return data

在進行優化之后，可以發現排序演算法可能提前終止排序狀態，考慮最好的情況，序列的順序本來就是排列好的，那么需要進行一輪排序來進行確認，一共需要進行 $n-1$ 次排序，因此在最好的情況下演算法的時間復雜度為 $O(n)$ ，空間復雜度為 $1$ ；在最差的情況下，一共需要進行 $\sum_{1}^{n}(i-1)$ 次比較運算，演算法復雜度為 $O(n^2)$ ，空間復雜度為 $1$ ，

雞尾酒排序

雞尾酒排序又稱為雙向冒泡排序，是冒泡排序的一個變種演算法，可以在某些情況下減少演算法的比較次數，雞尾酒排序演算法的程序如圖2所示：

雞尾酒排序演算法執行程序

?圖2 雞尾酒排序演算法的執行程序

對圖2觀察可知，利用雞尾酒排序在第三輪的時候，序列就已經達到了排序完成的狀態，比普通的冒泡排序演算法快了一輪，下面分析為什么會比冒泡演算法快一輪的原因，在冒泡演算法程序中，元素單一的從一側按照從小到大的順序被移動到另一側，但是如果假設有這樣一種情況，即序列的左側的大部分元素的相對順序都是排好的，只有右側部分元素的順序不對，那么此時雞尾酒排序相對于冒泡排序就會有極大的優勢，極端一點的例子，如：序列 $[2,3,4,5,1]$ ,如果按照冒泡排序來進行，那么需要進行4輪排序，如果按照雞尾酒排序的演算法來排序則只需要2輪排序，但是對于某些極端情況，如序列 $[5,4,3,2,1]$ ，冒泡排序和雞尾酒排序都需要進行4輪排序，

雞尾酒排序演算法的Python代碼如下（以下代碼已經針對每輪的比較次數和演算法終止條件進行了優化）:

    def cocktailsort(data:List[int])->List[int]):
            start = 0
            end = len(data)
            changed = 0
            while start != end:
                for i in range(start, len(data) - 1):
                    if data[i] > data[i + 1]:
                        tmp = data[i]
                        data[i] = data[i + 1]
                        data[i + 1] = tmp
                        changed = 1
                print(data)
                if changed == 0:
                    return data
                start = start + 1
                changed = 0
                for i in range(end - 1, 0, -1):
                    if data[i] < data[i - 1]:
                        tmp = data[i]
                        data[i] = data[i - 1]
                        data[i - 1] = tmp
                        changed = 1
                    print(data)
                    if changed == 0:
                        return data
                end = end - 1
            return data

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/117876.html

標籤：其他

上一篇：LeetCode刷題--1.兩數之和（簡單）

下一篇：第十六屆浙江大學寧波理工學院程式設計大賽 E雷頓女士與平衡樹（并查集）