menu Chancel's blog
rss_feed
Chancel's blog
有善始者实繁,能克终者盖寡。

常见的排序算法

作者:Chancel Yang, 创建:2019-03-12, 字数:6522, 已阅:879, 最后更新:2024-03-10

这篇文章更新于 128 天前,文中部分信息可能失效,请自行甄别无效内容。

现代大部分编程语言已经很少需要直接写排序算法了,但学习排序算法的原理依旧是一件非常有意思的事

下文是学习几个常见的排序算法笔记,如有错漏,请不吝指正

1. 前言

常见的算法概览如下

排序算法 是否稳定 最好时间复杂度 最差时间复杂度 平均时间复杂度 空间复杂度
冒泡排序(Bubble sort) $O(n)$ $O(n^2)$ $O(n^2)$ $O(1)$
插入排序(Insertion sort) $O(n)$ $O(n^2)$ $O(n^2)$ $O(1)$
希尔排序(Shell sort) $O(n log n)$ $O(n^2)$ 取决于步长序列 $O(1)$
快速排序(Quicksort) $O(n log n)$ $O(n^2)$ $O(n log n)$ $O(log n)$
选择排序(Selection sort) $O(n^2)$ $O(n^2)$ $O(n^2)$ $O(1)$
归并排序(Merge sort) $O(n log n)$ $O(n log n)$ $O(n log n)$ $O(n)$
计数排序(Counting sort) $O(n + k)$ $O(n + k)$ $O(n + k)$ $O(n + k)$

这些复杂度的值是一般情况下的估计值,实际应用中可能会有所变化。

1.1. 稳定性

算法的稳定性是指对于待排序列中相同项的原来次序不能被算法改变则称该算法稳定,如按数字顺序来排序下列的组合

TEXT
[(2, A), (1, B), (2, C), (3, D)]

那么在排序之后则会得到

TEXT
[(1, B), (2, A), (2, C), (3, D)]

这里可以看到,在排序后,两个值为 2 的元素(2, A), (2, C)仍然保持了它们在原始序列中的相对顺序,我们称这种算法为稳定的排序算法

1.2. 复杂度

复杂度则区分时间复杂度(Time complexity)空间复杂度(Space Complexity)

概念定义如下

  • 时间复杂度是一个函数,它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大$O$符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,亦即考察输入值大小趋近无穷时的情况
  • 空间复杂度是指计算机科学领域完成一个算法所需要占用的存储空间,一般是输入参数的函数。它是算法优劣的重要度量指针,一般来说,空间复杂度越小,算法越好

在不同的场景下,需要对时间和空间的复杂度有所取舍

常见的复杂度通常包含如下

  • $O(1)$:无论输入规模的大小,执行次数都保持恒定。例如,直接访问数组中的特定元素、执行固定次数的操作等
  • $O(n)$:执行次数与输入规模成线性关系。例如,遍历数组、对列表进行线性搜索等
  • $O(log n)$:执行次数与输入规模的对数关系。例如,二分查找算法
  • $O(n^2)$:执行次数与输入规模的平方关系。例如,嵌套循环的冒泡排序算法
  • $O(n log n)$:执行次数与输入规模的线性对数关系。例如,归并排序、快速排序等分治算法

2. 排序算法

2.1. 冒泡排序(Bubble Sort)

冒泡排序是一种简单的排序算法,它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成

实现思路

  1. 循环数组,从左向右比较相邻2个值的大小,并根据大小交换位置,第一次循环结束时最大的数字已经在最右边
  2. 循环n-1次,即获得排序后的顺序

Python代码实现如下

Python
def bubble_sort(sort_list):
    bubble_list_length = len(sort_list)
    while bubble_list_length > 0:
        for _i in range(0, bubble_list_length-1):
            if sort_list[_i] > sort_list[_i + 1]:
                sort_list[_i], sort_list[_i +
                                         1] = sort_list[_i+1], sort_list[_i]
        bubble_list_length -= 1
    return sort_list

2.2. 插入排序(Insertion Sort)

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

实现思路

  1. 获取数组长度n,循环range(1,n),获得A0,A1,比较A0,A1大小并交换位置
  2. 第二次循环,获得A0,A1,A2,比较A0,A1,A2,从右往左比较交换位置,以此类推

Python代码实现如下

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

2.3. 希尔排序(Shell Sort)

希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。希尔排序是不稳定排序算法

实现思路

  1. 选择一个增量序列(increment sequence),通常为n/2,n/4,n/8等。增量序列的选择是希尔排序的关键,不同的增量序列可能会影响算法的性能
  2. 根据选定的增量序列,将待排序序列分割为多个子序列,每个子序列中的元素相互间隔增量个位置
  3. 对每个子序列分别进行插入排序,即对每个子序列中的元素进行比较和交换操作,以使子序列中的元素有序
  4. 逐渐减小增量序列,重复步骤2和步骤3,直到增量序列减小到1
  5. 最后一轮增量序列为1时,进行最后一次插入排序,完成排序

