各种排序算法及Python源代码

• • • • 排序算法
      • • 排序算法稳定性
        • 冒泡排序
        • • 源代码
        • 选择排序
        • • 源代码
        • 插入排序
        • • 源代码
        • 希尔排序
        • • 源代码
        • 快速排序

• 在满足排序规则的前提下，保持原有顺序即具备稳定性，不保持原有顺序即不具稳定性

具备稳定性，最坏时间复杂度=O(n^2)

def bubble_list(list):

    for i in range(len(list)):
        for k in range(len(list)-1-i):
            if list[k] > list[k+1]:
                list[k],list[k+1] = list[k+1],list[k]
        print(list,end="nn")  #看下每个泡泡的上升情况
    return list

print(bubble_list([232,1,54,3463,22,121232,-8,99]))

不具备稳定性（不具备吗？应该具备吧？）

def select (list):
    select_list =[]
    for j in range(len(list)):
        min = list[j]    #如果min用作下标，不用重新构建一个select_list素组，这样可以少一次迭代
        for i in range(j+1,len(list)):
            if list[i] < min:
                min,list[i] = list[i],min

        select_list.append(min)
        print(select_list)  #还是看看过程
    return select_list


select([-101,232,1,22,54,3463,22,121232,-8,99])

源代码包含在下面希尔排序中

具备稳定性，最坏时间复杂度=O(n^2)

不具备稳定性，最坏时间复杂度=O(n^2)。它的好处就是平均时间复杂度较小（它的最好情况甚至也不如插入排序）

def insert(list):
    for i in range(len(list)-1):
        for j in range(i,-1,-1):
            if list[j+1] < list[j]:
                list[j+1],list[j] = list[j],list[j+1]
            else:
                break
        print(list)  #仍然看过程
    return list

def shell(list):   #在插入排序基础上建立希尔排序
    gap = len(list)
    while gap//2 != 1 :
        gap = gap//2
        gap_list = [list[k] for k in range(0,len(list),gap) ]  #构建基于每个gap的小列表
        insert(gap_list)
    return list

print(insert([-101, 232, 1, 22, 54, 3463, 22, 121232, -8, 99,-1234]))

print(shell([-101, 232, 1, 22, 54, 3463, 22, 121232, -8, 99,344543,-2123,12]))

基本思路：使用两个游标（low和high），从列表的两端进行逼近（或者叫遍历）。从列表第一个元素开始查找正确位置，游标low（high）遇到比当前要确认位置的元素小（大）的元素，则继续遍历，否则停止，并交换low和high两个游标所指元素。这个过程一直进行，进行到low和high指向的元素一样的时候，则这个位置就是当前要确认位置的元素的正确位置，原有列表也被这个元素分割成两个列表，后面再按这个思路一直进行下去

思路改进：先用high（或者low）进行遍历，遇到小于待确认位置元素的元素的时候，把这个元素赋值给low，然后low游标开始遍历，直到找到比待确认位置元素大的元素，把这个值赋值给high，循此往复