我在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实现。还请多指教。

第二篇