Python 实现排序算法

前言 冒泡排序 快速排序 插入排序 希尔排序 选择排序 堆排序 归并排序 计数排序 桶排序 基数排序

前言

本章介绍使用Python实现场景的几种排序算法。分别有冒泡算法、快速排序、插入排序、希尔排序、选择排序、堆排序、归并排序、计数排序、桶排序、基数排序。

创建一个比较大的list，用于测试排序算法使用。

import numpy as np
import time

src_list = np.random.randint(1, 100000, (50000)).tolist()

冒泡排序

冒泡排序是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。

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

start = time.time()
result = bubble_sort(src_list)
end = time.time()
print ("耗时：%d 毫秒" % int(round((end - start) * 1000)))

耗时：197286 毫秒

快速排序

在一个数据集中取个数作为参考点，大于该数的元素放在其右边；小于该数的元素放在其左边。这样就将数据集分成两部分，大于参考值部分和小于参考值部分，递归该过程，直到序列中所有记录均有序。

def quick_sort(listt, left, right):
    if left >= right:
        return listt

    # 选择参考点，该调整范围的第1个值
    pivot = listt[left]
    low = left  
    high = right

    while left < right:
        # 从右边开始查找大于参考点的值
        while left < right and listt[right] >= pivot:
            right -= 1
         # 这个位置的值先挪到左边
        listt[left] = listt[right] 

         # 从左边开始查找小于参考点的值
        while left < right and listt[left] <= pivot:
            left += 1
         # 这个位置的值先挪到右边
        listt[right] = listt[left]

    # 写回改成的值
    listt[left] = pivot

    # 递归，并返回结果
    quick_sort(listt, low, left - 1)    # 递归左边部分
    quick_sort(listt, left + 1, high)   # 递归右边部分
    return listt

start = time.time()
result = quick_sort(src_list, 0, 1000)
end = time.time()
print ("耗时：%d 毫秒" % int(round((end - start) * 1000)))

耗时：43 毫秒

插入排序

插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入

def insert_sort(alist):
    length = len(alist)
    for i in range(1,length):
        for j in range(i, 0, -1):
            if alist[j] < alist[j - 1]:
                alist[j], alist[j - 1] = alist[j - 1], alist[i]
            else:
                break
    return alist

start = time.time()
result = insert_sort(src_list)
end = time.time()
print ("耗时：%d 毫秒" % int(round((end - start) * 1000)))

耗时：20 毫秒

希尔排序

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。

def shell_sort(alist):
    n = len(alist)
    gap = n // 2
    while gap >= 1:
        for i in range(gap,n):
            while (i - gap) >= 0:
                if alist[i] < alist[i-gap]:
                    alist[i], alist[i-gap] = alist[i-gap], alist[i]
                    i = i - gap
                else:
                    break
        gap = gap // 2
    return alist

start = time.time()
result = shell_sort(src_list)
end = time.time()
print ("耗时：%d 毫秒" % int(round((end - start) * 1000)))

耗时：110 毫秒

选择排序

选择排序是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

def select_sort(alist):
    n = len(alist)
    for i in range(n):
    # 设置索引 i为最小值的索引
        min_idx = i
        # 通过比较，不断调整最小值的索引位置
        for j in range(i,n):
            if alist[j] < alist[min_idx]:
                min_idx = j
        # 交换第i个值与最小值
        alist[i], alist[min_idx] = alist[min_idx], alist[i]
    return alist

start = time.time()
result = select_sort(src_list)
end = time.time()
print ("耗时：%d 毫秒" % int(round((end - start) * 1000)))

耗时：101479 毫秒

堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。

# 调整堆的结构，使其父节点的值大于子节点的值
def max_heap(heap, heapsize, root):
    left = 2*root+1
    right = left + 1
    large = root
    if left < heapsize and heap[large] < heap[left]:
        large = left
    if right < heapsize and heap[large] < heap[right]:
        large = right
    # 若large=right或large=left，则说明，出现比父节点大的子节点，这时对调，使子节点变为父节点
    if large != root:
        heap[large], heap[root] = heap[root], heap[large]
        max_heap(heap, heapsize, large)

