我在B站學python之排序算法實作

各位小夥伴，剛好本人最近準備面試，想複習一下算法。最近看B站大佬有教python，順帶學習Python文法啦。

這是這兩天，我學習總結的python排序算法實作。初步分2篇獻上。

這是是第一篇：

1.冒泡排序

冒泡排序的思想簡單！！！一個線性表的冒泡一般是，兩個相鄰的元素比較，大（小）的就雙方交換位置（冒泡），接着再和下一個兩兩比較。比如：

1 5 3 2 4 8

比較過程應該是：

1 5 比較，1小，不用交換：

1 5 3 2 4 8

5 3 比較，5大，交換：

1 3 5 2 4 8

5 2 比較，5大，交換：

1 3 2 5 4 8

5 4 比較，5大，交換：

1 3 2 4 5 8

5 8 比較，8大，不用交換：

1 3 2 4 5 8

這樣就把最大的數冒泡到最右邊了。

接着采用同樣的讨論，把倒數第2大的數，冒泡到倒數第2個位置。

這就是冒泡思想。他的時間複雜度是O(N2），是穩定排序。代碼實作如下：

def bubble_sort(self):
        """
        冒泡排序
        :return:
        """
        flag = False
        n = len(self.list)
        for i in range(0, n - 1):
            for j in range(0, n - i):
                if self.list[i] > self.list[i + 1]:
                    (self.list[i], self.list[i + 1]) = (self.list[i + 1], self.list[i])
                    flag = True
            if not flag:
                return self.list
        return self.list
           

2.選擇排序

選擇排序，他的思想是每次(假設第i次）選擇一個最小元素的下标min，記住這個下标。然後往後邊比較，如果誰的值比這個下标指向的值更小，更新下标值，直到最後一個元素。接着，把最小元素和第i個元素交換位置。

這樣，每次從第i個元素開始找最小值，重複n-1遍，就依次找到第0-（n-1）個小的元素并且排好序。

他的思想也是基于比較的實作，不過更聰明，記住的是下标，最終也是交換。

時間複雜度O(n2), 不穩定排序。python代碼實作：

def select_sort(self):
        """
        選擇排序 每次選出最小的值索引，依次放在第i位
        不穩定的排序
        :return:
        """
        n = len(self.list)
        for i in range(0, n - 1):
            min_index = i
            for j in range(i + 1, n):
                if self.list[min_index] > self.list[j]:
                    min_index = j
            if min_index != i:
                (self.list[min_index], self.list[i]) = (self.list[i], self.list[min_index])
            else:
                return self.list
        return self.list
           

3.插入排序

不知道你打過鬥地主沒有？

一副牌裡面有：2 3 4 5 6 7 8 9 10 J Q K A 大王 小王

假設你起牌順序是這樣的：

3 5 2 4 9 7 8 9 J K A Q 大王 。。。

那麼大部分人都會這麼整理牌：

3 5

2 3 5

2 3 4 5

2 3 4 5 9

2 3 4 5 7 9

2 3 4 5 7 8 9

2 3 4 5 7 8 9 J

2 3 4 5 7 8 9 J K

2 3 4 5 7 8 9 J K A

2 3 4 5 7 8 9 J Q K  A 

2 3 4 5 7 8 9 J Q K  A  大王

是不是稍微明白了插入算法的思想？他的思想是：最左邊的數都是有序的，首先預設有個有序數組【3】，然後不斷從剩下的元素中取資料（起牌），取到之後，插入到有序數組【3】中，插入方法是和該數組的最右邊元素比較，如果起牌小，就交換次序；接着繼續往左邊比較，直到遇到不比這張牌小的數。

繼續，采用上面的方法，把剩餘元素插入【3。。。】數組中。得到的結果就是有序數組。

插入排序時間複雜度為O(n2), 是穩定排序。python代碼實作：

def insert_sort(self):
        """
        插入排序
        開始預設一個空數組，後續不斷從待排數組中，往該數組插入資料，保持該數組有序。
        最終取完待排數組中的元素，
        :return:
        """
        n = len(self.list)
        for i in range(0, n - 1):
            j = i + 1
            while j > 0:
                if self.list[j] < self.list[j-1]:
                    (self.list[j-1], self.list[j]) = (self.list[j], self.list[j-1])
                    j -= 1
                else:
                    break
        return self.list
           

以上，是最基本的三種排序算法的python實作。還請多指教。

第二篇