用python实现各种排序

从简单到复杂大致排序

1. 内置排序函数（不要太简单好吗）

nums.sort()  # 原地排序，不反回
sorted(nums) # 返回排序后的数组

2. 冒泡排序（排序的helloword）

def bubbleSort(nums):
    for i in range(len(nums))[::-1]:
        for j in range(i+1, len(nums)):
            if nums[j] < nums[j-1]:
                nums[j], nums[j-1] = nums[j-1], nums[j]

3.插入排序（静静躺着，期待下面大佬的表演）

def insertSort(nums):
    snums = []
    for i, num in enumerate(nums):
        j = i
        while j - 1 >= 0 and snums[j-1] > num:
            j -= 1
        snums.insert(j, num)
    return snums

4.归并排序（用上递归了！）

def mergeSort(nums):
    if len(nums) < 2:
        return nums
    mid = len(nums)//2
    l = mergeSort(nums[:mid])
    r = mergeSort(nums[mid:])
    for i in range(len(nums)):
        if not r or l[0] < r[0]:
            nums[i] = l.pop(0)
        else:
            nums[i] = r.pop(0)
    return nums

5.shell排序（插入排序？Nope）

def shellSort(nums):
    gap = len(nums)//2
    while gap:
        for i in range(gap, len(nums)):
            b = nums[i]
            j = i
            while j >= gap and nums[j-gap] > b:
                nums[j] = nums[j-gap]
                j -= gap
            nums[j] = b
        gap = gap // 2
    return nums

6.快速排序（我可有点难理解哟）

def quickSort(nums):
    def rsort(lo, hi):
        if lo >= hi:
            return
        i = lo
        for j in range(lo, hi):
            if nums[j] < nums[hi]:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
        nums[i], nums[hi] = nums[hi], nums[i]
        rsort(lo, i-1)
        rsort(i+1, hi)
    rsort(0, len(nums-1))