python实现十大核心算法（桶排没实例）

# author：sevenduke
# 2019-06-11
# 一、交换排序
# 排序算法的温故：冒泡排序

def dubblesort(arr):
    for i in range(0, len(arr)-1):
        for j in range(0, len(arr) - 1 - i):
            if arr[j] > arr[j+1]:
                #Python的变量并不直接存储值，而只是引用一个内存地址，交换变量时，只是交换了引用的地址。
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr
if __name__ == "__main__":
    list = [1,5,3,45,2,34,46,100]
    print("List source is:", list)
    result = dubblesort(list)
    print("List source is:", result)

# author：sevenduke
# 2019-06-11
# 一、交换排序
# 排序算法的温故：快速排序

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:
        partitionInex = parttion(arr,left,right)
        quickSort(arr, left,partitionInex-1)
        quickSort(arr, partitionInex+1, right)
    return arr

def parttion(arr, left, right):
    pivot = left
    position = left + 1
    index = position
    while index <= right:
        if arr[index] < arr[pivot]:
            swap(arr,index,position)
            position += 1
        index += 1
    swap(arr,pivot,position-1)
    print("List source is:", arr)
    return position-1

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

if __name__ == "__main__":
    list = [2,42,53,23,34,290,2344,200,3500]
    print("List source is:",list)
    result = quickSort(list)
    print("List source is:", result)

# author：sevenduke
# 2019-06-11
# 二、选择类排序
# 排序算法的温故：选择排序

def selectSort(arr):
    for i in range(len(arr)-2):
        minIndex = i
        for j in range(i+1,len(arr)):
            if arr[minIndex] > arr[j]:
                minIndex = j
        if i != minIndex:
            swap(arr, i, minIndex)
    return arr

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

if __name__ == "__main__":
    list = [2, 42, 53, 23, 34, 290, 2344, 200, 3500]
    print("List source is:", list)
    result = selectSort(list)
    print("List source is:", result)

import math
# author：sevenduke
# 2019-06-11
# 二、选择类排序
# 排序算法的温故：堆排序
# 堆排序分为以下两种：
#1、大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
#2、小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

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

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

def heapify(arr, i):
    left = i*2+1
    right = i*2+2
    position = i
    if left < arrlen and arr[left] > arr[position]:
        position = left
    if right < arrlen and arr[right] > arr[position]:
        position = right
    if position != i:
        swap(arr,i,position)
        heapify(arr,position)

def heapSort(arr):
    global arrlen
    arrlen = len(arr)
    # 从大到小排序
    bulitMaxHeap(arr)
    # 变化为从小到大排序
    for i in range(len(arr)-1,-1,-1):
        swap(arr,0,i)
        # 将当前可取的最大值拿到末尾
        arrlen -= 1
        heapify(arr,0)
    return arr

if __name__ == '__main__':
    list = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]
    print("List source is:", list)
    result = heapSort(list)
    print("List sort is:", result)

# author：sevenduke
# 2019-06-11
# 三、插入类排序
# 排序算法的温故：插入排序

def insertSort(arr):
    for i in range(len(arr)):
        index = i
        for j in range(i,len(arr)):
            if arr[index] > arr[j]:
                index = j
        if(index != i):
            swap(arr, i, index)
    return  arr

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

if __name__ == "__main__":
    list = [2, 42, 53, 23, 34, 290, 2344, 200, 3500]
    print("List source is:", list)
    result = insertSort(list)
    print("List source is:", result)

import math
# author：sevenduke
# 2019-06-11
# 三、插入类排序
# 排序算法的温故：希尔排序

def shellSort(arr):
    incretment = 1
    while(incretment < len(arr)/3):
        incretment = incretment * 3 + 1
    while incretment > 0:
        for i in range(incretment, len(arr)):
            temp = arr[i]
            j = i - incretment
            while j >= 0 and arr[j] > temp:
                arr[j+incretment] = arr[j]
                j -= incretment
            arr[j+incretment] = temp
        #incretment = int((incretment-1)/3)
        incretment = math.floor(incretment/3)
    return arr

if __name__ == "__main__":
    list = [2, 42, 53, 23, 34, 290, 2344, 200, 3500]
    print("List source is:", list)
    result = shellSort(list)
    print("List source is:", result)

import math
# author：sevenduke
# 2019-06-11
# 四、归并类排序
# 排序算法的温故：归并排序

def mergeSort(arr):
    import math
    if len(arr) < 2:
        return arr
    midIndex = math.floor(len(arr)/2)
    left, right = arr[0:midIndex], arr[midIndex:]
    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__":
    list = [34,24,53,2,43,54,657,3435,2423,231]
    print("List source is:", list)
    result = mergeSort(list)
    print("List source is:", result)

import math
# author：sevenduke
# 2019-06-11
# 五、分布类类排序
# 排序算法的温故：计数排序
# 局限性：适用于有固定范围的排序
# 桶排序和计数排序本质一致，这里就不做介绍了

def countingSort(arr):
    arrlen = max(arr)+1
    result = [0]*arrlen
    sortIndex = 0
    # 将arr中的数据填入到result数组中
    for i in range(len(arr)):
        if not result[arr[i]]:
            result[arr[i]] = 0
        result[arr[i]] += 1

    # 将result数组中的数据写入到arr中
    for i in range(len(result)):
        while result[i] > 0:
            arr[sortIndex] = i
            sortIndex += 1
            result[i] -= 1
    return arr

if __name__ == "__main__":
    list = [2,42,5234,24,243,236,76,767,565,45]
    print("List source is:", list)
    result = countingSort(list)
    print("List source is:", result)

import math
# author：sevenduke
# 2019-06-11
# 五、分布类类排序
# 排序算法的温故：基数排序
# 局限性：适用于整数排序（推广到特定的浮点数，和字符串，以及日期）


def redixSort(arr):
    # 找到arr中的最大的位数
    maxNumber = max(arr)
    mN_len = len(str(maxNumber))
    index = 0
    while index < mN_len:
        # 初始化二维数组
        bucket_list = [[] for i in range(10)]
        for elem in arr:
            bucket_list[int(elem / (10**index) % 10)].append(elem)
        arr.clear()
        for elem in bucket_list:
            for num in elem:
                arr.append(num)
        index += 1
    return arr

if __name__ == "__main__":
    list = [2, 42, 53, 23, 34, 290, 2344, 200, 3500]
    print("List source is:", list)
    result = redixSort(list)
    print("List source is:", result)