所有常见排序算法的python实现

# @Author: feiyun
# @Date: 2020-05-01
# 快排递归
def quick_sort_r(nums):
    if len(nums) < 2:
        return nums
    else:
        p = nums[0]
        left = [i for i in nums[1:] if i <= p]
        right = [i for i in nums[1:] if i > p]
        return quick_sort_r(left) + [p] + quick_sort_r(right)

# 快排非递归
def quick_sort(nums):
    if len(nums) < 2:
        return
    stack = []
    stack.append(len(nums) - 1)
    stack.append(0)
    while stack:
        left = stack.pop()
        right = stack.pop()
        l = left
        r = right
        p = nums[l]
        while l < r:
            while l < r and nums[r] >= p:
                r -= 1
            while l < r and nums[l] <= p:
                l += 1
            if l != r:
                nums[l], nums[r] = nums[r], nums[l]
        nums[left] = nums[l]
        nums[l] = p
        if left < l - 1:
            stack.append(l - 1)
            stack.append(left)
        if right > r + 1:
            stack.append(right)
            stack.append(r + 1)
    return nums

# 归并排序
def merge_sort(nums):
    def merge(ans, left, right):
        while left and right:
            if left[0] < right[0]:
                ans.append(left.pop(0))
            else:
                ans.append(right.pop(0))
        if left:
            ans += left
        if right:
            ans += right
        return ans
    ans = []
    n = len(nums)
    mid = n // 2
    if n < 2:
        return nums
    left = merge_sort(nums[:mid])
    right = merge_sort(nums[mid:])
    ans = merge(ans, left, right)
    return ans

# 非递归归并
def merge_sort_no_r(nums):
    def merge(nums, left, right, l):
        ans = []
        while left and right:
            if left[0] < right[0]:
                ans.append(left.pop(0))
            else:
                ans.append(right.pop(0))
        if left:
            ans += left
        if right:
            ans += right
        for num in ans:
            nums[l] = num
            l += 1
    n = len(nums)
    ans = []
    i = 1
    while i < n:
        l = 0
        mid = l + i - 1
        r = mid + i
        while r < n:
            merge(nums, nums[l:mid + 1], nums[mid + 1:r + 1], l)
            l = r + 1
            mid = l + i - 1
            r = mid + i
        if l < n and mid < n:
            merge(nums, nums[l:mid + 1], nums[mid + 1:], l)
        i += i
    return nums

# 冒泡排序
def bubble_sort(nums):
    n = len(nums)
    for i in range(n - 1):
        for j in range(n - i - 1):
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
    return nums

# 选择排序
def select_sort(nums):
    n = len(nums)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if nums[j] < nums[min_idx]:
                min_idx = j
        nums[i], nums[min_idx] = nums[min_idx], nums[i]
    return nums

# 插入排序
def insertion_sort(nums):
    for i, num in enumerate(nums):
        idx = i
        while idx > 0 and nums[idx - 1] > num:
            nums[idx] = nums[idx - 1]
            idx -= 1
        nums[idx] = num
    return nums 

# 堆排序
def heap_sort(nums):
    n = len(nums)
    first_parent = (n - 2) // 2
    # 递归堆调整
    def heapify(nums, i, n):
        c1 = i * 2 + 1
        c2 = i * 2 + 2
        if c2 >= n or c1 >= n:
            return
        max = i
        if c1 < n and nums[c1] > nums[max]:
            max = c1
        if c2 < n and nums[c2] > nums[max]:
            max = c2
        if max != i:
            nums[i], nums[max] = nums[max], nums[i]
            heapify(nums, max, n)
    # 非递归堆调整
    def heapify_no_r(nums, i, n):
        # c1 = i * 2 + 1
        # c2 = i * 2 + 2
        # while c1 < n and c2 < n:
        while i < n:
            c1 = i * 2 + 1
            c2 = i * 2 + 2
            max = i
            if c1 < n and nums[c1] > nums[max]:
                max = c1 
            if c2 < n and nums[c2] > nums[max]:
                max = c2
            if max != i:
                nums[i], nums[max] = nums[max], nums[i]
                i = max
            else:
                break
    while first_parent >= 0:
        # heapify(nums, first_parent, n)
        heapify_no_r(nums, first_parent, n)
        first_parent -= 1
    i = n - 1
    while i >= 0:
        nums[i], nums[0] = nums[0], nums[i]
        # heapify(nums, 0, i)
        heapify_no_r(nums, 0, i)
        i -= 1
    return nums
    
# 希尔排序
def shell_sort(nums):
    if not nums:
        return nums
    n = len(nums)
    if n < 2:
        return nums
    def insert_helper(nums, h, i):
        tmp = nums[i]
        idx = i
        while idx - h >= 0 and nums[idx - h] > tmp:
            nums[idx] = nums[idx - h]
            idx -= h
        nums[idx] = tmp
    h = n // 2
    while h > 0:
        for i in range(h, n):
            insert_helper(nums, h, i)
        h //= 2
    return nums
# 计数排序
def count_sort(nums):
    c = [0 for _ in range(len(nums))]
    for num in nums:
        c[num - 1] += 1
    ans = []
    for i, n in enumerate(c):
        ans.append([i] * n)
    return ans
if __name__ == '__main__':
    # nums = [3,6,7,2,4,9,1,5,8]
    nums = [2,1,5,4,3]
    # nums = [0,0,1,2,0,3]
    # nums = quick_sort(nums)
    # nums = merge_sort(nums)
    # nums = bubble_sort(nums)
    # nums = select_sort(nums)
    # nums = insertion_sort(nums)
    # nums = heap_sort(nums)
    # nums = shell_sort(nums)
    # nums = merge_sort_no_r(nums)
    # nums = count_sort(nums)
    nums = merge_sort(nums)
    print(nums)