本文共 2839 字，大约阅读时间需要 9 分钟。

• 插入排序：直接插入、希尔排序
• 选择排序：简单选择排序、堆排序
• 交换排序：冒泡排序、快速排序
• 基数排序
• 归并排序

不稳定排序：快速排序、希尔排序、选择排序、堆排序。

1、直接插入排序

平均时间复杂度：O(n^2)；最好情况：O(n)；最坏情况：O(n^2)

空间复杂度：O(1)

稳定

# 1.直接插入排序'''将数组分成有序和无序两部分，每次将无序序列中的第一个元素插入到有序序列中的合适位置。'''def insertSort(L):    for i in range(1,len(L)):       # 无序        for j in range(i-1,-1,-1):  # 从右向左查询有序序列            if L[j+1]

2、选择排序

平均时间复杂度：O(n^2)；最好情况：O(n^2)；最坏情况：O(n^2)

空间复杂度：O(1)

不稳定

# 2.选择排序'''将数组分成有序和无序两部分，每次选择无序序列中的最小元素放到有序序列的末尾。'''def selectSort(L):    minNum = 0      # 无序序列中的最小元素    temp = 0    for i in range(len(L)):        minNum = L[i]        for j in range(i+1,len(L)):     # 在无序序列中查找最小元素            if L[j]

3、优化后的冒泡排序

平均时间复杂度：O(n^2)；最好情况：O(n)；最坏情况：O(n^2)

空间复杂度：O(1)

稳定

# 3.优化后的冒泡排序'''两两比较元素并查看是否交换，每一趟结束后都有一个元素到达最终的位置。如果有一趟元素不需要交换，则说明数组有序，排序结束。'''def bubbleSort(L):    for i in range(len(L)):        flag = False        for j in range(len(L)-i-1):            if L[j]>L[j+1]:                L[j],L[j+1] = L[j+1],L[j]   #交换                flag = True        if not flag:    # 没有交换，已经有序            return L    return L

4、归并排序

平均时间复杂度：O(nlogn)；最好情况：O(nlogn)；最坏情况：O(nlogn)

空间复杂度：O(n)

稳定

''' 4.归并排序：分治法    把长度为n的输入序列分成长度 n/2的子序列；    对两个子序列分别采用归并排序；    将两个合并好的子序列归并成最终的序列'''def merge(L):    if len(L) <= 1:        return L    mid = len(L)//2    left = merge(L[:mid])    right = merge(L[mid:])    return mergesort(left,right)# 合并两个已排好序的数组def mergesort(left,right):    res = []    i,j=0,0    while i
   
    left[i]:            res.append(left[i])            i+=1        else:            res.append(right[j])            j+=1    # if j == len(right):    #     for c in left[i:]:    #         res.append(c)    # else:    #     for c in right[j:]:    #         res.append(c)    res += left[i:]    res += right[j:]    return res
   

5、快速排序

平均时间复杂度：O(nlogn)；最好情况：O(nlogn)；最坏情况：O(n^2)

空间复杂度：O(logn)

不稳定

# 快速排序'''选择一个元素作为基准，将比基准值小的元素放到基准值之前，比基准值大的元素放到基准值之后递归的对基准值前后的两个分区进行快速排序'''def quickSort(L,low,high):    if low>=high:        return    pivot = L[low]    i,j=low,high    while i < j:        while L[j]>=pivot and i

6、堆排序

平均时间复杂度：O(nlogn)

空间复杂度：O(1)

不稳定

# 6.堆排序'''1.将无序数组建立二叉堆，升序选择大顶堆2.将堆顶元素与末尾元素交换3.调整堆使其满足大顶堆，然后继续交换堆顶元素与当前末尾元素，继续调整，直到整个数组有序为止'''def heapsort(ls):    # 建堆（大顶堆）从第一个非叶子结点从下至上，从右至左调整结构    for i in range(len(ls) // 2 - 1, -1, -1):        adjust(ls, i, len(ls))    # 调整堆+交换    for j in range(len(ls) - 1, 0, -1):        # 交换堆顶元素与末尾元素，然后调整堆        ls[j], ls[0] = ls[0], ls[j]        adjust(ls, 0, j)# 调整堆def adjust(ls, i, length):    temp = ls[i]    # 取出当前元素    k = 2 * i + 1    for k in range(2 * i + 1, length, 2 * k + 1):   # 从i节点的左子节点开始        if k + 1 < length and ls[k] < ls[k + 1]:    # 如果左子节点小于右子节点，k指向较大者            k += 1        if ls[k] > temp:    # 如果较大的子节点大于父节点，把子节点赋值给父节点            ls[i] = ls[k]            i = k        else:   # # 如果较大的子节点小于父节点，则不用调整，退出循环            break    ls[i] = temp    # 将当前元素temp放到合适位置

转载地址：http://lrjui.baihongyu.com/