常见排序算法

排序

其实在大部分编程语言都提供了排序函数，导致在平时间我们进行一些简单的排序的时候直接拿来用，有些原理的思想不怎么记得清了，其实在很多场景下我们排序的数据都是对象。

排序算法的执行效率

一般我们写排序算法，都要去分析它执行的效率。

  • 最好/最坏情况、平均情况时间复杂度

    数据的规模和有序性都会影响排序算法的性能表现，比如，大部分数据是有序的话，肯定更快的能结束排序比对。

  • 时间复杂度的系数、常熟、低阶

    本来复杂度这种东西看的是一个变化趋势，不过在相同复杂度情况下，不同的排序算法比对性能就需要把这些被复杂度忽略的系数、常数、低阶也考虑进来，毕竟排序讲究的是高效稳定。

  • 比较次数和交换（或移动）次数

    在分析排序算法的时候，我们一般也会把比较次数和交换次数考虑进去。

排序算法的内存消耗

算法的内存消耗可以通过空间复杂度来衡量，排序算法也不例外。
一般空间复杂度为O(1)的排序算法，叫做原地排序。

排序算法的稳定性

稳定性也是衡量排序算法的好坏的。稳定性是指待排序中存在相等的元素，经过排序后，相等元素之间原有的先后顺序不变。

小规模数据排序

冒泡排序(O(n²))

冒泡排序算是时间复杂度度比较高的排序，数据量不大的时候，用它还是可以的，比较简单好理解。冒泡排序是稳定的原地排序算法。

时间复杂度O(n²),空间复杂度O(1)

冒泡排序只会操作相邻的两个数据，每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系，如果不满足就互换位置。一次冒泡会让至少一个元素移动到它应该在的位置，重复n次后就完成了数据排序。

  • python实现 
    1
    def bubble_sort(array):
    2
    '''
    3
    冒泡排序(时间复杂度O(n²),空间复杂度O(1))
    4
    :param array: 需要排序的数组
    5
    :return: 返回有序数组
    6
    '''
    7
    l = len(array)
    8
    if l <= 1:
    9
        return array
    10
    for i in range(l):
    11
        j = 0
    12
        # 利用一个标志位标识是否存在数据交换，提前终止必要的数据对比
    13
        is_exchange = False
    14
        while j < l - i - 1: # 比较次数：总个数-已经排序好的个数-1，这个1代表当前排序的元素，因为不需要和自己比较
    15
            if array[j] > array[j + 1]: # 进行数据交换
    16
                tmp = array[j]
    17
                array[j] = array[j + 1]
    18
                array[j + 1] = tmp
    19
                is_exchange = True
    20
            j = j + 1
    21
        if not is_exchange:
    22
            break
    23
    return array

插入排序(O(n²))

插入排序就是找到需要排序的元素应该插入的位置。插入排序是稳定的原地排序算法。
插入排序算法思想是分为：已排序区间和未排序区间。初始已排序区间只有一个元素（也就是数组第一个元素）。

时间复杂度O(n²),空间复杂度O(1)

核心思想就是取未排序区间的元素，在已排序区间找到合适的插入位置将其插入，并保证已排序区间数据一直有序，重复这个过程，直到未排序区间没有元素。

  • 比冒泡的优势

    虽然两者复杂度一直，但是冒泡的数据移动比插入的要复杂（需要靠临时变量的参与赋值），所以硬是要做极致的性能优化的话，还是选择插入排序比较好（相对于冒泡）。

  • python实现

    1
    def insert_sort(array):
    2
        '''
    3
        插入排序(时间复杂度O(n²),空间复杂度O(1))
    4
        :param array:需要排序的数组
    5
        :return:返回有序数组
    6
        '''
    7
        l = len(array)
    8
        if l <= 1:
    9
            return array
    10
        i = 1
    11
        while i < l:
    12
            j = i - 1
    13
            value = array[i]
    14
    15
            # 查找插入位置，也就是j的实际数值表示了合适的位置的前一个索引
    16
            while j >= 0:
    17
                if value < array[j]: # 数据移动
    18
                    array[j + 1] = array[j]
    19
                else:
    20
                    break
    21
                j = j - 1
    22
            i = i + 1
    23
            array[j+1] = value # 合适的位置插入数据
    24
        return array

选择排序(O(n²))

选择排序的思路有点类似插入排序，也是分已排序区间和未排序区间。但是选择排序每次都会从未排序区间中找最小元素，将其放到已排序区间的末尾。

时间复杂度O(n²),空间复杂度O(1)

