冒泡排序，希尔排序

冒泡排序实现

class BubbleSort:
    def sort(self,data:list):
        for i in range(len(data)-1):
            for j in range(len(data)-1-i):
                is_swap = True
                if data[j] > data[j+1]:
                    data[j], data[j+1] = data[j+1], data[j]

对于有序数据或者完全有序的数据而言，可使用下面方式进行优化

优化

class BubbleSort:
    def sort(self,data:list):
        for i in range(len(data)-1):
            # 记录是否存在中间过程中就已经排好序的情况
            is_swap = False
            for j in range(len(data)-1-i):
                is_swap = True
                if data[j] > data[j+1]:
                    data[j], data[j+1] = data[j+1], data[j]
            if not is_swap:
                break

希尔排序

class ShellSort:
    @staticmethod
    def sort(data: list):
        h = len(data) // 2
        while h >= 1:
            start = 0
            while start < h:
                # 当前组开始的下标
                i = start + h
                # 对data[start,start+h,start+2h...]进行插入排序
                while i < len(data):
                    temp = data[i]
                    # 需要替换的位置 暂定当前位置
                    j = i
                    while 0 <= j - h and temp < data[j - h]:
                        data[j] = data[j - h]
                        j -= h
                    data[j] = temp
                    i += h
                start += 1
            # 每次间隔都为之前的 1/2
            h = h // 2

• 时间复杂度 O(n^2- n^2/ 2*logn)