Python3實作各種内部排序算法

文章目錄

• 一、前言
• 二、插入排序算法
• • 1、直接插入排序
  • 2、希爾排序
  • 3、希爾排序和直接插入排序的速度比較
• 三、交換排序算法
• • 1、冒泡排序
  • 2、快速排序
  • 3、快速排序的時間耗費
• 四、選擇排序算法
• • 1、直接選擇排序
  • 2、堆排序
• 五、歸并排序算法

一、前言

排序是計算機内經常進行的一種操作，目的是将一組無序的記錄序列調整為有序的記錄序列，通常分為内部排序和外部排序。若整個排序過程不需要通路外存便能完成，則稱此類排序問題為内部排序；反之，若排序的記錄數量巨大，整個排序過程不可能在記憶體中完成，則稱為外部排序。而在實際中，我們通常使用的是内部排序算法，故本文也主要講解各種内部排序算法的原理及其實作。

二、插入排序算法

插入排序算法的基本思想是：每一步将下一條待排序的記錄有序地插入到已經排好序的記錄子集中，直到将所有待排序的記錄全部插入為止。

1、直接插入排序

直接插入排序是一種最基本的插入排序算法，其具體的插入過程如下：将第 i 條記錄的關鍵字 Ki 順序與其前面記錄的關鍵字 Ki-1, Ki-2, …, K1 進行比較，将所有關鍵字大于 Ki 的記錄依次向右移動一個位置，直到遇見關鍵字小于或等于 Ki 的記錄 Kj 。此時 Kj 後面必為空位置，将第 i 條記錄插入該空位置即可。

完整的直接插入排序是從 i=1（第2條記錄） 開始，即将第1條記錄作為已排好序的單元素子集合，然後将第2條至第n條記錄插入到該子集合中，具體的實作代碼如下所示：

def insert_sort(data_list):
	    # get the length of data list
	    length = len(data_list)
	    for i in range(1, length):
	        # previous index
	        j = i - 1
	        # if current value is less than previous value, then move to previous
	        if data_list[i] < data_list[j]:
	            temp = data_list[i]
	            data_list[i] = data_list[j]
	            # continue to move previous
	            j -= 1
	            while j >= 0 and data_list[j] > temp:
	                data_list[j + 1] = data_list[j]
	                j -= 1
	            # until find the proper place for current value
	            data_list[j + 1] = temp
	    # return the sorted list from minimum to maximum
	    return data_list

           

2、希爾排序

希爾排序又稱為縮小增量排序法，利用直接插入排序的最佳性質，其思想是首先将待排序的關鍵字序列分成若幹個較小的子序列，然後對子序列進行直接插入排序操作。

希爾排序在具體實作時，首先標明兩條記錄間的距離 d1 ，在整個待排序的記錄序列中将所有間隔為 d1 的記錄分成一組，然後在組内進行直接插入排序。接下來去兩條記錄間的距離 d2 < d1 ，在整個待排序的記錄序列中将所有間隔為 d2 的記錄分成一組，同樣進行組内直接插入排序；直到最後標明的兩條記錄見的距離 dt=1 為止。希爾排序的具體實作代碼如下所示：

def shell_sort(data_list):
	    # get the length of data list
	    length = len(data_list)
	    gap = length // 2
	    while gap >= 1:
	        # insert sort
	        for j in range(gap, length):
	            i = j
	            while i - gap >= 0:
	                if data_list[i] < data_list[i - gap]:
	                    data_list[i], data_list[i - gap] = data_list[i - gap], data_list[i]
	                    i -= gap
	                else:
	                    break
	        # decrease the gap
	        gap //= 2
	    # return the sorted list from minimum to maximum
	    return data_list

           

3、希爾排序和直接插入排序的速度比較

希爾排序其實是在直接插入排序的基礎上進行排序處理的，減少了資料移動的次數，也就是對直接插入排序的一種優化。但是通過大量的程式實踐表明，對于資料規模比較小的排序，其實插入排序的效率比希爾排序的效率高；而對于大規模的資料排序，希爾排序的效率更高。是以，建議大家簡單程式使用插入排序，大型程式采用希爾排序。

三、交換排序算法

1、冒泡排序

冒泡排序是一種簡單的交換排序方法，通過對相鄰的資料元素進行交換，進而逐漸将待排序的序列變成有序序列。冒泡排序的基本思想是：從頭掃描待排序的記錄序列，在掃描的過程中順次比較相鄰的兩個元素的大小。下面的代碼則是對冒泡排序的具體實作：

def bubble_sort(data_list):
	    # get the length of data list
	    length = len(data_list)
	    for i in range(0, length - 1):
	        for j in range(0, length - 1 - i):
	            # compare near two elements and swap them
	            if data_list[j] > data_list[j + 1]:
	                data_list[j], data_list[j + 1] = data_list[j + 1], data_list[j]
	    # return the sorted list from minimum to maximum
	    return data_list

           

