手撕代码必会排序算法（冒泡、快排、堆排）

一、冒泡排序

1、基础版

def bubble_Sort(arr):
    n = len(arr)
    for i in range(n-1):
        for j in range(n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

2、改进版

加入Flag，若剩余的都已经是有序的则无需继续

def super_bubble_Sort(arr):
    n = len(arr)
    for i in range(n-1):
        Flag = False
        for j in range(n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                Flag = True
        if not Flag: break

二、快排

1、方法一

思路及其简单，实现也及其简单，但是面试官往往想让你写的是方法二

def quick_Sort(nums):
    if len(nums) <= 1:
        return nums
    pivot = nums[0]
    left = [nums[i] for i in range(1, len(nums)) if nums[i]<pivot]
    right = [nums[i] for i in range(1, len(nums)) if nums[i]>=pivot]
    return quick_Sort(left) + [pivot] + quick_Sort(right)

2、方法二

import random

def partition(left, right, nums):
    rand_index = random.randint(left, right)
    nums[left], nums[rand_index] = nums[rand_index], nums[left]
    pivot, index = nums[left], left
    for i in range(left+1, right+1):
        if nums[i] < pivot:
            index += 1
            nums[i], nums[index] = nums[index], nums[i]
    nums[left], nums[index] = nums[index], nums[left]
    return index
    
def quick_Sort_Inter(left, right, nums):
    if left < right:
        index = partition(left, right, nums)
        quick_Sort_Inter(left, index-1, nums)
        quick_Sort_Inter(index+1, right, nums)

三、堆排

def heap_Sort(nums):
    #调整堆
    def Heapify(nums, i, size):
        #非叶子节点的左右两个孩子
        lchild = 2*i + 1
        rchild = 2*i + 2

        #在当前节点、左右孩子中找到最大元素的索引
        largest = i
        if lchild < size and nums[lchild] > nums[largest]:
            largest = lchild
        if rchild < size and nums[rchild] > nums[largest]:
            largest = rchild
        #如果最大元素的索引不是当前节点，把最大的节点交换到上面，继续调整堆
        if largest != i:
            nums[largest], nums[i] = nums[i], nums[largest]
            Heapify(nums, largest, size)

    #建立堆
    def build_Heap(nums, size):
        for i in range(len(nums)//2)[::-1]:
            Heapify(nums, i, size)

    size = len(nums)
    build_Heap(nums, size)
    for i in range(size)[::-1]:
        #每次根节点都是最大的数，最大数放在后面
        nums[0], nums[i] = nums[i], nums[0]
        #交换完后还需要继续调整堆，只需调整根节点，此时数组的size不包括已经排序好的数
        Heapify(nums, 0, i)
    return nums