Python实现10大排序算法

Python实现10种排序算法。通过Java版改写，可能有句法不那么Python的问题。另外，第10个还没写出来，有空再补上。

Bubble Sort 冒泡排序

比较相邻的元素，如果第一个比第二个大，就交换他们。对每一对相邻元素做相同的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数。针对所有的元素重复以上的步骤，除了最后一个重复以上步骤，直到排序完成.

def bubble_sort(arr):
    for i in range(len(arr) - 1):
        for j in range(len(arr) - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    print(arr)
    return

list1 = [1, 23, 43, 2, 3, 54, 6, 34, 81, 99, 342, 3, 4452, 344, 234, 44, 55, 67, 57, 24, 723]
bubble_sort(list1)

Selection Sort 选择排序

首先从未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后从剩余未排序元素中继续寻找最小（大）元素，移动到已排序末尾。以此类推，直到所有元素均排序完毕

def selection_sort(arr):
    for i in range(len(arr) - 1):
        min_index = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

list1 = [1, 23, 43, 2, 3, 54, 6, 34, 81, 99, 342, 3, 4452, 344, 234, 44, 55, 67, 57, 24, 723]
print(selection_sort(list1))

Insertion Sort 插入排序

通过构建有序序列，对未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入

def insertion_sort(arr):
    for i in range(1, len(arr)):
        previous = i - 1
        current = arr[i]
        while previous >= 0 and arr[previous] > current:
            arr[previous + 1] = arr[previous]
            previous -= 1
        arr[previous+1] = current
    return arr

list1 = [1, 23, 43, 2, 3, 54, 6, 34, 81, 99, 342, 3, 4452, 344, 234, 44, 55, 67, 57,24, 723]
print(insertion_sort(list1))

Shell Sort 希尔排序

简单插入排序的改进版，它与插入排序不同之处在于，他会优先比较距离较远的元素希尔排序又叫“缩小增量排序”

def shell_sort(arr):
    gap = len(arr) // 2
    while gap > 0:
        for i in range(gap, len(arr)):
            while i - gap >= 0 and arr[i] < arr[i - gap]:
                arr[i], arr[i-gap] = arr[i - gap], arr[i]
                i -= gap
        gap = gap // 2
    return arr

list1 = [1, 23, 43, 2, 54, 6, 34, 81, 99, 342, 3, 4452, 344, 234, 44, 55, 67, 57, 24, 723]
print(shell_sort(list1))

Merge Sort 归并排序

将已有序的子序列合并，得到完整有序的序列；即先使每个子序列有序，再使子序列段间有序

def merge_sort(arr):
    if len(arr) < 2:
        return arr
    middle = len(arr) // 2
    left = merge_sort(arr[:middle])
    right = merge_sort(arr[middle:])
    return merge(left, right)

def merge(a, b):
    aux = []
    while len(a) > 0 and len(b) > 0:
        if a[0] <= b[0]:
            aux.append(a.pop(0))
        else:
            aux.append(b.pop(0))
    else:
        if len(a) == 0:
            aux += b
        else:
            aux += a
    return aux


list1 = [1, 23, 43, 2, 54, 6, 34, 81, 99, 342, 3, 4452, 344, 234, 44, 55, 67, 57, 24, 723]
print(merge_sort(list1))

Quick Sort 快速排序

在序列中选择一个基准点，然后分别从序列的两段扫描，设两个指示标志。从后半部分开始，如果有元素比该基准点小，就交换两个指示标志位置的值，然后从前半部分开始扫描，发现有元素大于基准点的值，就交换两个指示标志位置的值，如此往复循环，直到俩指示标志的前者与后者相当或前者大于后者，交换位置，一次排序完成了。以后采用递归的方式，分别对前半部分和后半部分排序

def quick_sort(arr):
    return q_sort(arr, 0, len(arr) - 1)

def q_sort(arr, lo, hi):
    if lo < hi:
        pivot = partition(arr, lo, hi)
        q_sort(arr, lo, pivot - 1)
        q_sort(arr, pivot + 1, hi)
    return arr

def partition(arr, lo, hi):
    pivot_value = arr[hi]
    i = lo - 1
    for j in range(lo, hi):
        if arr[j] <= pivot_value:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[hi] = arr[hi], arr[i + 1]
    return i + 1

list1 = [1, 23, 43, 2, 54, 6, 34, 81, 99, 342, 3, 4452, 344, 234, 44, 55, 67, 57, 24, 723]
print(quick_sort(list1))

def quick_sort(arr, lo, hi):
    if lo > hi:
        return
    stack = []
    stack.append(lo)
    stack.append(hi)
    while stack:
        lo = stack.pop(0)
        hi = stack.pop(0)
        if hi - lo <= 0:
            continue
        pivot = arr[hi]
        i = lo - 1
        for j in range(lo, hi):
            if arr[j] <= pivot:
                i += 1
                arr[i], arr[j] = arr[j], arr[i]
        arr[i + 1], arr[hi] = arr[hi], arr[i + 1]
        stack.extend([lo, i, i + 2, hi])

Heap Sort 堆排序

堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或大于）它的父节点。
将初始待排序关键字序列(R1,R2,R3,...Rn)构成一顶堆，此堆为初始的无序区：将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区（R1,R2,R3,...Rn-1）和新的有序区，且满足R[1,2,3,...,n-1] <= R[n]；由于交换后的新的堆顶R[1]可能违反堆的性质，因为需要对当前无序区（R1,R2,R3,...,Rn-1）调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区（R1,R2,R3,...,Rn-2）和新的有序区（Rn-1,Rn）
不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成

def heapify(arr, i, k):
    # 构建堆的规则
    j = 2 * i
    while j <= k:
        if j < k and arr[j] < arr[j + 1]:
            j += 1
        if arr[i] >= arr[j]:
            break
        arr[i], arr[j] = arr[j], arr[i]
        i = j
        j *= 2

def heap_sort(arr):
    # 从最后一个有子节点的节点开始构建堆
    last = len(arr) // 2 - 1
    for i in range(last, -1, -1):
        heapify(arr, i, len(arr) - 1)

    # 将最大的数放在堆的最后一个位置，并将剩余部分重新构建堆
    for k in range(len(arr) - 1, 0, -1):
        arr[0], arr[k] = arr[k], arr[0]
        heapify(arr, 0, k - 1)

if __name__ == "__main__":
    arr = [1, 23, 43, 2, 54, 6, 34, 81, 99, 342, 3, 4452, 344, 234, 44, 55, 67, 57, 24, 723]
    heap_sort(arr)
    print(arr)

list1 = [1, 23, 43, 2, 54, 6, 34, 81, 99, 342, 3, 4452, 344, 234, 44, 55, 67, 57, 24, 723]

Counting Sort 计数排序

计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。
作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数，找出待排序的数组中最大和最小的元素；统计数组中每个值为i的元素出现的个数，存入数组C的第i项；对所有的计数累加，反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

def counting_sort(arr, largest):
    bucket = [0]*(largest + 1)
        sorted_index = 0

    for i in range(len(arr)):
        bucket[arr[i]] = arr.count(arr[i])

    for j in range(len(bucket)):
        while bucket[j] > 0:
            arr[sorted_index] = j
            sorted_index += 1
            bucket[j] -= 1
   return arr

list1 = [1, 23, 43, 2, 24, 54, 6, 34, 81, 99, 342, 3, 4452, 344, 234, 44, 55, 67, 57, 24, 723]
print(counting_sort(list1, 4452))

Bucket Sort 桶排序

桶排序是计数排序的升级版。它利用函数的映射关系，高效与否的关键在于这个映射函数的确定，假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶分别排序。每个桶里的排序，有可能再使用比的排序算法，或是以递归方式继续使用桶排序

设置一个定量的数组当做空桶
遍历输入数据，并且把数据一个一个放到对应的桶里
对每个不是空的桶进行排序
从不是空的桶里把排好序的数据拼接起来

def bucket_sort(arr, bucket_size):
    if len(arr) == 0:
        return arr

    min_value = arr[0]
    max_value = arr[0]
    for i in range(len(arr)):
        if arr[i] < min_value:
            min_value = arr[i]
        if arr[i] > max_value:
            max_value = arr[i]

    # bucket_size = 5
    bucket_count = (max_value - min_value) // bucket_size + 1
    buckets = [[]*i for i in range(bucket_count)]

    for i in range(len(arr)):
        buckets[(arr[i] - min_value) // bucket_size].append(arr[i])
    # print(buckets)

    arr = []
    for i in range(len(buckets)):
        insertion_sort(buckets[i])
        for j in range(len(buckets[i])):
            arr.append(buckets[i][j])

    # print(buckets)

    return arr


list1 = [1, 23, 43, 2, 24, 54, 6, 34, 81, 99, 342, 3, 4452, 344, 234, 44, 55, 67, 57, 24, 723]
print(bucket_sort(list1, 50))

Panalyz

Python实现10大排序算法

Bubble Sort 冒泡排序

Selection Sort 选择排序

Insertion Sort 插入排序

Shell Sort 希尔排序

Merge Sort 归并排序

Quick Sort 快速排序

Heap Sort 堆排序

Counting Sort 计数排序

Bucket Sort 桶排序

TBC

下一篇：母婴产品消费数据分析(MySQL/Tableau)