排序算法的代码实现（python）

1. 冒泡排序

def bubbleSort(arr):
    for i in range(1,len(arr)):
        for j in range(len(arr)-1):
            if arr[j]>arr[j+1]:
                arr[j],arr[j+1]=arr[j+1],arr[j]
        print('第'+str(i)+'趟的排序结果为:',arr)
    return arr



if __name__ == '__main__':
    arr=[10, 12, 1, 11, 14, 15, 1, 6]
    print('待排序列表为:',arr)
    bubbleSort(arr)
    print('冒泡排序后的结果为:',arr)

2. 选择排序

def selectSort(arr):
    for i in range(len(arr)-1):
        # 记录最小索引
        minIndex=i
        for j in range(i+1,len(arr)):
            if arr[j]<arr[minIndex]:
                minIndex=j
        if i != minIndex:
            arr[i],arr[minIndex]=arr[minIndex],arr[i]
        print('第'+str(i+1)+'趟的排序结果为:',arr)
    return arr

if __name__ == '__main__':
    arr=[10, 12, 1, 11, 14, 15, 1, 6]
    print('待排序列表为:',arr)
    selectSort(arr)
    print('选择排序后的结果为:',arr)

3. 插入排序

def insertSort(arr):
    for i in range(len(arr)):
        preIndex=i-1
        current=arr[i]
        while preIndex >= 0 and arr[preIndex] > current:
            arr[preIndex+1]=arr[preIndex]
            preIndex -= 1
        arr[preIndex + 1] = current
        print('第'+str(i+1)+'趟的排序结果为:',arr)
    return arr

if __name__ == '__main__':
    arr=[10, 12, 1, 11, 14, 15, 1, 6]
    print('待排序列表为:',arr)
    insertSort(arr)
    print('插入排序后的结果为:',arr)

4. 希尔排序

'''
直接插入的升级版，先基本拍有序，再直接插入，不稳定
'''
def shellSort(arr):
    import math
    gap=1
    while (gap < len(arr)/3):
        gap=gap*3+1
    while gap > 0:
        for i in range(gap,len(arr)):
            temp = arr[i]
            j = i - gap
            while j >= 0 and arr[j] > temp:
                arr[j+gap] = arr[j]
                j -= gap
            arr[j + gap] = temp
        gap = math.floor(gap/3)

    return arr


if __name__ == '__main__':
    arr = [10, 12, 1, 11, 14, 15, 1, 6]
    print('待排序列表为:', arr)
    shellSort(arr)
    print('希尔排序后的结果为:', arr)

5. 归并排序

def mergeSort(arr):
    import math
    if(len(arr)<2):
        return arr
    middle = math.floor(len(arr)/2)
    left, right = arr[0:middle], arr[middle:]
    return merge(mergeSort(left), mergeSort(right))

def merge(left,right):
    result = []
    while left and right:
        if left[0] <= right[0]:
            result.append(left.pop(0));
        else:
            result.append(right.pop(0));
    while left:
        result.append(left.pop(0));
    while right:
        result.append(right.pop(0));
    return result



if __name__ == '__main__':
    arr = [10, 12, 1, 11, 14, 15, 1, 6]
    print('待排序列表为:', arr)
    mergeSort(arr)
    print('归并排序后的结果为:', arr)

6. 快排

'''
从数列中挑出一个元素，称为 “基准”（pivot）;

重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

'''
def quickSort(arr, left=None, right=None):
    left = 0 if not isinstance(left,(int, float)) else left
    right = len(arr)-1 if not isinstance(right,(int, float)) else right
    if left < right:
        partitionIndex = partition(arr, left, right)
        quickSort(arr, left, partitionIndex-1)
        quickSort(arr, partitionIndex+1, right)
    return arr

def partition(arr, left, right):
    pivot = left
    index = pivot+1
    i = index
    while  i <= right:
        if arr[i] < arr[pivot]:
            swap(arr, i, index)
            index+=1
        i+=1
    swap(arr,pivot,index-1)
    return index-1

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]



if __name__ == '__main__':
    arr = [10, 12, 1, 11, 14, 15, 1, 6]
    print('待排序列表为:', arr)
    quickSort(arr)
    print('快排后的结果为:', arr)

7. 堆

'''
创建一个堆 H[0……n-1]；

把堆首（最大值）和堆尾互换；

把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；

重复步骤 2，直到堆的尺寸为 1。

'''
def buildMaxHeap(arr):
    import math
    for i in range(math.floor(len(arr)/2),-1,-1):
        heapify(arr,i)

def heapify(arr, i):
    left = 2*i+1
    right = 2*i+2
    largest = i
    if left < arrLen and arr[left] > arr[largest]:
        largest = left
    if right < arrLen and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        swap(arr, i, largest)
        heapify(arr, largest)

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

def heapSort(arr):
    global arrLen
    arrLen = len(arr)
    buildMaxHeap(arr)
    for i in range(len(arr)-1,0,-1):
        swap(arr,0,i)
        arrLen -=1
        heapify(arr, 0)
    return arr


if __name__ == '__main__':
    arr = [10, 12, 1, 11, 14, 15, 1, 6]
    print('待排序列表为:', arr)
    heapSort(arr)
    print('冒泡排序后的结果为:', arr)

8. 计数

def countingSort(arr, maxValue):
    bucketLen = maxValue+1
    bucket = [0]*bucketLen
    sortedIndex =0
    arrLen = len(arr)
    for i in range(arrLen):
        if not bucket[arr[i]]:
            bucket[arr[i]]=0
        bucket[arr[i]]+=1
    for j in range(bucketLen):
        while bucket[j]>0:
            arr[sortedIndex] = j
            sortedIndex+=1
            bucket[j]-=1
    return arr


if __name__ == '__main__':
    arr = [10, 12, 1, 11, 14, 15, 1, 6]
    print('待排序列表为:', arr)
    countingSort(arr,15)
    print('计数排序后的结果为:', arr)