一、插入排序：平均时间复杂度 O(n^2)，稳定的算法
思想：2轮遍历，逐个找到<=key的位置后方插入(升序)

class Solution:
    def InsertSort(self, arr):
        n = len(arr)
        for i in range(1,n) #从第2项开始往前比较
            key = arr[i]
            j = i - 1
            #j往前遍历，找到key>= arr[j]的位置+1插入key
            while j >= 0 and key < arr[j]:
                arr[j+1] = arr[j] #未找到时均往后挪一位
                j -= 1
           arr[j+1] = key #找到时插入，未找到时，j+1=i不变
       return arr     

二、选择排序：平均时间复杂度 O(n^2)，不稳定
思想：2轮遍历，每次从后序列中找到最小值交换

class Solution:
    def SelectSort(self, num):
        i, j = 0, 0
        k = 0
        for i in range(n-1):
            k = i
            Min_n = num[k]
            for j in range(i+1, n):
                if Min_n> num[j]:
                    k = j #记录最小值下标
                    Min_n = num[j]
           num[i], num[k] = num[k], num[i]        
        return num

三、冒泡排序：平均时间复杂度 O(n^2)，不稳定

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

四、快速排序：平均时间复杂度 O(nlogn)，不稳定
思想：选定中心轴值，小的放左边，大的放右边。递归左右子列表
左右指针滑动时，填坑法移动。

class Solution:
    def MySort(self, arr: list[int]) ->list[int]:
        # write code here
        def quick_sort(arr: list[int], left, right):
            if left >= right:
                return
            p, q = left, right
            pivot = arr[left]  #取左指针为轴值
            while(p<q):
                              #此处注意等号，否则相等的时候可能陷入死循环。
                while(p<q and arr[q]>=pivot):#右指针先移动，比轴值小时停止
                    q -= 1
                arr[p] = arr[q] #填坑法，将小值放置左指针位置，重合时重复赋值
                while(p<q and arr[p]<=pivot):
                    p += 1
                arr[q] = arr[p] #将大值放置右指针位置
            arr[p] = pivot #将轴值放置重合位置
            quick_sort(arr, left, p-1)
            quick_sort(arr, p+1, right)
            return arr
        if len(arr) < 2:
            return arr
        return quick_sort(arr, 0, len(arr)-1)


if __name__ == "__main__":
    x = Solution()
    #arr = [2, 4, 1, 3, 5]
    print(x.MySort([1, 2, 3, 4, 5]))

*当数组逆序，且轴值为第一位时，时间复杂度退化成o（n^2）

五、堆排序：平均时间复杂度 O(nlogn)，不稳定
堆的定义：1、完全二叉树；2、父节点值均大于子节点值（大根堆，小根堆反之）
构造堆，取堆顶值。递归实现
排序思想：在堆的基础上，迭代取堆顶值，再构造堆

def heapify(arr, n, i): #第i点构造，在第n点前。
    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. 先建立大堆。叶子节点无孩子节点比较
    # 自底而上，堆顶在arr[0]
    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) #每次前i个，从堆顶再重新构造。