三、排序：其它排序算法

3.1 希尔排序

class ShellSort:
    """
    希尔排序（一种分组插入排序算法）
    时间复杂度：取决于Gap序列（https://en.wikiredia.com/wiki/Shellsort#Gap_sequences）
    空间复杂度：O(1)
    简介：
        Gap序列为 n/2, n/4, n/8 ..., 1 的希尔排序算法实现：
            1 取一个整数d1=n/2，将列表分为d1个组，此时每组相邻的两个元素之间的下标间距为d1，再对每个组的元素直接进行插入排序
            3 取一个整数d2=d1/2，将列表分为d2个组，此时每组相邻的两个元素之间的下标间距为d2，再对每个组的元素直接进行插入排序
            3 重复以上操作，直到di=1，即所有元素在同一个组内，此时进行插入排序即可得到最终有序列表
    """

    @staticmethod
    def sort_gap(li, gap):
        """
        分组插入排序实现方式1
        :param li:
        :param gap: 分组间距
        :return:
        """
        n = len(li)
        for right in range(gap, n):
            curr = li[right]
            for left in range(right - gap, -1, -gap):
                if li[left] > curr:  # curr和当前组内的有序区元素逐个比较
                    li[left + gap] = li[left]
                else:  # 直到找到正确的位置，退出循环
                    li[left + gap] = curr
                    break
            else:  # curr比当前组内的有序区所有元素都小
                li[right % gap] = curr  # right % gap 为当前组的第一个元素下标
        return li

    @staticmethod
    def sort_gap_2(li, gap):
        """
        分组插入排序实现方式2
        :param li:
        :param gap: 分组间距
        :return:
        """
        n = len(li)
        for right in range(gap, n):
            curr = li[right]
            left = right - gap
            while left >= 0 and li[left] > curr:  # curr和有序区元素逐个比较，直到找到正确的位置，退出循环
                li[left + gap] = li[left]
                left -= gap
            li[left + gap] = curr  # 补充空位
        return li

    def sort(self, li):
        """
        希尔排序
        :param li:
        :return:
        """
        n = len(li) // 2
        while n >= 1:
            self.sort_gap(li, n)
            n //= 2
        return li
      

3.2 计数排序

class CountSort:
    """
    计数排序
    时间复杂度：O(n)
    空间复杂度：O(n)
    简介：
        适用条件
            假设已知列表中数据范围在0-100之间
        1 生成一个长度为100的列表
        2 遍历列表，对1-100之间的元素出现次数做统计，并存储
        3 更具统计后的数据按顺序展开，生成新的列表即排序完成
    """

    @staticmethod
    def count_sort(li, max_count=100):
        """
        计数排序
        :param li:
        :param max_count:
        :return:
        """
        count = [0 for _ in range(max_count + 1)]  # 生成一个长度为100的列表
        for val in li:
            count[val] += 1  # 对1-100之间的元素出现次数做统计
        li.clear()
        for ind, val in enumerate(count):
            for _ in range(val):
                li.append(ind)

    def sort(self, li):
        """
        计数排序
        :param li:
        :return:
        """
        self.count_sort(li, 100)
        return li

3.3 桶排序

class BucketSort:
    """
    桶排序
    时间复杂度：平均O(n+k)、最坏O(n*n*k)
    空间复杂度：O(n*k)
    简介：
        适用条件
            假设已知列表内元素都在1-10000范围内
        1 构建100个桶，每个桶内存放固定范围内的元素
        2 遍历列表，根据元素范围确定该放哪个桶内
        3 对每个桶内元素排序，所有桶加起来即为有序列表
    效率：
        取决于数据的分布，对不同数据排序时采取不同对分桶策略
    """

    @staticmethod
    def bucket_sort(li, n=100, max_num=10000):
        buckets = [[] for _ in range(n)]  # 创建桶
        for val in li:
            i = min(val // (max_num // n), n - 1)  # i 表示var放到几号桶里
            buckets[i].append(val)  # 把val加到桶里
            for j in range(len(buckets[i]) - 1, 0, -1):  # 同时保持桶内的顺序
                if buckets[i][j] < buckets[i][j - 1]:
                    buckets[i][j], buckets[i][j - 1] = buckets[i][j - 1], buckets[i][j]
                else:
                    break
        sorted_li = []
        for buc in buckets:
            sorted_li.extend(buc)
        return sorted_li

    def sort(self, li):
        """
        桶排序
        :param li:
        :return:
        """
        return self.bucket_sort(li, 10, 100)

3.4 基数排序

class RadixSort:
    """
    基数排序
    时间复杂度：O(n*k)
    空间复杂度：O(n+k)
    简介：
        1 找到元素中最大值，并得到其位数k
        2 分0-9十个桶，
        3 对列表中元素的个位进行分桶排序
        4 对列表中元素的十位进行分桶排序
        5 重复操作，直到k位
    """

    def sort(self, li):
        """
        基数排序
        :param li:
        :return:
        """
        max_num = max(li)
        it = 0
        while 10 ** it <= max_num:
            buckets = [[] for _ in range(10)]
            for var in li:  # 分桶
                digit = (var // 10 ** it) % 10
                buckets[digit].append(var)
            li.clear()
            for buc in buckets:  # 把分桶后的元素重新写回li
                li.extend(buc)
            it += 1
        return li