常用排序算法

2020-10-24

引言

常用排序算法共有十种,堆排序在前面的章节已经介绍过,本章主要介绍九种常用排序算法。排序算法分为以下几种类型:

  • 非线性时间比较类排序
    1. 交换排序:冒泡排序和快速排序
    2. 插入排序:简单插入和希尔排序
    3. 选择排序:简单选择和堆排序
    4. 归并排序:二路归并排序和多路归并排序

  • 线性时间非比较类排序
    1. 基数排序
    2. 计数排序
    3. 桶排序

各大排序算法复杂度比较:

在正式开始排序算法讲解之前,准备好通用工具,以便后续算法测试

# 工具箱
from random import randint

# 生成随机序列
def generateRandomSequence(start, end):
    output = [randint(start, end) for _ in range(100)]
    return output

# 检验排序正确性
def testSorted(sorted_list):
    if not sorted_list:
        raise ValueError('数组为空,无法检测!')
    for i in range(1, len(sorted_list)):
        # 默认检测升序
        if sorted_list[i] < sorted_list[i-1]:
            return False
    return True

此外,本文所有排序算法都默认为升序排列(包含思路解释),事实上降序原理一模一样。

冒泡排序

核心思想

对一个列表多次重复便利,比较相邻的两项,并且交换顺序排错的项。每对列表实现一次遍历,就有一个最大项排在了正确的位置,遍历到最后就完成了排序。

Python实现

利用for-loop结构,免去繁杂的边界问题,外循环倒序遍历,保证每轮循环的最后一项都是已排好的。此外,还增加了'剪枝'操作,如果在某一轮循环中不存在冒泡的行动,说明此时数组已完成排序。

def bubbleSort(nums):
    size = len(nums)
    for i in range(size-1, -1, -1):
        flag = False
        for j in range(i):
            if nums[j] > nums[j+1]:
                nums[j], nums[j+1] = nums[j+1], nums[j]
                flag = True
        if not flag:
            break
        
    return nums

if __name__ == '__main__':
    sample = generateRandomSequence(0, 100)
    
    bubble_sorted = bubbleSort(sample)
    testSorted(bubble_sorted)

快速排序

核心思想

四个字可以概括快排的思路——分而治之,通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对两部分数据进行快速排序,递归地完成整个过程。

Python实现

def quickSort(nums):
    size = len(nums) # 计算数组长度
    def helper(left, right):
        if left >= right: # 递归出口:当左指针大于右指针时,表明左右两侧均已调整完成
            return nums
        pivot = left # 设置基准值指针
        i, j = left, right # 设置左右指针
        while i < j:
            # 指针滑动,保证右指针指向小于基准的元素,左指针指向大于基准的元素
            while i < j and nums[j] > nums[pivot]:
                j -= 1
            while i < j and nums[i] <= nums[pivot]:
                i += 1
            nums[i], nums[j] = nums[j], nums[i]
        # 调整基准点
        nums[pivot], nums[j] = nums[j], nums[pivot]
        helper(left, j-1) # 调整基准点左侧
        helper(j+1, right) # 调整基准点右侧
        return nums
    return helper(0, size-1)

if __name__ == '__main__':
    sample = generateRandomSequence(0, 100)
    
    quick_sorted = quickSort(sample)
    testSorted(quick_sorted)

简单插入排序

核心思想

将每个元素插入到前面已排序的部分,直到最后完成排序。

Python实现

这里给出for循环版本和while循环版本

def insertionSort(nums):
    size = len(nums)
    for i in range(1, size):
        if nums[i] < nums[i-1]:
            tmp = nums.pop(i)
            for j in range(i):
                if tmp < nums[j]:
                    nums.insert(j, tmp)
                    break
    return nums

def insertionSort1(nums):
    size = len(nums)
    for i in range(1, size):
        while i > 0 and nums[i-1] > nums[i]:
            nums[i-1], nums[i] = nums[i], nums[i-1]
            i -= 1
    return nums

if __name__ == '__main__':
    sample = generateRandomSequence(0, 100)
    
    insertion_sorted = insertionSort(sample)
    testSorted(insertion_sorted)
    insertion_sorted1 = insertionSort1(sample)
    testSorted(insertion_sorted1)

希尔排序

核心思想

插入排序的改进版,每次选取一定的间隔,然后对分割的子序列进行插入排序,直到分割间隔为0时终止。

Python实现

