5种排序算法的实现（python）

包括冒泡排序、选择排序、插入排序、快速排序和归并排序。前三者的时间复杂度为O（n*n）,后两者的时间复杂度为O（nlogn），两者的基本思想都是分治和递归。

1. 冒泡排序

def buble_sort(nums):
    n=len(nums)
    for i in range(n):
        ## j的边界值需要满足，j+1<n-1.range(n-1)无法取到最后一个值
        for j in range(0,n-i-1):
            if nums[j]>nums[j+1]:
                nums[j],nums[j+1]=nums[j+1],nums[j]

    return nums

2. 选择排序。选择一个元素，判断是否是最小的元素。

https://www.runoob.com/python3/python-selection-sort.html

def select_sort(nums):
    n=len(nums)
    for i in range(n):
        min_index=i
        for j in range(i+1,n):
            if nums[j]<nums[min_index]:
                min_index=j
        ## 只有当位置发生改变时，才交换
        if min_index != i:
            nums[i],nums[min_index]=nums[min_index],nums[i]

    return nums

3. 插入排序。将当前元素插入到已排序的序列的正确的位置

https://www.runoob.com/python3/python-insertion-sort.html

def insert_sort(nums):
    n=len(nums)
    for i in range(1,n):
        j=i
        ## 若当前元素小于该元素之前的所有元素，先保存当前元素的值，再将其之前的元素逐一后移，最后将该元素放到合适的位置
        while j>0:
            if nums[j-1]>nums[j]:
                nums[j-1],nums[j]=nums[j],nums[j-1]
            j -= 1

    return nums

## 以下方法较上述方法，交换方式略微不同
def insert_sort2(nums):
    n=len(nums)
    for i in range(1,n):
        key=nums[i]
        j=i-1
        ## 若当前元素小于该元素之前的所有元素，先保存当前元素的值，再将其之前的元素逐一后移，最后将该元素放到合适的位置
        while j>=0 and nums[j]>key:
            nums[j+1] = nums[j] ## 后移一位
            j -= 1
        nums[j+1] = key ## 将元素放到正确的位置.注意是j+1

    return nums

4. 快速排序。分治和递归的思想结合。时间复杂度是nlogn。

https://blog.csdn.net/weixin_43250623/article/details/88931925

def quick_sort(nums,start,end):
    if start >= end: ## 相等，退出递归
        return
    low,high=start,end
    ```
    中间元素的选取，影响后面比较的顺序。
    当mid=nums[low]时，则应先从右往左比较，再从左往右比较。
    目的是保证nums[low] 能被替换为正确的元素。如果比较顺序相反，则不能得到正确的结果。
    ```
    mid=nums[low]
    ## 比mid 元素大的放到右边，比mid元素小的放到左边
    while low<high :
        while low < high and nums[high]>=mid:
            high -= 1
        nums[low]=nums[high]

        while low < high and nums[low]<mid:
            low += 1
        nums[high]=nums[low]

    nums[low] = mid

    ## 从基准元素的靠左一位开始递归。此处也不必再比较中间元素mid，因为它已经放到了正确的位置
    quick_sort(nums,start,low-1) 
    quick_sort(nums,low+1,end)

5. 归并排序。也是分治和递归思想的结合，时间复杂度也是nlogn，但是比快排算法需要更多的空间，因为需要另外开辟一个数组。

https://blog.csdn.net/qq_36813467/article/details/88848415

def merge_sort(alist):
    if len(alist)<=1:
        return alist

    mid=len(alist)//2
    left=merge_sort(alist[:mid])
    right=merge_sort(alist[mid:])

    return merge(left,right)

## 需要另开一个列表存储已排序的序列
def merge(left,right):
    l,r=0,0
    s=[]
    while l<len(left) and r<len(right):
        if left[l] < right[r]:
            s.append(left[l])
            l += 1
        else:
            s.append(right[r])
            r += 1

    ## 将一个列表合并到已有列表，应当使用extend（比+代价更小）。append只是增加一个元素。
    s.extend(left[l:]) if l<len(left)
    s.extend(right[r:]) if r<len(right)

    return s

测试用例：

if __name__ == '__main__':
    alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    
    print(buble_sort(alist))

---

参考：
https://blog.csdn.net/weixin_41624982/article/details/89486592