算法分类

注：原理大部分是从菜鸟教程搬运的
十种常见排序算法可以分为两大类

• 比较类排序：通过比较来决定元素间的次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
• 非比较类排序：不通过比较来决定元素间的次序，可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
  

算法复杂度

算法详解

冒泡排序

相邻位置比较大小，互换位置，一次遍历后能保证最后的值为最大或最小，简单直观，适用于小规模数据

算法步骤

1. 从前往后遍历，除了最后一个
2. 比较相邻元素，如果第一个比第二个大，就交换
3. 遍历结束后，最后的元素为最大的数据
4. 重复1-3，直到排序完成

动图演示

代码实现

def bubble_sort(arr):
    for i in range(len(arr)):
        for j in range(0, len(arr)-1-i):
            if arr[j] > arr [j+1]:  # 第一个比第二个大
                arr[j], arr[j+1] = arr[j+1], arr[j]  # 交换
    return arr

选择排序

利用二次遍历选择最小值放在当前位置，简单直观，但是算法复杂度最好都是O(n²),效率很低，只适用于小规模数据

算法步骤

1. 从前往后遍历，在从当前位置往后二次遍历
2. 找出最小值，放在当前位置

动图演示

代码实现

def select_sort(arr):
    for i in range(len(arr)):
        min_index = i  # 最小值的下标
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_index]:
                min_index = j
        if (min_index != i):
            arr[i], arr[min_index] = arr[min_index], arr[i]  # 将最小值放在当前位置
    return arr

插入排序

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

算法步骤

• 从第一个元素开始，该元素可以认为已经被排序；
• 取出下一个元素，在已经排序的元素序列中从后向前扫描；
• 如果该元素（已排序）大于新元素，将该元素移到下一位置；
• 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
• 将新元素插入到该位置后；
• 重复步骤2~5

动图演示

代码实现

def insert_sort(arr):
    for i in range(1, len(arr)):
        for j in range(i, 0, -1):  # 从当前位置向前遍历
            if arr[j] < arr[j - 1]:  # 遇到比自己大的，交换；遇到比自己小的，循环结束
                arr[j], arr[j - 1] = arr[j - 1], arr[j]
            else:
                break
    return arr

希尔排序

1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序

算法步骤

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；

2. 按增量序列个数k，对序列进行k 趟排序；

3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

动图演示

代码实现

def shell_sort(arr):
    gap = len(arr) // 2

    while gap > 0:
        for g in range(gap):
            for i in range(g + gap, len(arr), gap):
                for j in range(i, g, -gap):
                    if arr[j] < arr[j - gap]:
                        arr[j], arr[j - gap] = arr[j - gap], arr[j]
                    else:
                        break
        gap = gap // 2
    return arr

归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

算法步骤

1. 把长度为n的输入序列分成两个长度为n/2的子序列；

2. 对这两个子序列分别采用归并排序；

3. 将两个排序好的子序列合并成一个最终的排序序列。

动图演示

代码实现