def shellSort(nums):
    size = len(nums)
    gap = size // 2
    while gap:
        for i in range(gap, size):
            while i - gap >= 0 and nums[i-gap] > nums[i]:
                nums[i-gap], nums[i] = nums[i], nums[i-gap]
                i -= gap
        gap //= 2
    return nums


if __name__ == '__main__':
    sample = generateRandomSequence(0, 100)
    
    shell_sorted = shellSort(sample)
    testSorted(shell_sorted)

选择排序

核心思想

在未排序的列表中选取一个最小值放到已排序数组的第一位,直到最后一个元素选择完毕。

Python实现

def selectionSort(nums):
    size = len(nums)
    start = 0
    while start < size:
        min_num = float('inf')
        min_index = 0
        for j in range(start, size):
            if nums[j] < min_num:
                min_num = nums[j]
                min_index = j
        nums[start], nums[min_index] = nums[min_index], nums[start]
        start += 1
    return nums
    

if __name__ == '__main__':
    sample = generateRandomSequence(0, 100)
    
    selection_sorted = selectionSort(sample)
    testSorted(selection_sorted)

堆排序树(三):优先队列的概念与基本操作

归并排序

核心思想

归并排序和快排同样采用了分而治之的思想,但它的算法思路是递归地将数组分割为几个子数组,再将子数组内部和外部排序,最后拼接。

Python实现

def mergeSort(nums):
    if len(nums) <= 1:
        return nums
    mid = len(nums) // 2
    left = mergeSort(nums[:mid])
    right = mergeSort(nums[mid:])
    return merge(left, right)

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

    
if __name__ == '__main__':
    sample = generateRandomSequence(0, 100)

    merge_sorted = mergeSort(sample)
    testSorted(merge_sorted)

基数排序

核心思想

根据数字的位数进行排序,从最低位开始到最高位。

Python实现

def radixSort(nums):
    if not nums:
        return []
    maxNum = max(nums)
    maxDigit = len(str(maxNum))
    bucketList = [[] for _ in range(10)]
    div, mod = 1, 10
    for i in range(maxDigit):
        for num in nums:
            bucketList[num % mod // div].append(num)
        div *= 10
        mod *= 10
        idx = 0
        for j in range(10):
            for k in bucketList[j]:
                nums[idx] = k
                idx += 1
            bucketList[j] = []
    return nums
        


if __name__ == '__main__':
    sample = generateRandomSequence(0, 100)

    radix_sorted = radixSort(sample)
    testSorted(radix_sorted)

计数排序

核心思想

计算除数组的最大值和最小值,根据最值开辟一个空间,然后空间种元素下标为数组种的值,元素值表示该元素的数量。最后将这个空间索引元素按顺序输出完成排序,这个方法的缺点是浪费了大量空间,且效率完全取决于最值之差。

Python实现

def countingSort(nums):
    max_num, min_num = max(nums), min(nums)
    tmp = [0] * (max_num-min_num+1)
    for num in nums:
        tmp[num-min_num] += 1
        
    res = []
    for i in range(len(tmp)):
        while tmp[i] > 0:
            res.append(i+min_num)
            tmp[i] -= 1
    return res
    

if __name__ == '__main__':
    sample = generateRandomSequence(0, 100)

    counting_sorted = countingSort(sample)
    testSorted(counting_sorted)

桶排序

核心思想

基数排序的优化版,将每个数据放到一个桶里(桶是均匀分割的数据范围),然后再对每个桶分别排序,递归地完成上述一系列操作。

Python实现

def bucketSort(nums, bucketSize):
    if len(nums) < 2:
        return nums
    max_num, min_num = max(nums), min(nums)
    bucketNum = (max_num-min_num) // bucketSize + 1
    buckets = [[] for _ in range(bucketNum)]
    for num in nums:
        buckets[(num-min_num) // bucketSize].append(num)
    res = []
    for bucket in buckets:
        if not bucket:
            continue
        if bucketSize == 1: # 如果桶间隔为1,等价于计数排序,直接扩展
            res.extend(bucket)
        else:
            if bucketNum == 1: # 如果桶数为1,说明间隔过大
                bucketSize -= 1
            res.extend(bucketSort(bucket, bucketSize))
    return res
    

if __name__ == '__main__':
    sample = generateRandomSequence(0, 100)

    bucket_sorted = bucketSort(sample, 5)
    testSorted(bucket_sorted)
    

总结

这十个常用的排序算法各有优劣,需要针对特定的环境自行选择,但毫无疑问,性价比最高的还是快排。