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

def quickSort(arr,low,high):
if low < high:
pi = partition(arr, low, high)
quickSort(arr, low, pi-1)
quickSort(arr, pi+1, high)
n = len(arr)
quickSort(arr, 0, n-1)

5. 归并排序

class Solution:
    def merge_sort(arr):
        if len(arr) == 1: return arr
        mid = len(arr) // 2
        left = arr[:mid]        right = arr[mid:]        return marge(merge_sort(left), merge_sort(right))
    def marge(left, right):
        res = []        while len(left) > 0 and len(right) > 0:
        # 左右两个数列第一个最小放前面
            if left[0] <= right[0]:
                res.append(left.pop(0))
            else:
                res.append(right.pop(0))
        # 只有一个数列中还有值，直接添加
        res += left
        res += right
        return res

6. 桶排序

牺牲空间

class Solution:
    def bucket_sort(s):
        min_num = min(s)
        max_num = max(s)
        # 桶的大小
        bucket_range = (max_num-min_num) / len(s)
        # 桶数组
        count_list = [ [] for i in range(len(s) + 1)]        # 向桶数组填数
        for i in s:
            count_list[int((i-min_num)//bucket_range)].append(i)
        s.clear()
        # 回填，这里桶内部排序直接调用了sorted
        for i in count_list:
            for j in sorted(i):
            s.append(j)

7. 计数排序

当数值中有非整数时，计数数组的索引无法分配

class Solution:
    def count_sort(s):
        # 找到最大最小值
        min_num = min(s)
        max_num = max(s)
        # 计数列表
        count_list = [0]*(max_num-min_num+1)
        # 计数
        for i in s:
            count_list[i-min_num] += 1
        s.clear()
        # 填回
        for ind,i in enumerate(count_list):
            while i != 0:
            s.append(ind+min_num)
            i -= 1

8. 希尔排序

减小增量排序

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录”基本有序”时，再对全体记录进行依次直接插入排序。

class solution:
    def shell_sort(s):
        b = len(s)                         #列表长度
        gap = b // 2                       #初始步长设置为总长度的一半
 2/3   首页 上一页 1 2 3 下一页 尾页