# 构造一个堆，对堆中数据重新排序
def build_max_heap(heap):
    length = len(heap)
    # 从后往前调整结构
    for i in range((length-2)//2,-1,-1):
        max_heap(heap, length, i)

# 将根节点取出与最后一位对调，对前面len-1个节点继续进行对调过程
def heap_sort(heap):
    build_max_heap(heap)
    for i in range(len(heap)-1,-1,-1):
        heap[0], heap[i] = heap[i], heap[0]
        max_heap(heap,i,0)
    return heap

start = time.time()
result = heap_sort(src_list)
end = time.time()
print ("耗时：%d 毫秒" % int(round((end - start) * 1000)))

耗时：334 毫秒

归并排序

归并排序(mergesort)是创建在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。

分治法：

分割：递归地把当前序列平均分割成两半

集成：在保持元素顺序的同时将上一步得到的子序列集成到一起(归并)

def merge_sort(alist):
    if len(alist) < 2:
        return alist
    # 将列表分成更小的两个列表
    mid = int(len(alist)/2)
    # 分别对左右两个列表进行处理，分别返回两个排序好的列表
    left = merge_sort(alist[:mid])
    right = merge_sort(alist[mid:])
    # 对排序好的两个列表合并，产生一个新的排序好的列表
    return merge(left,right)

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

start = time.time()
result = merge_sort(src_list)
end = time.time()
print ("耗时：%d 毫秒" % int(round((end - start) * 1000)))

耗时：163 毫秒

计数排序

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

对每一个输入的元素a[i]，确定小于 a[i] 的元素个数。所以可以直接把 a[i] 放到它输出数组中的位置上。假设有5个数小于 a[i]，所以 a[i] 应该放在数组的第6个位置上

def count_sort(alist):
    # 找到最大最小值
    min_num = min(alist)
    max_num = max(alist)
    # 初始化计数列表
    count_list = [0]*(max_num-min_num+1)
    # 对列表中的每一个元素计数
    for num in alist:
        count_list[num-min_num] += 1
    alist.clear()
    # 当某个元素的个数不为 0，将该元素填回alist列表
    for cur_num, count in enumerate(count_list):
        while count != 0:
            alist.append(cur_num+min_num)
            count -= 1
    return alist

start = time.time()
result = count_sort(src_list)
end = time.time()
print ("耗时：%d 毫秒" % int(round((end - start) * 1000)))

耗时：20 毫秒

桶排序

把数组a划分为n个大小相同子区间（桶），每个子区间各自排序，最后合并。桶排序要求数据的分布必须均匀，不然可能会失效。计数排序是桶排序的一种特殊情况，可以把计数排序当成每个桶里只有一个元素的情况。

原理：

(1) 设置一个定量的数组当作空桶

(2) 遍历输入数据，并且把数据一个一个放到对应的桶里去

(3) 对每个不是空的桶进行排序

(4) 从不是空的桶里把排好序的数据拼接起来

def bucket_sort(alist):
    min_num = min(alist)
    max_num = max(alist)
    # 设置桶的大小
    bucket_size = (max_num - min_num)/len(alist)
    # 创建桶数组
    bucket_list = [[]for i in range(len(alist)+1)]
    # 向桶数组填数
    for num in alist:
        bucket_list[int((num-min_num)//bucket_size)].append(num)
    alist.clear()
    # 回填，这里桶内部排序直接调用了sorted
    for i in bucket_list:
        for j in sorted(i):
            alist.append(j)
    return alist

start = time.time()
result = bucket_sort(src_list)
end = time.time()
print ("耗时：%d 毫秒" % int(round((end - start) * 1000)))

耗时：61 毫秒

基数排序

基数排序的总体思路就是将待排序数据拆分成多个关键字进行排序，也就是说，基数排序的实质是多关键字排序，比如说成绩的排序，如果两个人总分相同，则语文高的排在前面，语文成绩也相同则数学高的排在前面，如果对数字进行排序，那么个位、十位、百位就是不同优先级的关键

原理：

(1) 取得数组中的最大数，并取得位数

(2) 建立桶数组

(3) 按位数的大小分别装进不同的桶里

(4) 将原数组清空，将各个桶里的数据依次添加进原列表

(5) 再进行前一位的排序，依次循环，直到排序的位数大于最大值的位数

def radix_sort(alist):
    # 记录正在对哪一位进行排序，最低位为个位
    i = 0
    # 最大值的位数
    max_num = max(alist)
    j = len(str(max_num))
    while i < j:
        # 建立桶数组，数字为0-9，所以建10个桶
        bucket_list = [[]for i in range(10)]
        # 按位数的大小分别装进不同的桶里
        for num in alist:
            bucket_list[int(num/(10**i)%10)].append(num)
        #将原列表清空，将各个桶里的数据依次添加进原列表
        alist.clear()
        for l in bucket_list:
            for b in l:
                alist.append(b)
        # 再进行前一位的排序，依次循环，直到排序的位数大于最大值的位数
        i += 1
    return alist

start = time.time()
result = radix_sort(src_list)
end = time.time()
print ("耗时：%d 毫秒" % int(round((end - start) * 1000)))

耗时：123 毫秒