def merge_sort(arr):
    if len(arr) < 2:
        return arr
    middle = len(arr) // 2
    left = arr[0:middle]
    right = arr[middle:]
    return merge(merge_sort(left), merge_sort(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

快速排序

是冒泡算法的分治版

算法步骤

1. 从数列挑出一个基准
2. 比基准小的放在基准前面， 大的放在基准后面， 这个称为分区
3. 递归地对左右两边的子数列分区

动图演示

代码实现

def quick_sort(arr, left=None, right=None):
    left = 0 if left is None else left
    right = len(arr) - 1 if right is None else right
    if left < right:
        partition_index = partition(arr, left, right)
        quick_sort(arr, left, partition_index - 1)
        quick_sort(arr, partition_index + 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

堆排序

算法步骤

1. 创建堆，长度为数组长度
2. 从堆底部开始互换堆首堆尾，保证堆首的值最大
3. 此时整个堆首的值最大，堆顶端数据和堆尾端数据对换，堆尺寸缩小1
4. 重复步骤2、3，直到堆的尺寸为1

动图演示

代码实现

def build_max_heap(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 heap_sort(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

计数排序

适用于数组元素在一个较小的区间，并且值不为负数

算法步骤

1. 找出数组最大值k，创建一个长度为k+1的新数组
2. 统计待排序数组中每个值为i的元素出现的次数，存入新数组的第1项
3. 反向填充目标数组

动图演示

代码实现

 def count_sort(arr, max_value):
    bucket = [0] * (max_value + 1)
    for num in arr:
        bucket[num]+=1
    index = 0
    for i in range(len(bucket)):
        if bucket[i]:
            for j in range(bucket[i]):
                arr[index] = i
                index += 1
    return arr

桶排序

桶排序是计数排序的升级版，高效与否取决于桶的分布函数和桶内的排序方法

算法步骤

1. 设置一个定量的数组当作空桶；

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

3. 对每个不是空的桶进行排序；

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

动图演示

将元素分布到桶中

元素在桶中排序

代码实现

 def bucket_sort(arr, min_value, max_value):
    BUCKET_SIZE = 3
    bucket_size = (max_value-min_value) // BUCKET_SIZE + 1
    buckets = [[] for i in range(bucket_size)]
    for i in range(len(arr)):
        buckets[(arr[i]-min_value)//BUCKET_SIZE].append(arr[i])  # 利用映射函数分配
    index = 0
    for bucket in buckets:  # 对每个桶进行排序
        quick_sort(bucket)  # 这里使用快速排序
        for num in bucket:
            arr[index] = num
            index += 1
    return arr

基数排序

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。

算法步骤

1. 取得数组中的最大数，并取得位数；

2. arr为原始数组，从最低位开始取每个位组成radix数组；

3. 对radix进行计数排序（利用计数排序适用于小范围数的特点）；

动图演示

代码实现

def radix_sort(arr, max_digit):
    for digit in range(max_digit):
        buckets = [[] for i in range(10)]
        for i in range(len(arr)):
            buckets[int(arr[i] / (10 ** digit)) % 10].append(arr[i])
        index = 0
        for bucket in buckets:
            for num in bucket:
                arr[index] = num
                index += 1
    return arr 

效率测试

测试代码

import copy
import time
import sys
import random

from sort.bubble_sort import bubble_sort
from sort.bucket_sort import bucket_sort
from sort.count_sort import count_sort
from sort.heap_sort import heap_sort
from sort.insert_sort import insert_sort
from sort.merge_sort import merge_sort
from sort.quick_sort import quick_sort
from sort.radix_sort import radix_sort
from sort.select_sort import select_sort
from sort.shell_sort import shell_sort

sys.setrecursionlimit(100000000)


def time_count(func):
    def wrapper(*args, **kwargs):
        start = time.clock()
        func(*args, **kwargs)
        end = time.clock()
        print(f'耗时：{end - start}秒')

    return wrapper


class Executor(object):
    def __init__(self, func, func_name, *args, **kwargs):
        self.func = func
        self.func_name = func_name
        self.args = args
        self.kwargs = kwargs
        self.start()

    @time_count
    def start(self):
        print(self.func_name + '开始执行')
        self.func(*self.args, **self.kwargs)



class TestCase:
    digit = 6

    def __init__(self):
        self.list = [random.randint(0, 10**self.digit-1) for i in range(10**self.digit)]
        print(f'测试{10 ** self.digit}条数据排序')

    def test_bubble_sort(self):
        Executor(bubble_sort, '冒泡排序', copy.deepcopy(self.list))

    def test_select_sort(self):
        Executor(select_sort, '选择排序', copy.deepcopy(self.list))

    def test_insert_sort(self):
        Executor(insert_sort, '插入排序', copy.deepcopy(self.list))

    def test_shell_sort(self):
        Executor(shell_sort, '希尔排序', copy.deepcopy(self.list))

    def test_merge_sort(self):
        Executor(merge_sort, '归并排序', copy.deepcopy(self.list))

    def test_quick_sort(self):
        Executor(quick_sort, '快速排序', copy.deepcopy(self.list))

    def test_heap_sort(self):
        Executor(heap_sort, '堆排序', copy.deepcopy(self.list))

    def test_count_sort(self):
        Executor(count_sort, '计数排序', copy.deepcopy(self.list), 10**self.digit)

    def test_bucket_sort(self):
        Executor(bucket_sort, '桶排序', copy.deepcopy(self.list), 0, 10**self.digit)

    def test_radix_sort(self):
        Executor(radix_sort, '基数排序', copy.deepcopy(self.list), self.digit)

    def main(self):
        # self.test_bubble_sort()
        # self.test_select_sort()
        # self.test_insert_sort()
        self.test_shell_sort()
        self.test_merge_sort()
        self.test_quick_sort()
        self.test_heap_sort()
        self.test_count_sort()
        self.test_bucket_sort()
        self.test_radix_sort()


if __name__ == '__main__':
    TestCase().main()

结果汇总

自己电脑测的，结果可能有偏差，以下结果均为测试5次取平均

总结

数据量较大时，如果不考虑空间复杂度，个人推荐基数排序，空间占用相比计数排序小很多，速度也快；如果考虑空间复杂度，个人推荐希尔排序和快速排序。