排序算法之插入排序（Python3實作）

插入排序有兩種，一種是穩定的直接插入排序，一種是不穩定的希爾插入排序。下面就簡單介紹一下兩個排序算法以及代碼實作。

一、直接插入排序

# coding: utf-8
# 直接插入排序：首先将第一個元素看成有序序列，從第二個開始，将目前元素
# 與前面的有序序列的最後一個元素進行比較，如果目前元素大，則直接i++判斷下一個
# 否則插入到前面有序序列中的合适位置，若目前元素與有序序列中的某一進制素相等，則
# 插入此元素的後面，是以排序算法是穩定的，時間複雜度是O(n^2)

class DirectInsertSort:
    def __init__(self, data):
        self.data = data

    def sort(self):
        data = self.data
        n = len(data)
        for i in range(1, n):       # 認為第一個元素是有序的，從第二個元素開始和前面的有序數組比較插入
            if data[i]<data[i-1]:   # 如果小于有序數組中最大的元素，則進入尋找帶插入數字的合适位置
                j = i-2
                t = data[i]
                data[i] = data[i-1]
                while j>=0 and data[j]>t:   # data[j]>t 表示穩定
                    data[j+1] = data[j]
                    j-=1
                data[j+1] = t
        return data

def main():
    try:
        data = [int(x) for x in input('請輸入需要排序的數組，以空格分隔').strip().split(' ')]
    except:
        print('輸入不合法')
    else:
        s = DirectInsertSort(data)
        print('排序前的數組：', end=' ')
        print(s.data)
        ans = s.sort()
        print('排序後的數組：', end=' ')
        print(ans)

if __name__ == '__main__':
    main()

           

二、希爾插入排序

 希爾排序是根據直接插入排序提出來的，利用樹的結構特性，在某些情況下可以提高排序的效率。

# coding: utf-8
# 希爾排序：取m個子長度{（一般是n/2,n/4,n/8...1)n為排序數組的長度}，每次比較目前元素和
# （目前元素下标+子長度）的元素，重複m次。希爾排序是不穩定的，

class ShellInsertSort:
    def __int__(self, data):
        pass

    def shellSort(self,data):
        n = len(data)
        d = n//2
        while d>=1:
            data = self.sort(data, d, n)
            d = d // 2
        return data

    def sort(self, data, d, n):
        for i in range(d, n):
            if data[i]<data[i-d]:
                j = i - d - d
                t = data[i]
                data[i] = data[i - d]
                while j >= 0 and data[j] > t:  # data[j]>t 表示穩定
                    data[j + d] = data[j]
                    j -= d
                data[j + d] = t
        return data

def main():
    try:
        data = [int(x) for x in input('請輸入需要排序的數組，以空格分隔').strip().split(' ')]
    except:
        print('輸入不合法')
    else:
        s = ShellInsertSort()
        print('排序前的數組：', end=' ')
        print(data)
        ans = s.shellSort(data)
        print('排序後的數組：', end=' ')
        print(ans)

if __name__ == '__main__':
    main()