Python排序方法

1.冒泡排序

#普通版
def  test_sort(alist):
    n = len(alist)
    for j in range(n-1,0,-1):
        for i in range(j):
            if alist[i] > alist[i+1]:
                alist[i], alist[i+1] = alist[i+1], alist[i] 

if __name__ == "__main__":
    li = [16,13,18,29,7,30,66,77,22,55,0,23,45,63]
    test_sort(li)
    print(li)

#改进版
def  test_sort(alist):
    n = len(alist)
    for j in range(n-1,0,-1):
        count = 0
        for i in range(j):
            if alist[i] > alist[i+1]:
                alist[i], alist[i+1] = alist[i+1], alist[i] 
                count +=1
        if 0 == count:
            return
#优化已经是排好顺序的，可以不用在排序。
if __name__ == "__main__":
    li = [16,13,18,29,7,30,66,77,22,55,0,23,45,63]
    test_sort(li)
    print(li)

2.选择排序

def  test_sort(alist):
    n = len(alist)
    for j in range(n-1):
        min_index = j
        for i in range(j+1, n):
            if alist[min_index] > alist[i]:  
                min_index = i
        alist[j], alist[min_index] = alist[min_index], alist[j] 
                
if __name__ == "__main__":
    li = [16,13,18,29,7,30,66,77,22,55,0,23,45,63]
    test_sort(li)
    print(li)

3.插入排序

def  test_sort(alist):
    n = len(alist)
    for j in range(1,n):
        #代表内层循环的起始值
        i = j
        #执行从右边的无序序列中取出第一个元素，既i位置的元素，然后插入到前面的位置
        while i > 0:
            if alist[i] < alist[i-1]:  
                alist[i], alist[i-1] = alist[i-1], alist[i]
                i -= 1
            else:
                break
                          
if __name__ == "__main__":
    li = [16,13,18,29,7,30,66,77,22,55,0,23,45,63]
    test_sort(li)
    print(li)

4.希尔排序

def  test_sort(alist):
    n = len(alist)
    gap = n//2
    #gap变成1的时候就是一个插入排序
    while gap > 0:
        for j in range(gap,n):
            i = j
            while i > 0:
                if alist[i] < alist[i-gap]:  
                    alist[i], alist[i-gap] = alist[i-gap], alist[i]
                    i -= 1
                else:
                    break
        #缩短步长
        gap //=2              
if __name__ == "__main__":
    li = [16,13,18,29,7,30,66,77,22,55,0,23,45,63]
    test_sort(li)
    print(li)

5.快速排序

def  test_sort(alist, start, end):
    #退出条件
    if start >= end:
        return
    #初始值
    mid = alist[start]
    #游标
    low = start
    high = end

    while low < high:
        while low < high and alist[high] >= mid:
            high -= 1
        alist[low] = alist[high]
        while low < high and alist[low] < mid:
            low += 1
        alist[high] = alist[low]

    #退出循环后程序结束后将基准元素放到该位置
    alist[low] = mid
    #对基准元素左右子序列分别进行快速排序
    test_sort(alist, start, low-1)
    test_sort(alist, low+1, end)


if __name__ == "__main__":
    li = [16,13,18,29,7,30,66,77,22,55,0,23,45,63]
    test_sort(li, 0, len(li)-1)
    print(li)

image.png