它是不稳定的原地排序算法，跟其余排序没啥可比性，一般实际项目中不会用，(没啥优化空间,任何情况的复杂度都是O(n²))，不过数据量很小的话，倒也可以用一用无伤大雅

  • python实现 
    1
    # typing为python3.5+新特性
    2
    from typing import List
    3
    def select_sort(array: List[int]) -> List[int]:
    4
        '''
    5
        选择排序(时间复杂度O(n²),空间复杂度O(1))
    6
        :param array: 需要排序的数组
    7
        :return: 返回有序数组
    8
        '''
    9
        l = len(array)
    10
        if l <= 1:
    11
            return array
    12
        for i in range(l):
    13
            # 记录临时的最小值和索引位置
    14
            min_value = array[i]
    15
            min_index = i
    16
            # 查找未排序区的最小值
    17
            for j in range(i, l):
    18
                if min_value > array[j]:
    19
                    min_value = array[j]
    20
                    min_index = j
    21
            # 数据交换
    22
            array[i], array[min_index] = array[min_index], array[i]
    23
        return array

    希尔排序(O(nlogn))

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

    比较在希尔排序中是最主要的操作，而不是交换。用步长序列的希尔排序比插入排序要快，甚至在小数组中比快速排序和堆排序还快，但是在涉及大量数据时希尔排序还是比快速排序慢。

    平均时间复杂度根据步长序列的不同而不同

改进方案

  • 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率

  • 插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

  • python实现

    1
    from typing import List
    2
    def shell_sort(array: List[int]) -> List[int]:
    3
        '''
    4
        希尔排序(时间复杂度O(nlog2n)，最坏空间复杂度O(n))
    5
        :param array: 需要排序的数组
    6
        :return: 返回有序数组
    7
        '''
    8
        n = len(array)
    9
        # 初始步长
    10
        gap = n // 2
    11
        while gap > 0:
    12
            for i in range(gap, n):
    13
                # 每个步长进行插入排序
    14
                temp = array[i]
    15
                j = i
    16
                # 插入排序
    17
                while j >= 0 and j - gap >= 0 and array[j - gap] > temp:
    18
                    array[j] = array[j - gap]
    19
                    j -= gap
    20
                array[j] = temp
    21
            # 得到新的步长
    22
            gap = gap // 2
    23
        return array

大规模数据排序

冒泡排序、插入排序、选择排序这三种排序算法，它们的时间复杂度都是 O(n2)，比较高，适合小规模数据的排序。
归并排序和快速排序算法适合大规模的数据排序,这两种排序都用到了分治思想。
分治算法一般都是用递归来实现的。分治是一种解决问题的处理思想，递归是一种编程技巧。

归并排序(O(nlogn))

核心思想是：如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。

时间复杂度O(nlogn),空间复杂度O(n)
归并排序虽然是稳定的、时间复杂度为 O(nlogn) 的排序算法，但是它是非原地排序算法。归并之所以是非原地排序算法，主要原因是合并函数无法在原地执行

  • python实现 
    1
    def merge_sort(array):
    2
        '''
    3
        归并排序
    4
        :param array: 需要排序的数组
    5
        :return: 返回有序数组
    6
        '''
    7
    8
        def _dispersion(array, low, high):
    9
            '''
    10
            拆分数据
    11
            :param array:
    12
            :param begin:
    13
            :param end:
    14
            :return:
    15
            '''
    16
            if low >= high: return
    17
            mid = low + (high - low) // 2
    18
            _dispersion(array, low, mid)
    19
            _dispersion(array, mid + 1, high)
    20
            _merge(array, low, mid, high)
    21
    22
        def _merge(a, low, mid, high):
    23
            '''
    24
            合并数据
    25
            :param a:
    26
            :param low:
    27
            :param mid:
    28
            :param high:
    29
            :return:
    30
            '''
    31
            print(low,mid,high)
    32
            i, j = low, mid + 1
    33
            tmp = []
    34
            while i <= mid and j <= high:
    35
                if a[i] <= a[j]:
    36
                    tmp.append(a[i])
    37
                    i += 1
    38
                else:
    39
                    tmp.append(a[j])
    40
                    j += 1
    41
            start = i if i <= mid else j
    42
            end = mid if i <= mid else high
    43
            tmp.extend(a[start:end + 1])
    44
            a[low:high + 1] = tmp
    45
    46
        l = len(array)
    47
        if l <= 1:
    48
            return array
    49
        _dispersion(array, 0, l - 1)
    50
        return array

快速排序(O(nlogn))

一般高级语言都会有自带封装的快排方法供调用。
快排是一种原地、不稳定的排序算法。快速排序通过设计巧妙的原地分区函数，可以实现原地排序，解决了归并排序占用太多内存的问题。