Python代码实现如下

Python
def diminishing_increment_sort(sort_list):
    length = len(sort_list)
    h = 1
    while h < length/3:
        h = 3*h+1
    while h >= 1:
        for i in range(h, length):
            j = i
            while j >= h and sort_list[j] < sort_list[j-h]:
                sort_list[j], sort_list[j-h] = sort_list[j-h], sort_list[j]
                j -= h
        h = h//3
    return sort_list

2.4. 快速排序(Quick Sort)

快速排序又称划分交换排序(partition-exchange sort),简称快排。最早由东尼·霍尔提出。快速排序$O(nlogn)$通常明显比其他算法更快,因为它的内部循环(inner loop)可以在大部分处理器架构上很有效率地达成。

快速排序的内部循环通常使用指针操作和元素交换,而不需要额外的数组或列表操作

实现思路

  1. 取任意一个数作为基准数(第一个/倒数第一均可),并在源数组中删除该数
  2. 建立两个新数组,分别为左数组和右数组
  3. 循环源数组,将每一个数与基准数进行比较,较小的归入左数组,较大的归入右数组
  4. 递归调用自身,将左数组跟右数组递归调用至数组大小小于2,将所有数组合并即可

Python代码实现如下

Python
def quick_sort(sort_list):
    if len(sort_list) > 2:
        mid = sort_list[0]
        sort_list.remove(mid)
        left_list = []
        right_list = []
        for i in range(0, len(sort_list)):
            if sort_list[i] < mid:
                left_list.append(sort_list[i])
            if sort_list[i] > mid:
                right_list.append(sort_list[i])
        return quick_sort(left_list) + [mid] + quick_sort(right_list)
    else:
        return sort_list

2.5. 选择排序(Selection sort)

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

实现思路

  1. 创建新数组,循环当前数据,pop出最小数,添加到新数组,以此类推

Python代码实现如下

Python
def selection_sort(sort_list):
    def _select_min_number(temp_list):
        if len(temp_list) is 0:
            return None
        min_number = temp_list[0]
        for _n in temp_list:
            if _n < min_number:
                min_number = _n
        return min_number

2.6. 归并排序(Merge Sort)

归并排序是创建在归并操作上的一种有效的排序算法,1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。

实现思路

  1. 将待排序序列不断地分割成两个子序列,直到每个子序列只有一个元素。
  2. 逐个合并相邻的子序列,直到所有子序列合并为一个有序序列。

Python代码实现如下

Python
def mergeSort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = mergeSort(arr[:mid])
    right = mergeSort(arr[mid:])

    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0

    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.extend(left[i:])
    result.extend(right[j:])

    return result

2.7. 计数排序(Counting Sort)

计数排序是一个非比较排序算法,该算法于1954年由 Harold H. Seward 提出。优势在于在对一定范围内的整数排序时,它的复杂度为$Ο(n+k)$(其中k是整数的范围),快于任何比较排序算法。 当然这是一种牺牲空间换取时间的做法,而且当$O(k)$>$O(nlog(n))$的时候其效率反而不如归并排序,堆排序等比较排序算法*

实现思路

  1. 新建一个一样大小的数组
  2. 循环旧数组,取出第一个数A1,再循环一遍旧数组,逐一比较,记所有小于A1的数为p,记所有等于A1的数为q
  3. 赋值给新数组下标为[p]-[p+q]范围的数为A1,以此类推

Python代码实现如下

Python
def counting_sort(sort_list):
    length = len(sort_list)
    new_list = [None]*length
    for i in range(length):
        p = 0
        q = 0
        for j in range(length):
            if sort_list[j]<sort_list[i]:
                p+=1
            if sort_list[j]==sort_list[i]:
                q+=1
        for k in range(p,p+q):
            new_list[k] = sort_list[i]
    return new_list

3. 尾声

参考资料


[[replyMessage== null?"发表评论":"发表评论 @ " + replyMessage.m_author]]

account_circle
email
web_asset
textsms

评论列表([[messageResponse.total]])

还没有可以显示的留言...
gravatar
[[messageItem.m_author]] [[messageItem.m_author]]
[[messageItem.create_time]]
[[getEnviron(messageItem.m_environ)]]
[[subMessage.m_author]] [[subMessage.m_author]] @ [[subMessage.parent_message.m_author]] [[subMessage.parent_message.m_author]]
[[subMessage.create_time]]
[[getEnviron(messageItem.m_environ)]]