稳定排序：归并排序、冒泡排序、插入排序、基数排序、桶排序
不稳定排序：选择排序、快速排序、堆排序、希尔排序

划分排序算法稳定与否的依据：排序前后两个相等的数相对位置不变，则算法稳定，否则不稳定。

1.冒泡排序

时间复杂度：O(n)

def bubble_sort(testlist):
    for i in range(len(testlist)-1):
        for j in range(0,len(testlist)-i-1):
            if testlist[j]>testlist[j+1]:
                testlist[j],testlist[j+1]=testlist[j+1],testlist[j]
    return testlist

优化后的冒泡排序

def improved_bubble_sort(testlist):
    for i in range(len(testlist)-1):
        flag=0
        for j in range(len(testlist)-1-i):
            if testlist[j]>testlist[j+1]:
                testlist[j],testlist[j+1]=testlist[j+1],testlist[j]
                flag+=1
            if flag==0:
                return testlist
    return testlist

2.选择排序

时间复杂度：O(n)

#Select_Sort
def select_sort(testlist):
    for i in range(len(testlist)-1):
        min_index=i
        for j in range(i+1,len(testlist)):
            if testlist[j]<testlist[min_index]:
                min_index=j
        testlist[i],testlist[j]=testlist[j],testlist[i]
    return testlist

3.插入排序

#Insert_Sort
def inserted_sort(testlist):
    for i in range(1,len(testlist)):
        while i>0:
            if testlist[i]<testlist[i-1]:
                testlist[i],testlist[i-1]=testlist[i-1],testlist[i]
                i-=1
            else:
                break
    return testlist

4.归并排序

#归并排序
#思路：
#1.对于当前数组，将当前数组分为两个子数组，并不断切分这两个子数组
#2.通过比较两个切分后子数组的每个元素的大小对两个子数组中的元素进行排序
#3.重复1-2步骤，直到子数组的长度为1为止
    def sortArray(self, nums: List[int]) -> List[int]:
        n=len(nums)
        if n<=1:
            return nums
        def merge(a,b):
            na,nb=len(a),len(b)
            i=j=0
            ans=[]
            while i<na and j<nb:
                if a[i]<=b[j]:
                    ans.append(a[i])
                    i+=1
                else:
                    ans.append(b[j])
                    j+=1
            if i<na:
                ans.extend(a[i:])
            if j<nb:
                ans.extend(b[j:])
            return ans
        mid=n//2
        left=self.sortArray(nums[:mid])
        right=self.sortArray(nums[mid:])
        return merge(left,right)

5.快速排序

算法思想：

1.对于当前的数组，随机选择一个元素当作基准数（这里我们选择第一个元素）
2.将所有比基准数小的元素排在基准数之前，比基准数大的元素排在基准数之后
3.当基准数被放到准确的位置后，根据基准数的位置将元素切分为前后两个数组
4.对子数组采用步骤1-4的递归操作，直到子数组的长度小于等于1为止

def quick_sort(testlist,start,end):
    if start<end:
        i,j=start,end
        base=testlist[i]
        while i<j:
            while i<j and testlist[j]>=base:
                j-=1
            testlist[i],testlist[j]=testlist[j],testlist[i]
            while i<j and testlist[i]<=base:
                i+=1
            testlist[i],testlist[j]=testlist[j],testlist[i]
        base=testlist[i]
        quick_sort(testlist,start,i-1)
        quick_sort(testlist,i+1,end)

6.桶排序

堆排序基本思想：

将待排序的序列构成一个大根堆，此时整个序列的最大值就是堆顶的根节点。将其与末尾节点进行交换，此时末尾就是最大值。
然后将剩余n-1个元素重新构造成一个大根堆，这样就会得到n个元素的次小值。如此反复执行，就可以得到一个有序序列。

def buckerSort(nums,bucketNum):
    if len(nums)<=1:
        return nums
    maxNum=nums[0]
    minNum=nums[0]
    #找到最大值和最小值
    for i in range(1,len(nums)):
        if nums[i]>maxNum:
            maxNum=nums[i]
        elif nums[i]<minNum:
            minNum=nums[i]
        else:
            continue
    bucketSize=(maxNum-minNum+1)//bucketNum#根据桶的数量找到每个桶的范围
    buckets=[[] for i in range(bucketNum)]
    for i in range(len(nums)):
        buckets[(nums[i]-minNum)//bucketSize].append(nums[i])
    for i in range(bucketNum):
        buckets[i].sort()
    res=[]
    for i in range(len(buckets)):
        for j in range(len(buckets[i])):
            res.append(buckets[i][j])
    return res

7.堆排序

def sift(list,root,end):
    while True:
        child=2*root+1#找到左孩子  
        if child>end:
            break
        if child+1<=end and list[child]<list[child+1]:
            child+1
        if list[root]<list[child]:
            list[root],list[child]=list[child],list[root]
            root=child
        else:
            break
#sift 可以调整任何一个点所组成的数 为大根堆

def head_sort(list):
    #第一次调整 为大根堆：从最后一个非叶子节点的index，一直倒着调到index
    first=len(list)//2-1
    for i in range(first,-1,-1):
        sift(list,i,len(list)-1)  #end = len(list-1) 判断左右节点是否超出范围
    #上面的for 可以实现  将原来的list调整为大根堆
    for j in range(len(list)-1,0,-1):
        list[j],list[0]=list[0],list[j]  #交换，  此时最大值为调整到最后
        sift(list,0,j-1)