2、快速排序

在前面的冒泡排序中，在掃描過程中隻是比較了相鄰的兩個元素，進行交換時隻能消除一個逆序。是以，産生了快速排序，對多個不相鄰的元素進行交換，這樣就能消除待排序記錄中的多個逆序，進而加快排序的速度。快速排序的基本思想是：

（1）從待排序記錄序列中選取一條記錄，通常選取第一條記錄作為基數，将其關鍵字設為K1。

（2）将關鍵字小于K1的記錄移到前面，将關鍵字大于K1的記錄移動後面，進而将待排序記錄序列分為兩個子序列。

（3）将關鍵字為K1的記錄插入到其分界線的位置。

通常上述的3個步驟稱為一趟快速排序，後續需要遞歸對左右子序列各自進行快速排序，直到子序列的長度不超過1停止，最後待排序記錄序列就變成一個有序序列。下面是對快速排序的實作代碼：

def quick_sort(data_list):
	    if len(data_list) <= 1:
	        return data_list
	    # left is smaller than base, while right is bigger than base
	    left, right = [], []
	    # base element
	    base = data_list.pop()
	    # partition of original list
	    for data in data_list:
	        if data < base:
	            left.append(data)
	        else:
	            right.append(data)
	    # return the sorted list from minimum to maximum
	    return quick_sort(left) + [base] + quick_sort(right)

           

3、快速排序的時間耗費

快速排序的時間耗費和使用遞歸調用的深度的趟數有關，是以快速排序的時間耗費可分為最好情況、最壞情況和一般情況三種。一般情況介于最好情況和最壞情況之間，沒有讨論的必要，下面着重講下最好和最壞這兩種情況。

（1）在最好的情況下，每趟将序列分為長度相等的兩個子序列，這就相當于是二分查找（也就是折半查找），此時時間耗費為 T(n)=O(nlog2n)。

（2）在最壞的情況下，即原帶排序記錄已經排好序時，算法執行的時間最長。第一趟需要經過 n-1 次比較，第二趟需要經過 n-2 次比較，以此類推，最後總的比較次數為 1 + 2 + 3 + … + n-1 = n(n-1)/2。此時的快速排序其實就相當于是冒泡排序，故時間消耗為 T(n)=O(n2)。

四、選擇排序算法

選擇排序算法其實就是有選擇性的進行排序，但是并不是随意的選擇，選擇排序算法中每一趟會從待排序的記錄中選擇出關鍵字最小的記錄，然後順序放在已經排好序的子序列最後，直到排序完全部記錄為止。常用的選擇排序算法有直接選擇排序和堆排序。

1、直接選擇排序

直接選擇排序又稱之為簡單選擇排序，其過程是：第 i 趟簡單選擇排序是指通過 n-i 次關鍵字的比較，從 n-i+1 條記錄中選擇出關鍵字最小的記錄，并與第 i 條記錄進行交換。這樣共需要進行 i-1 趟比較，直到排序完全部記錄為止。下面是直接選擇排序的具體實作代碼：

def select_sort(data_list):
	    # get the length of data list
	    length = len(data_list)
	    for i in range(0, length):
	        for j in range(i + 1, length):
	            if data_list[i] > data_list[j]:
	                data_list[i], data_list[j] = data_list[j], data_list[i]
	    # return the sorted list from minimum to maximum
	    return data_list

           

2、堆排序

堆排序是指在排序過程中，将向量中存儲的資料看成一棵完全二叉樹，利用完全二叉樹中雙親節點和孩子節點之間的内在關系，以選擇關鍵字最小的記錄的過程。待排序記錄仍采用向量數組方式存儲，并非采用樹這種存儲結構，而僅僅根據完全二叉樹的順序結構特征進行分析而已。

堆排序的具體做法是：将待排序的記錄的關鍵字存放在數組 r[1…n] 中，将 r 用一棵完全二叉樹的順序來表示。每個節點表示 一條記錄，第一條記錄 r[1] 作為二叉樹的根，後面的各條記錄 r[2…n] 依次逐層從左往右順序排序，任意節點 r[i] 的做孩子是 r[2i]、右孩子是 r[2i+1]、雙親是 r[r/2]。調整這棵完全二叉樹，使各節點的關鍵字值滿足下列條件：

r[i].key >= r[2i].key && r[i].key >= r[2i+1].key (i=1, 2, 3, …, n/2)

将滿足上述條件的完全二叉樹稱為堆，将堆中根節點的最大關鍵字稱為最大根堆。反之，若完全二叉樹的任意節點的關鍵字小于或等于其左孩子和右孩子的關鍵字，則對應的堆稱為最小根堆。

