冒泡排序、选择排序、插入排序

冒泡排序

时间复杂度：an^2 + bN + 1 （固定时间的操作，都是O(1)）–> O(N^2)

额外空间复杂度：O(1)

class ChangeBubbleSort(object):
    def sorted(self, arr: []):
        """
        冒泡排序
        :param arr: 无序列表
        :return: 排序后的列表
        """
        if len(arr) < 2 or arr is not None:
            for i in range(len(arr) - 1):
                for j in range(len(arr) - i - 1):
                    if arr[j] > arr[j + 1]:
                        arr[j], arr[j + 1] = arr[j + 1], arr[j]
        return arr


list_ = [2, 4, 3, 5, 7, 6, 9, 8]
sort_arr = ChangeBubbleSort().sorted(list_)
print(sort_arr)

选择排序

时间复杂度–> O(N^2)

额外空间复杂度O(1)

class SelectionSort(object):
    def sort(self, arr: []):
        """
        选择排序，主要是记录最小值的缩影
        :param arr: 无序数列
        :return: 有序数列
        """
        if len(arr) > 2 or arr is not None:
            for i in range(len(arr) - 1):
                min_index = i

                # 重点：从头部开始，尾部不动 ==> 过程中i不变，j增加
                for j in range(i + 1, len(arr)):
                    # 每一次都找到最小的，替换min_index，最后替换最小值和当前i的数值
                    # if arr[j] < arr[min_index]:
                    #     min_index = j
                    min_index = j if arr[j] < arr[min_index] else min_index
                arr[i], arr[min_index] = arr[min_index], arr[i]
        print(arr)


list_ = [2, 4, 3, 5, 7, 6, 9, 8]
SelectionSort().sort(list_)

---

插入排序

时间复杂度：O(N^2)

额外空间复杂度：O(1)

class InsertionSort(object):
    def sort(self, arr: []):
        """
        插入排序：（选择排序、冒泡排序是不考虑数列情况的，是否有排序）
            最好情况: O(N)
            最差情况: O(N^2)
            平均情况, 都按照最差的情况来算 O(N^2)
        """
        if len(arr) > 2 or arr is not None:

            # 这里从第2个数开始（index=1）, 0~i-1上已经有序
            for i in range(1, len(arr)):

                # 第二个循环，是向前比较
                index = i
                while index > 0 and arr[index - 1] > arr[i]:
                    arr[index], arr[index - 1] = arr[index - 1], arr[index]
                    index -= 1
        print(arr)


list_ = [2, 4, 3, 5, 7, 6, 9, 8]
InsertionSort().sort(list_)