大部分情况下时间复杂度为O(nlogn),极端情况下才会退化到O(n²),空间复杂度O(n)

  • python实现 
    1
    def quick_sort(array):
    2
        '''
    3
        快速排序
    4
        :param array: 需要排序的数组
    5
        :return: 返回有序数组
    6
        '''
    7
    8
        def _dispersion(a, low, high):
    9
            '''
    10
            递归分区拆分
    11
            :param a:
    12
            :param low:
    13
            :param high:
    14
            :return:
    15
            '''
    16
            if low < high:
    17
                m = _partition(a, low, high)
    18
                _dispersion(a, low, m - 1)
    19
                _dispersion(a, m + 1, high)
    20
    21
        def _partition(a, low, high):
    22
            '''
    23
            找出合适的中间位置
    24
            :param a:
    25
            :param low:
    26
            :param high:
    27
            :return:
    28
            '''
    29
            pivot, j = a[low], low # 选任意一个数据作为分区点（这里选择第一个，其实分区点的选择对快排的效率是有影响的）
    30
            # 进行分区
    31
            for i in range(low + 1, high + 1):
    32
                if a[i] <= pivot: # 小于分区点的进行数据交换，放分区点左边
    33
                    j += 1 # 顺带记录分区点需要偏移的位置索引
    34
                    a[j], a[i] = a[i], a[j] # 进行数据交换
    35
            a[low], a[j] = a[j], a[low] # 最后对分区点和合适位置的数据进行交换，达到分区效果
    36
            return j
    37
    38
        l = len(array)
    39
        if l <= 1:
    40
            return array
    41
        _dispersion(array, 0, l - 1)
    42
        return array

堆排序(Ο(nlogn))

堆排序是一种基于比较的排序算法。堆排序可以被认为是一种改进的选择排序。类似于选择排序，堆排序将其输入划分为已排序和未排序的区域

线性排序

桶排序、计数排序、基数排序三种时间复杂度都是O(n) 的排序算法。这些排序算法的时间复杂度是线性的，我们把这类排序算法叫作线性排序,对要排序的数据要求很苛刻。
之所以能做到线性的时间复杂度，主要原因是，这三个算法是非基于比较的排序算法，都不涉及元素之间的比较操作，都是非原地的稳定排序算法。

桶排序(O(n))

核心思想是将要排序的数据分到几个有序的桶里,每个桶里的数据再单独进行排序（比如利用快排、归并等）。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。

