六种排序方法的Python实现

#1、冒泡排序从小到大
def bubbleSort(alist):
    n = len(alist)-1
    for i in range(n):
        for j in range(n-i):
            if alist[j] > alist[j+1]:
                alist[j],alist[j+1] = alist[j+1],alist[j]
    return alist

#2、选择排序从小到大
def selectSort(alist):
    n = len(alist)
    for i in range(n-1):
        min = i
        for j in range(i+1,n):
            if alist[j] < alist[min]:
                min = j
        if min !=i:
            alist[i],alist[min] = alist[min],alist[i]
    return alist

#3、插入排序从小到大
def insertSort(alist):
    n = len(alist)
    for i in range(1,n):
        for j in range(i,0,-1):
            if alist[j] < alist[j-1]:
                alist[j],alist[j-1] = alist[j-1],alist[j]

    return alist

#4、快速排序从小到大
def quickSort(alist,start,end):
    if start >= end:
        return
    low = start
    high = end
    mid = alist[start]
    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

    quickSort(alist,start,low-1)
    quickSort(alist,low+1,end)

#5、希尔排序从小到大
def shellSort(alist):
    n = len(alist)
    gap = n // 2
    while gap > 0:
        for i in range(gap,n):
            j = i
            while j>=gap and alist[j] < alist[j-gap]:
                alist[j],alist[j-gap] = alist[j-gap],alist[j]
                j -= 1
        gap = gap // 2

#6、归并排序从小到大
def mergeSort(alist):
    if len(alist) <=1:
        return alist
    num = len(alist)//2
    left = mergeSort(alist[:num])
    right = mergeSort(alist[num:])
    return merge(left,right)

def merge(left,right):
    l,r = 0,0
    result = []
    while l<len(left) and r<len(right):
        if left[l]<right[r]:
            result.append(left[l])
            l+=1
        else:
            result.append(right[r])
            r+=1
    result+=left[l:]
    result+=right[r:]
    return result