python中8大排序（原理+代码）

枫铃4年前 (2021-07-10)Python237

常用的排序方法：冒泡排序、选择排序、插入排序、快速排序、堆排序、归并排序

冒泡排序(Bubble Sort)：

比较相邻的元素。如果第一个比第二个大（升序），就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤,除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较

def bubble_sort(alist):
    n = len(alist)
    for i in range(n-1):   
        for j in range(n-1-i):
            if alist[j] > alist[j+1]:
                alist[j],alist[j+1] = alist[j+1],alist[j]
if __name__ == '__main__':
    alist = [1,2,4,9,5,6,8]
    bubble_sort(alist)
    print(alist)
最优时间复杂度：O(n) 
最坏时间复杂度：O(n2)
空间复杂度：o(1)
稳定性：稳定

选择排序(Selection sort)：

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
然后，再从剩余未排序元素中继续寻找最小（大）元素，
然后放到已排序序列的末尾。
以此类推，直到所有元素均排序完毕。

'''
遇到问题没人解答？小编创建了一个Python学习交流QQ群：857662006 
寻找有志同道合的小伙伴，互帮互助,群里还有不错的视频学习教程和PDF电子书！
'''
def select_sort(alist):
    n = len(alist)
    for i in range(n-1):
        min_index = i
        for j in range(i+1,n): # 遍历无序序列
            # 判断当前数值是否小于最小值，如果小于，则记录其索引
            if alist[j] < alist[min_index]:
                min_index = j
        # 判断min_index索引是否相同,不相同，做数值交换
        if i != min_index:
            alist[i],alist[min_index] = alist[min_index],alist[i]
if __name__ == '__main__':
    alist = [12,34,56,78,90,87,65,43,21]
    select_sort(alist)
    print(alist)
最优时间复杂度：O(n*log2n)
最坏时间复杂度：O(n2)
空间复杂度：O(log2n)~o(n)
稳定性：不稳定

插入排序：

开始假定列表里下标为0的元素是最小，在后面还未排序的数据里依次选取数据在前面有序区域里做比较并放在正确的位置，就像我们在玩扑克牌的时候依次把扑克牌有顺序的拜访

import random
def insert_sort(li):
    for i in range(1, len(li)):
        tmp = li[i]     #tmp是无序区取出的一个数
        j = i - 1       #li[j]是有序区最大的那个数
        while j >= 0 and li[j] > tmp:
         # li[j]是有序区最大的数，tmp是无序区取出的一个数，tmp从有序区最大的那个数开始比
         # 小就调换位置，直到找到有序区中值不大于tmp的结束
            li[j+1]=li[j]    #将有序区最右边的数向右移一个位置
            j = j - 1
        li[j + 1] = tmp       #将tmp放到以前有序区最大数的位置，再依次与前一个数比较
data = list(range(100))
random.shuffle(data)        #将有序列表打乱
insert_sort(data)
print(data)
时间复杂度：o(n2)
空间复杂度：o(1)
稳定性：稳定

快速排序：

随机选取一个值，挨个跟后面的数值作比较，比该数值小的将放在左列表中，反之则放在右列表，返回形式为：左列表+[随机值]+右列表，左右列表使用递归的方式继续进行排序。

'''
遇到问题没人解答？小编创建了一个Python学习交流QQ群：857662006 
寻找有志同道合的小伙伴，互帮互助,群里还有不错的视频学习教程和PDF电子书！
'''
def quick(list):
    if len(list) < 2:
        return list
    tmp = list[0]  # 临时变量 可以取随机值
    left = [x for x in list[1:] if x <= tmp]  # 左列表
    right = [x for x in list[1:] if x > tmp]  # 右列表
    return quick(left) + [tmp] + quick(right)

li = [4,3,7,5,8,2]
print(quick(li))

时间复杂度：O(nlog₂n)
空间复杂度：O(nlog₂n)
稳定性：不稳定