桶排序没有一个标准，要看实际情况，有的桶排序甚至很复杂。
实际项目上，桶排序其实比计数排序用的场景更多，经常用于外部排序，然后在结合其余排序算法。

  • 主要注意这几要素

    1
    1.在额外空间充足的情况下，尽量增大桶的数量
    2
    2.使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中
    3
    3.对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要

  • 思路步骤

    1
    1.确定每个桶里装的数值范围大小。
    2
    2.根据数值来确定需要桶的个数。
    3
    3.利用映射函数把数值分散到各个桶里。
    4
    4.遍历每个桶进行单独排序，这里的排序可随自己选择排序算法。
    5
    5.组合每个桶子的数据。

  • python实现

    1
    def bucket_sort(array, bucket_size):
    2
        '''
    3
        桶排序
    4
        param array: 需要排序的数组
    5
        :param bucket_size: 桶子大小，表示每个桶最大可以装多大的倍数值。
    6
            eg：第一个桶：1*bucket_size - 1，第二个桶：2*bucket_size - 1
    7
        :return: 返回有序数组
    8
        '''
    9
        l = len(array)
    10
        if l <= 1: return array
    11
    12
        # 找出最大/小值
    13
        '''
    14
        类似于：
    15
        min_value , max_value = array[0],array[0]
    16
        for value in array:
    17
            if min_value > value:
    18
                min_value = value
    19
            elif max_value < value:
    20
                max_value = value
    21
        '''
    22
        min_value = min(array)
    23
        max_value = max(array)
    24
    25
        # 计算需要的桶子个数
    26
        bucket_count = ((max_value - min_value) // bucket_size) + 1
    27
    28
        # 创建二维数组来当做桶子
    29
        buckets = [[] for i in range(bucket_count)]
    30
    31
        # 使用映射函数（这里用整除法代替），将数据均匀分配到桶子里
    32
        for value in array:
    33
            # 计算数据应该放入桶子的序号
    34
            index = (value - min_value) // bucket_size
    35
            # 将数据添加进桶里（利用python list 自动扩容特性）
    36
            buckets[index].append(value)
    37
    38
        # 对每个桶子排序（这里利用归并排序，主要是为了稳定）
    39
        array.clear()
    40
        for bucket in buckets:
    41
            if len(bucket) <= 0: continue  # 空桶子直接忽略
    42
            # a_sort = insert_sort(bucket)
    43
            a_sort = merge_sort(bucket)
    44
            # 依次循环添加到数组即可
    45
            for value in a_sort:
    46
                array.append(value)
    47
        return array

计数排序(O(n))

计数排序其实是桶排序的一种特殊情况,它实际是把每一种数据可能都分了一个桶，当要排序的 n 个数据，所处的范围并不大的时候，比如最大值是 k，我们就可以把数据划分成 k 个桶。每个桶内的数据值都是相同的，省掉了桶内排序的时间。

相对来说比较占空间，因为排序的过程需要额外的开辟内存空间来辅助排序（使用前评判一下是否可以接受这些内存的消耗,有点空间换时间的味道）

  • 思想步骤

    1
    1.找出排序数组最大的值，用它充当桶子个数。（也是因为这个导致计数排序不能排序非负整数，也对元素数值过大不适合）。
    2
    2.遍历数组对各种值进行计数操作写入计数数组。
    3
    3.对计数数组进行逐步求和操作写入求和数组
    4
    4.最后遍历需要排序的数组，根据计数求和数组计算下标插入数据。

  • python实现

    1
    def count_sort(array):
    2
        '''
    3
        计数排序(只能排序非负整数，如果有负数，要转换成整数在排序)
    4
        :param array: 需要排序的数组
    5
        :return: 返回有序数组
    6
        '''
    7
        n = len(array)
    8
        if n <= 1: return array
    9
        # 找出最大值规划桶的个数
    10
        '''
    11
        原理:
    12
        max_value = array[0]
    13
        for i in range(1, n):
    14
            if max_value < array[i]:
    15
                max_value = array[i]
    16
        '''
    17
        max_value = max(array)
    18
    19
        # 设置桶大小
    20
        barrel = [0] * (max_value + 1)
    21
        # 遍历数据开始计数
    22
        for value in array:
    23
            barrel[value] += 1
    24
    25
        # 对计数逐步求和生成数组
    26
        '''
    27
        求和原理类似于：
    28
        for j in range(1,len(barrel)):
    29
            barrel[j] = barrel[j - 1] + barrel[j]
    30
            counts_sum = barrel
    31
        '''
    32
        counts_sum = list(itertools.accumulate(barrel))
    33
        
    34
        # sort为排序后的数组
    35
        sort = [0] * n
    36
        # 从尾部开始遍历，保证排序的稳定性（因为相同元素是从最大位置开始算的下标）
    37
        for value in reversed(array):
    38
            count = counts_sum[value]
    39
            # 计算元素应该所在的位置并插入数组
    40
            sort[count - 1] = value
    41
            # 计数和自减一次
    42
            counts_sum[value] -= 1
    43
        array[:] = sort
    44
        return sort

  • 注意

    计数排序只能用在数据范围不大的场景中，如果数据范围 k 比要排序的数据 n 大很多，就不适合用计数排序了。而且，计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数

基数排序(O(n))

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

  • 思路步骤

    1
    1.找出最大值确定位数到底有几位。
    2
    2.根据位数确定最外层循环次数。
    3
    3.根据实际情况确定桶子个数（比如数值排序，只要10个桶子）。
    4
    4.根据每个位放入桶里，最后循序取出替换原数据，进行下一次的更高位的入桶操作。

  • python实现

    1
    def radix_sort(array):
    2
        '''
    3
        基数排序
    4
        :param array: 需要排序的数组
    5
        :return: 返回有序数组
    6
        '''
    7
        # 找出最大位数
    8
        digit = 0  # 最低位数初始为0
    9
        max_digit = 1  # 最高位数初始为1
    10
        max_value = max(array)  # 找出最大值求最大位数
    11
        while 10 ** max_digit < max_value:
    12
            max_digit += 1
    13
    14
        # 按位排序，从低到高分别入桶
    15
        while digit < max_digit:
    16
            tmp = [[] for i in range(10)]  # 因为是数字排序，这里搞10个桶子就够了（因为个位数范围0~9）
    17
    18
            # 遍历，求出每个值的位数（从个位开始）
    19
            for value in array:
    20
                # 利用位数值做数组索引
    21
                t = int((value / 10 ** digit) % 10)
    22
                tmp[t].append(value)
    23
    24
            # 把桶子里的数据按循序取出来,替换上一次的数据
    25
            array.clear()
    26
            for bucket in tmp:
    27
                for i in bucket:
    28
                    array.append(i)
    29
            # 继续高位排序
    30
            digit = digit + 1
    31
    32
        return array

基数、计数、桶排序区别

三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异

  • 基数排序：根据键值的每位数字来分配桶
  • 计数排序：每个桶只存储单一键值
  • 桶排序：每个桶存储一定范围的数值
赏

拿钱去买猫粮~

微信

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

优秀的判断力来自经验，<br>但经验来自于错误的判断。<br><br>~余生只想爱胖爱生活<br><br>真正的勇士敢于直面惨淡的人生，<br>敢于正视淋漓的鲜血。