十大排序算法Python实现-LeetCode题解（全面精简附解释）

while gap >= 1:
for i in range (b):
j = i
while j >= gap and s[j-gap] > s[j]: #在每一组里面进行直接插入排序
s[j], s[j-gap] = s[j-gap], s[j] j-= gap
gap = gap//2 #更新步长

9. 堆排序

class Solution:
    def heapify(arr, n, i):
        largest = i
        l = 2 * i + 1     # left = 2*i + 1
        r = 2 * i + 2     # right = 2*i + 2 
        if l < n and arr[i] < arr[l]:
            largest = l 
        if r < n and arr[largest] < arr[r]:
            largest = r 
        if largest != i:
            arr[i],arr[largest] = arr[largest],arr[i]  # 交换
            heapify(arr, n, largest) 
    def heapSort(arr):
        n = len(arr) 
        # Build a maxheap.
        for i in range(n, -1, -1):
            heapify(arr, n, i) 
        # 一个个交换元素
        for i in range(n-1, 0, -1):
            arr[i], arr[0] = arr[0], arr[i]   # 交换
            heapify(arr, i, 0) 

10. 基数排序

class Solution:
    def radix_sort(s):
        """基数排序"""
        i = 0 # 记录当前正在排拿一位，最低位为1
        max_num = max(s)  # 最大值
        j = len(str(max_num))  # 记录最大值的位数
        while i < j:
            bucket_list =[[] for _ in range(10)] #初始化桶数组
            for x in s:
                bucket_list[int(x / (10**i)) % 10].append(x) # 找到位置放入桶数组
            s.clear()
            for x in bucket_list:   # 放回原序列
                for y in x:
                    s.append(y)
            i += 1

注：部分排序方法，LeetCode提交代码会超时

码字不易，学习小白，如有不对，欢迎留言批评交流~

觉得不错，辛苦您点个赞，观个注~~~~~~~~

作者：算法之美DL

 3/3   首页 上一页 1 2 3