堆排序的基本思想是：初始時把要排序的數的序列看作是一棵順序存儲的二叉樹，調整它們的存儲順序，使之成為堆，這時堆的根節點的數值最大。然後将根節點與堆的最後一個節點交換，接着将前面的 n-1 個數重新調整為堆。以此類推，直到隻有兩個節點的堆，并對它們作交換，最後得到有 n 個節點的有序序列。下面是堆排序的具體實作代碼，主要包括兩個過程：一是建立堆，二是堆頂與堆的最後一個元素交換位置。

def adjust_heap(data_list, index, length):
	    lchild = 2 * index + 1
	    rchild = 2 * index + 2
	    maxi = index
	    if index < length // 2:
	        if lchild < length and data_list[lchild] > data_list[maxi]:
	            maxi = lchild
	        if rchild < length and data_list[rchild] > data_list[maxi]:
	            maxi = rchild
	        if maxi != index:
	            data_list[maxi], data_list[index] = data_list[index], data_list[maxi]
	            adjust_heap(data_list, maxi, length)
	
	
	def build_heap(data_list):
	    # get the length of data list
	    length = len(data_list)
	    for i in range(0, length // 2)[::-1]:
	        adjust_heap(data_list, i, length)
	
	
	def heap_sort(data_list):
	    # get the length of data list
	    length = len(data_list)
	    build_heap(data_list)
	    for i in range(0, length)[::-1]:
	        data_list[0], data_list[i] = data_list[i], data_list[0]
	        adjust_heap(data_list, 0, i)
	    return data_list

           

五、歸并排序算法

歸并排序的基本思想是：利用歸并過程，開始時将 k 個資料看成 k 個長度為1的已排好序的表，将相鄰的表成對合并，得到長度為2的 (k/2) 個有序表，每個表含有2個資料；進一步再将相鄰的表成對合并，得到長度為4的 (k/4) 個有序表，…。如此重複下去，直到将所有資料全都合并到一個長度為k的有序表為止，進而完成排序。

歸并排序的實作方法通常有兩種，分别是自底向上和自頂向下方法。

1、自底向上的方法

其基本思想是，當第1趟歸并排序時，将帶排序的記錄清單 R[1…n] 看作n個長度為1的有序子清單，然後将這些子清單進行兩兩歸并。

① 如果 n 為偶數，則得到 n/2 個長度為2的有序子清單。

② 如果 n 為奇數，則最後一個子清單輪空（不參與歸并）。

是以當完成本趟歸并後，前 [log2n] 個有序子清單的長度為2，最後一個子清單的長度仍為1。

第2趟歸并的功能是，對第1趟歸并得到的 [log2n] 個有序子清單實作兩兩歸并。如此反複操作，直到得到一個長度為n的有序列清單為止。

上述每次歸并操作，都是将兩個有序的子清單合并為一個有序的子清單，是以也稱為“二路歸并排序”。

2、自頂向下的方法

使用分治法進行自頂向下的算法設計，主要分為3個步驟。假設歸并排序的目前區間是 R[low,…,high]，分治法的3個步驟如下：

（1）分解：将目前區間一分為二，即求分裂點。

（2）求解：遞歸地對兩個子區間 R[low,…,mid] 和 R[mid+1,…,high] 進行歸并排序。

（3）組合：将已經排序的兩個子區間 R[low,…,mid] 和 R[mid+1,…,high] 歸并為一個有序的區間 R[low,…,high]。

遞歸的終止條件是：子區間的長度為1。

下面則是對歸并排序的自頂向下方法的實作代碼：

def merge(left_list, right_list):
	    result = []
	    i, j = 0, 0
	    while i < len(left_list) and j < len(right_list):
	        if left_list[i] <= right_list[j]:
	            result.append(left_list[i])
	            i += 1
	        else:
	            result.append(right_list[j])
	            j += 1
	    result += left_list[i:]
	    result += right_list[j:]
	    return result
	
	
	def merge_sort(data_list):
	    # get the length of data list
	    length = len(data_list)
	    if length <= 1:
	        return data_list
	    mid = length // 2
	    left_list = merge_sort(data_list[:mid])
	    right_list = merge_sort(data_list[mid:])
	    return merge(left_list, right_list)

           

歸并排序與快速排序、堆排序相比，其最大的特點是，它是一種穩定的排序方法。歸并排序中一趟歸并要多次用到二路歸并算法，一趟歸并的操作是調用 (n/2h) 次合并算法，對 r[1…n] 中前後相鄰且長度為h的有序段進行兩兩歸并，得到前後相鄰、長度為2h的有序段，并存放在 r[1…n] 中，時間複雜度為 O(n)。整個歸并排序需要進行 m(m=log2n) 趟二路歸并，是以歸并排序總的時間複雜度為 O(nlog2n)。