关于算法:算法可视化从入门到精通-10-大排序算法

41次阅读

共计 21117 个字符，预计需要花费 53 分钟才能阅读完成。

在本文中，咱们将通过动图可视化加文字的模式，循序渐进全面介绍不同类型的算法及其用处（包含原理、优缺点及应用场景）并提供 Python 和 JavaScript 两种语言的示例代码。除此之外，每个算法都会附有一些技术阐明，比方应用大 \(O\) 符号来剖析不同算法的工夫复杂度和空间复杂度等，也提到了一些少数人都很容易了解的一些高级概述。

篇幅很长，急躁读完它，您会受益匪浅。

提要

  1. 什么是排序算法？

    • 排序算法有什么用？
    • 为什么排序算法如此重要？
    • 算法的评估规范

    • 数据结构中不同类型的排序算法

      • 基于比拟的排序算法
      • 基于非比拟的排序算法
      • 就地排序算法
      • 稳固的排序算法
      • 自适应排序算法

  2. 您须要理解的 10 大排序算法

    • 冒泡排序
    • 插入排序
    • 疾速排序
    • 桶排序
    • 壳排序
    • 归并排序
    • 抉择排序
    • 基数排序
    • 梳排序
    • 排序
  3. 比拟所有排序算法
  4. 什么是最常见的排序算法？

什么是排序算法？

从实质上讲，排序算法是一种计算机程序，它将数据组织成特定的程序，例如字母程序或数字程序，通常是升序或降序。

排序算法有什么用？

排序算法次要用于以高效的形式重新排列大量数据，以便更容易地对其进行搜寻和操作。它们还用于进步搜寻和合并等其余算法的效率，这些算法的操作依赖于排序数据。

为什么排序算法如此重要？

排序算法用于按特定程序组织数据，这使得搜寻、拜访和剖析更加容易。在许多利用中，排序是数据处理流程的要害局部，排序算法的效率对系统的整体性能产生重大影响。

  • 在数据库中 排序用于按特定程序检索记录，例如按日期、字母程序或数字程序。这使用户能够疾速找到他们须要的数据，而无需手动搜寻大量未分类的数据。
  • 在搜索引擎中 按相关性顺序排列搜寻后果。通过以这种形式对后果进行排序，用户能够疾速找到他们想要的信息，而不用筛选不相干的后果。
  • 在许多迷信和工程利用中 钻研人员能够进行数据分析和模仿，以深刻理解简单零碎，并对将来行为做出更精确的预测。

算法的评估规范

评估一个排序算法的好坏，通常按照以下规范进行评估：

  • 工夫复杂度 是指在计算机科学与工程畛域实现一个算法所须要的工夫，是掂量一个算法优劣的重要参数，应用大 \(O\) 符号示意。一般而言，好的性能是 \(O(n \log n)\)，坏的性能是 \(O(n^2)\)，对于一个排序现实的性能是 \(O(n)\)，但均匀而言不可能达到。
  • 空间复杂度 形容该算法或程序运行所须要的存储空间大小，和工夫复杂度相似，空间复杂度通常也应用大 \(O\) 符号来渐进地示意，例如 \(O(n)\)、\(O(2^n)\)、\(O(n \log n)\) 等，其中 \(n\) 用来示意输出的长度，该值能够影响算法的空间复杂度。
  • 递归 一些算法要么是递归的，要么是非递归的，而其余算法可能两者都是（如归并排序）。
  • 稳定性 稳固排序算法会让本来有相等键值的纪录维持绝对秩序。也就是说，如果一个排序算法是稳固的，当有两个相等键值的纪录 \(R\) 和 \(S \)，且在本来的列表中 \(R \) 呈现在 \(S \) 之前，在排序过的列表中 \(R \) 也会呈现在 \(S \) 之前。
  • 它们是否是比拟排序 比拟排序仅通过应用比拟运算符比拟两个元素来检查数据。
  • 算法是串行还是并行的
  • 自适应性 利用其输出中的现有程序，则它属于 自适应排序系列。

数据结构中不同类型的排序

有多种类型的排序可用，排序算法的抉择取决于各种因素，例如数据集的大小、要排序的数据类型以及所需的工夫和空间复杂度。

基于比拟的排序算法

比拟数据集中的元素，并依据比拟后果来确定两个元素中哪个应该放在序列后面。基于比拟的排序算法包含：

  • 疾速排序
  • 堆排序
  • 归并排序
  • 插入排序
  • 抉择排序
  • 冒泡排序

基于非比拟的排序算法

这些不间接比拟元素，而是应用数据集的其余属性来确定它们的程序。基于非比拟的排序算法包含：

  • 基数排序
  • 计数排序
  • 桶排序

就地排序算法

这些算法对数据进行就地排序（In-place），这意味着他们不须要额定内存来存储两头后果，这些算法只须要少数几个指针，所以它们的空间复杂度都是 \(O(log \ n) \)。就地排序算法的示例包含：

  • 冒泡排序
  • 梳排序
  • 抉择排序
  • 插入排序
  • 堆排序
  • 希尔排序

稳固的排序算法

稳固排序算法（Stable sorting）会让本来有相等键值的纪录维持绝对秩序。也就是如果一个排序算法是 稳固 的，当有两个相等键值的纪录 \(R \) 和 \(S \)，且在本来的列表中 \(R \) 呈现在 \(S \) 之前，在排序过的列表中 \(R \) 也将会是 \(S \) 之前。

这些保留了数据集中的相等元素的绝对程序。稳固排序算法的示例包含 插入排序 、 归并排序 和Timsort 等。

自适应排序算法

如果排序算法利用其输出中的现有程序，则它属于自适应排序（Adaptive sorting）。它受害于输出序列中的预排序，通常通过批改现有的排序算法来执行。自适应排序算法的示例包含 插入排序 、 冒泡排序 和 Timsort 等。

您须要晓得的 10 大排序算法

当初让咱们来看看在排序算法中须要理解的十种罕用的排序算法。

冒泡排序

冒泡排序（Bubble sort）有时也称为“下沉排序”，是一种简略的排序算法，该排序算法是基于比拟的算法。它反复遍历给定的数据列表，一次比拟两个元素，如果程序谬误则替换它们，该算法始终继续到它不替换任何项为止。

冒泡排序的历史

冒泡排序的起源能够追溯到 20 世纪 50 年代前期，Donald Knuth 在其 1968 年的经典著作 《计算机编程艺术》 中对其进行了遍及。

从那时起，它被宽泛用于各种利用，包含编译器的排序算法、数据库中的元素排序，甚至扑克牌的排序。

冒泡的排序的优缺点

冒泡排序被认为是一种绝对低效的排序算法，因为它的均匀复杂度和最坏状况复杂度都是 \(O(n^2) \)，这使得它的效率远低于大多数其余排序算法，例如疾速排序或归并排序等。

技术阐明：复杂度 \(O(n^2) \) 意味着算法实现所需的工夫与输出大小的平方成正比。这意味着更大的输出会导致算法破费更长的工夫能力实现。

例如，思考一种对数字数组进行排序的算法，对一个蕴含 10 个数字的数组进行排序，可能须要 1 秒，但对蕴含 20 个数字的数组进行排序，则可能就须要 4 秒。这是因为该算法必须将数组中的每个元素与其余所有元素进行比拟，因而它必须对较大的数组进行 20 次比拟，而对较小的数组只需 比拟 10 次。

然而，它很容易了解和实现，并且常常被用作排序的入门以及更简单算法的构建块，但现在它在实践中很少被应用。

冒泡排序的用例

冒泡排序是一种简略的的算法，可用于对小型列表或元素数组进行排序。它易于实现和了解，因而能够在简略和清晰比性能更重要的状况下应用。

  • 教育目标 它常常被用在计算机科学课程中，作为简略排序算法的一个例子。学生们能够通过学习冒泡排序来理解根本的排序技术，并通过学习冒泡排序来理解算法的工作原理。
  • 对小数据集进行排序 它可用来对最多几百个元素的小型数据集进行排序。在性能不是关键问题的状况下，冒泡排序能够成为对小列表进行排序的一种疾速而简略的办法。
  • 预排序数据 它能够用作更简单的排序算法的一个初步步骤。例如，如果数据曾经被局部排序，在运行更简单的算法之前，能够用冒泡排序来进一步排序数据。
  • 构建更简单算法的模块 它通常与归并排序或疾速排序联合应用，并应用插入排序对小型子数组进行排序，因为这些其余算法能够在更大的数据集上体现更好的性能。

冒泡排序的实现

  1. 应用嵌套循环来遍历各个项。
  2. 比拟列表中的相邻的两项。
  3. 如果程序不对，就进行替换。
  4. 直到列表被排序实现。
Python 中的冒泡排序
def bubble_sort(items):
    for i in range(len(items)):
        for j in range(len(items) - 1 - i):
            if items[j] > items[j+i]:
                items[j], items[j+1] = item[j+1], items[j]
    return items
items = [10, 14, 2, 9, 14, 37, 29]
print(bubble_sort(items))
JavaScript 中的冒泡排序
function bubbleSort(items) {
    let swapped;
    do {
        swapped = false;
        for (let i = 0; i < items.length - 1; i++) {if(items[i] > items[i+1]) {[items[i], items[i+1]] = [items[i+1], items[i]]
                swapped = true;
            }
        }
    } while(swapped)
    return items;
}

items = [10, 14, 2, 9, 14, 37, 29]
console.log(bubbleSort(items))

插入排序

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

插入排序在实现上，通常采纳就地排序（即只需用到 \(O(1) \) 的额定空间的排序），因此在从后向前扫描过程中，须要重复把已排序元素逐渐向后挪位，为最新元素提供插入空间。

插入排序的历史

在《计算机编程的艺术》中，Knuth 评论说插入排序“早在 1946 年约翰·莫奇利 (John Mauchly) 在首次发表的计算机排序探讨中就提到了”，并将其形容为一种“天然”算法，能够很容易地了解和实现。

到 1950 年代前期，Donald L. Shell 对他的 Shell 排序算法（见下文）进行了一系列改良，该办法将元素之间的间隔进行比拟，每次通过时间隔都会减小，从而将算法的复杂度升高到 \(O(n^{3/2}) \) 和 \(O(n^{4/3}) \) 两个不同的变体中。这听起来可能不多，但对于理论利用来说这是一个相当显着的改良！

技术阐明：\(O(n^{3/2}) \) 和 \(O(n^{4/3}) \) 复杂度比 \(O(n^2) \) 复杂性更有效率，这意味着它们须要更少的工夫来实现。这是因为他们不须要执行与 \(O(n^2) \) 复杂度一样多的比拟。

例如，应用 \(O(n^2) \) 算法对蕴含 10 个数字的数组进行排序可能须要 1 秒，但应用 \(O(n^{3/2}) \) 算法对同一个数组进行排序可能只须要 0.5 秒。这是因为在应用该算法时能够执行更少的比拟，从而导致更快的运行工夫。

2006 年，Bender、Martin Farach-Colton 和 Mosteiro 公布了插入排序的一种新变体，称为库排序或“间隙插入排序（gapped insertion sort）”，它在整个数组中留下大量未应用的空间（或“间隙”），进一步改良了运行工夫到 \(O(n \log n) \)。

技术阐明：\(O(n \log n) \) 复杂度比 \(O(n^2) \) 以及 \(O(n^{3/2}) \) 和 \(O(n^{4/3}) \) 复杂度更有效率。这是因为它采纳了分而治之的办法，这意味着它能够将问题分解成更小的局部并更快地解决它们。

例如，应用一种 \(O(n^2) \) 算法对蕴含 10 个数字的数组进行排序可能须要 1 秒，应用一种 \(O(n^{3/2}) \) 算法对同一个数组进行排序须要 0.5 秒，但应用一种 \(O(n \log n) \) 算法对同一个数组进行排序可能仅须要 0.1 秒。这是因为该算法能够将数组分解成更小的局部并并行求解它们，从而放慢运行工夫。

插入排序的优缺点

插入排序通常在实践中用于小数据集或作为更简单算法的构建块。

就像冒泡排序一样，它的最坏状况和均匀状况工夫复杂度是 \(O(n^2) \)。但与冒泡排序不同的是，
插入排序可用于对数据集进行就地排序，这意味着它不须要额定的内存来存储两头后果。

插入排序的用例

插入排序简略高效，罕用于输出数据曾经排序或输出数据规模较小的状况。它还用于对小型数据集进行排序和构建更简单算法的块，就像冒泡排序一样。

  • 局部排序的数据 它非常适合数据曾经局部排序的状况。在这种状况下，算法能够疾速地将新元素插入到正确的地位，而不须要简单的排序操作。
  • 在线分拣 它通常用于输出数据当时未知的在线排序应用程序中。在这些状况下，算法能够在收到输出数据时对其进行增量排序。
  • 自适应排序 插入排序是自适应排序的候选者，因为它能够利用输出数据中的现有程序。随着输出数据变得更加有序，算法的性能也会进步。

插入排序的实现

  1. 取一个未排序的列表，抉择第一个项作为 “ 枢轴（pivot）”。
  2. 遍历列表，将枢轴插入到排序后列表中的正确地位。
  3. 对列表中的下一个项反复这一过程。
  4. 继续下去，直到列表排序结束。
Python 中的插入排序
def insertion_sort(items):
    for i in range(1, len(items)):
        j = i
        while j > 0 and items[j-1] > items[j]:
            items[j-1], items[j] = items[j], items[j-1]
            j -= 1
    return items

items = [6,20,8,19,56,23,87,41,49,53]
print(insertion_sort(items))
JavaScript 中的插入排序
function insertionSort(items) {for(let i = 1; i < items.length; i++) {
        let j = i;
        // 从后向前扫描
        while(j > 0 && items[j-1] > items[j]) {[items[j-1], items[j]] = [items[j], items[j-1]];
            j--;
        }
    }
    return items;
}

let items = [6, 20, 8, 19, 56, 23, 87, 41, 49, 53];
console.log(insertionSort(items));

疾速排序

疾速排序（Quicksort）是一种风行的分而治之排序算法，其基于将数组划分为两个子数组的准则——一个蕴含小于“枢轴”元素的元素，另一个蕴含大于“枢轴”元素的元素，而后递归地对这两个子数组进行排序。

疾速排序的根本步骤包含：

  1. 从数组中抉择一个“枢轴”元素。
  2. 将数组分成两个子数组，一个蕴含小于枢轴的元素，另一个蕴含大于枢轴的元素。
  3. 应用疾速排序递归地对两个子数组进行排序。
  4. 合并两个排序的子数组。

快排的历史

疾速排序由 Tony Hoare 于 1959 年创造，Hoare 在英国的 Elliott Brothers 计算机公司)工作时开发了该算法，作为对 Ferranti Mark I 计算机内存中的单词进行排序的一种办法。

疾速排序最后于 1961 年作为钻研论文发表，因为其简略、高效和易于实现，它很快成为应用最宽泛的排序算法之一。

快排的长处

  • 它的均匀用例工夫复杂度为 \(O(n \log n) \)。
  • 它须要很少的额定内存，因为它对数组进行就地排序。
  • 它易于施行并且被宽泛了解。
  • 它很容易地并行化。

快排的毛病

它的最坏状况工夫复杂度是 \(O(n^2) \)，当枢轴抉择不过后，使其在某些状况下比其余算法（如归并排序或堆排序）效率低。

技术阐明：咱们不想抉择太小或太大的枢轴，否则算法将以二次方工夫运行。现实的状况是抉择中位数作为基准，但这并不总是可行，除非咱们当时理解数据分布。

疾速排序的用例

疾速排序作为一种高效的排序算法，有着宽泛的利用。

  • 大数据集 它的均匀状况工夫复杂度为 \(O(n \log n) \)，这意味着它能够疾速对大量数据进行排序。
  • 随机数据 它在随机排序的数据上体现良好，因为它依赖于枢轴元素将数据分成两个子数组，而后递归排序。当数据是随机的时，枢轴元素很可能靠近中位数，这会导致良好的性能。
  • 并行处理 它能够很容易地并行化，这使得它非常适合在多核处理器上对大型数据集进行排序。通过将数据分成更小的子数组，该算法能够同时在多个内核上执行，从而进步性能。
  • 外排序 它通常用作外排序算法的一部分，用于对太大而无奈放入内存的数据进行排序。在这种状况下，数据被分类为块，而后应用归并排序算法将其合并。
  • 数据压缩 它被用在一些数据压缩算法中，例如 bzip2 压缩软件 中应用的 Burrows-Wheeler 变换。该算法用于对 Burrows-Wheeler 矩阵中的数据进行排序，而后对其进行转换以生成压缩数据。

疾速排序的实现

  1. 选取“枢轴”点，最好是中位数，将列表分为两局部。
  2. 疾速对左侧局部和右侧局部进行排序。
  3. 持续直到列表排序结束。
Python 中的疾速排序
def quick_sort(items):
    if len(items) > 1:
        privot = items[0]
        left = [i for i in items[1:] if i < privot]
        right = [i for i in items[1:] if i >= pivot]
        return quick_sort(left) + [pivot] + quick_sort(right)
    else:
        return items
        
items = [6,20,8,19,56,23,87,41,49,53]
print(quick_sort(items))
JavaScript 中的疾速排序
function quickSort(items) {if(items.length > 1) {
        // 以第一项作为枢轴
        const pivot = items[0];
        let left = [], right = [];
        for(let i = 1; i < items.length; i++) {if(items[i] < pivot) {left.push(items[i]);
            } else {right.push(items[i]);
            }
        }
        return [...quickSort(left), pivot, ...quickSort(right)];
    } else {return items;}
}

const items = [6, 20, 8, 19, 56, 23, 87, 41, 49, 53];
console.log(quickSort(items));

桶排序

桶排序（Bucket sort）或称为 箱排序，是一种用于对均匀分布的数据进行排序的有用算法，它能够很容易地并行化以进步性能。

其工作的原理是将数组分到无限数量的桶里。每个桶再个别排序（有可能再应用别的排序算法或是以递归形式持续应用桶排序进行排序）。桶排序是鸽巢排序的一种演绎后果。当要被排序的数组内的数值是平均调配的时候，桶排序应用线性工夫 \(O(n) \)。但桶排序并不是比拟排序，他不受 \(O(n \log n) \) 上限的影响。

桶排序的根本步骤包含：

  1. 设置一个定量的数组当作空桶子。
  2. 遍历列表，并且把项一个一个放到对应的桶子去。
  3. 对每个不是空的桶子进行排序。
  4. 从不是空的桶子里把项再放回原来的列表中。

桶排序的历史

桶排序的实现早在 1950 年代就曾经存在，有音讯称该办法自 1940 年代就已存在，它当初仍在宽泛应用。

桶排序的长处

  • 它对于均匀分布的数据是十分有效率的，均匀工夫复杂度为 \(O(n+k) \)，其中 \(n \) 是元素的数量，\(k \) 是桶的数量。
  • 它很容易的并行化，从而能够利用古代处理器中的多个内核。
  • 它是稳固的，这意味着它保留了原始数组中的相等元素的绝对程序。
  • 通过调整程序，它能够用于具备非均匀分布的数据。

* 技术阐明：\(O(n+k) \) 的复杂性比 \(O(n^2) \)、\(O(n^{3/2}) \) 和 \(O(n^{4/3}) \)、\(O(n \log n) \)  复杂度更有效率。这是因为它只须要执行线性数量的操作，而不必思考输出的大小。
例如，思考一种对数字数组进行排序的算法。应用 \(O(n^2) \) 算法对一个由 10 个数字组成的数组进行排序可能须要 1 秒，应用 \(O(n^{3/2}) \) 算法对同一数组进行排序可能须要 0.5 秒，应用 \(O(n \log n) \) 算法对同一数组进行排序可能须要 0.1 秒，但应用 \(O(n+k) \) 算法对同一数组进行排序仅须要 0.05 秒，这是因为该算法不须要执行那么多比拟。

桶排序的毛病

对于非均匀分布的数据，桶排序的效率低于其余排序算法，最坏状况下的性能为 \(O(n^2) \)。此外，它须要额定的内存来存储桶，这对于十分大的数据集来说可能是个问题。

桶排序的用例

就像疾速排序一样，桶排序能够很容易地并行化并用于外排序，然而桶排序在解决均匀分布的数据时特地有用。

  • 对浮点数进行排序 在这种状况下，划分为固定数量的桶区间，每个桶代表输出数据的一个子区间。而后将这些数字放入相应的桶中，并应用另一种算法（例如插入排序）进行排序。最初，排序后的数据被连接成一个数组。
  • 对字符串进行排序 依据字符串的第一个字母分组到桶中。而后应用另一种算法对每个桶中的字符进行排序，或递归的应用桶排序。对字符串中的每个后续字母反复此过程，直到整个汇合排序结束。
  • 直方图生成 这可用于生成数据的直方图，用于示意一组值的频率散布。在这种状况下，将数据范畴划分为固定数量的桶，并统计每个桶中值的数量。生成的直方图可用于可视化数据的散布。

桶排序的实现

  1. 将项的列表拆分为肯定数量的“桶”。
  2. 每个桶应用不同排序算法进行排序。
  3. 而后将这些桶合并回一个排序列表中。
Python 中的桶排序
def bucket_sort(items):
    buckets = [[] for _ in range(let(items))]
    for item in items:
        bucket = int(item/len(items))
        buckets[bucket].append(item)
    for bucket in buckets:
        bucket.sort()
    return [item for bucket in buckets for item in bucket]

items = [6,20,8,19,56,23,87,41,49,53]
print(bucket_sort(items))
JavaScript 中的桶排序
function bucketSort(items) {
    // 分成 items.length 个桶
    const buckets = new Array(items.length);
    for(let i = 0; i < buckets.length; i++) {buckets[i] = []}
    // 遍历列表，依据条件往每个桶里放对应的数据
    for(let j = 0; j < items.length; j++) {let bucket = Math.floor(items[j] / items.length)
        buckets[bucket].push(items[j]) 
    }

    // 对每个桶里的数据进行排序
    for(let k = 0; k < buckets.length; k++) {buckets[k].sort();}
    // 将每个桶组合到一个列表中
    return [].concat(...buckets) 
 }

let items = [6, 20, 8, 19, 56, 23, 87, 41, 49, 53];
console.log(bucketSort(items));

Shell 排序

Shell 排序 也称 递加增量排序算法，它不是一次对整个列表进行排序，而是将列表分成更小的子列表。而后应用插入排序算法对这些子列表进行排序，从而缩小排序列表所需的替换次数。Shell 排序是插入排序的一种更高效的改良版本，是非稳固排序算法。

它也被称为 “Shell 办法 ”，其工作原理是，首先定义一个称为增量序列的整数序列，增量序列用于确定将独立排序的子列表大小，最罕用的增量序列是“Knuth 序列”，其定义如下（其中 \(h \) 是具备初始值的区间，\(n \) 是列表的长度）。

h = 1
while h < n:
  h = 3*h + 1

一旦定义了增量序列，Shell 排序算法就会应用插入排序算法对子列表进行排序，以增量序列作为步长，从最大增量开始，而后向下迭代到最小增量。

当增量大小为 1 时算法进行，此时它等同于惯例插入排序算法。

Shell 排序的历史

Shell 排序是 Donald Shell 于 1959 年创造的，作为插入排序的变体，旨在通过将原始列表合成为更小的子列表并对这些子列表进行独立排序来进步性能。

Shell 排序的长处

  • 它是插入排序的改良版本，因而易于了解和实现。
  • 对于许多输出数据序列，它的工夫复杂性优于 \(O(n^2) \)。
  • 这是一种就地排序算法，这意味着它不须要额定的内存。

Shell 排序的毛病

很难预测 Shell 排序的工夫复杂度，因为它取决于增量序列的抉择。

Shell 排序的用例

Shell 排序是一种通用算法，用于在各种应用程序中对数据进行排序，尤其是在对大型数据集进行排序时，例如疾速排序和桶排序等。

  • 对大部分已排序的数据进行排序 Shell 排序缩小了数据排序所需的比拟和替换次数，在这种特定状况下，这使得它比其余排序算法（例如疾速排序或并归排序）更快。
  • 应用大量反转对数组进行排序 反转是掂量一个数组未被排序的水平，它被定义为程序谬误的元素对的数量。在对具备大量反转的数组进行排序时，Shell 排序比其余一些算法（如冒泡排序或插入排序）更无效。
  • 就地排序 Shell 排序不须要额定的内存来对输出进行排序，这使得它在内存无限或不须要额定内存应用的状况下十分有用。
  • 在分布式环境中排序 通过将输出数据分成更小的子列表并独立排序，每个子列表能够在独自的处理器或节点上排序，从而缩小排序数据所需的工夫。

Shell 排序的实现

  1. 将 \(n \) 个元素的数组划分为 \(n/2 \) 个子序列。
  2.  第一个数据和第 \(n/2 \) + \(1 \) 个数据进行比拟，第 \(2 \) 个数据和第 \(n/2 \) + \(2 \) 个数据进行比拟，顺次类推，实现第一轮排序。
  3. 而后，它变成 \(n/4 \) 个序列，并再次进行排序。
  4. 一直反复上述过程，随着程序的缩小，最终变为一个，整个排序实现。
Python 中的 Shell 排序实现
def shell_sort(items):
    sublistcount = len(items) // 2
    while sublistcount > 0:
        for start in range(sublistcount):
            gap_insertion_sort(items, start, sublistcount)
        sublistcount = sublistcount // 2
    return items

def gap_insertion_sort(items, start, gap):
    for i in range(start+gap, len(items), gap):
        currentvalue = items[i]
        position = i
        while position >= gap and items[position-gap] > currentvalue:
            items[position] = items[position-gap]
            position = position-gap
        items[position] = currentvalue

items = [6,20,8,19,56,23,87,41,49,53]
print(shell_sort(items))
JavaScript 中的 Shell 排序
function shellSort(items) {let sublistcount = Math.floor(items.length / 2);
    while(sublistcount > 0) {for(let start = 0; start < sublistcount; start++) {gapInsertionSort(items, start, sublistcount);
        }
        sublistcount = Math.floor(sublistcount / 2);
    }
    return items;
}

function gapInsertionSort(items, start, gap) {for(let i = start + gap; i < items.length; i += gap) {let currentValue = items[i];
        let position = i;
        while(position >= gap && items[position - gap] > currentValue) {items[position] = items[position - gap];
            position = position - gap;
        }
        items[position] = currentValue;
    }
}


let items = [6, 20, 8, 19, 56, 23, 87, 41, 49, 53];
console.log(shellSort(items));

归并排序

归并排序（Merge sort）的根本思维是将输出列表一分为二，应用归并排序递归地对每一半进行排序，而后将排序后的两半合并在一起。合并步骤是通过反复比拟每一半的第一个元素并将两者中较小的一个增加到排序列表中来执行的，反复此过程，直到所有元素都被从新合并在一起。

归并排序的历史

归并排序由 John von Neumann 于 1945 年创造，作为一种基于比拟的排序算法，其工作原理是将输出列表划分为更小的子列表，递归地对这些子列表进行排序，而后将它们合并回一起以生成最终的排序列表.

归并排序的长处

归并排序在最坏状况下的工夫复杂度为 \(O(n \log n) \)，这使得它比冒泡排序、插入排序或抉择排序等其余风行的排序算法更高效。

归并排序也是一种稳固排序算法，这意味着它保留了相等元素的绝对程序。

归并排序的毛病

归并排序在内存应用方面有一些毛病，该算法在划分步骤中须要额定的内存来存储列表的两半，以及在合并过程中须要额定的内存来存储最终排序的列表。在对十分大的列表进行排序时，这可能是一个问题。

归并排序的用例

归并排序是一种通用排序算法，能够并行化以对大型数据集进行排序和外排序（相似疾速排序和桶排序），它也罕用作更简单算法（如冒泡排序和插入排序）的构建块。

  • 稳固排序 归并排序的稳固排序意味着它保留了相等元素的绝对程序。这使得它在保护相等元素的程序很重要的状况下十分有用，例如在金融应用程序中或呈现于可视化目标对数据进行排序时。
  • 实现二进制搜寻 它用于无效地搜寻排序列表中的特定元素，因为它依赖于排序的输出。归并排序可用于无效地对二分搜寻和其余相似算法的输出进行排序。

归并排序的实现

  1. 应用递归将列表拆分为较小的排序子列表。
  2. 将子列表从新合并在一起，在合并时对我的项目进行比拟和排序。
Python 中的归并排序实现
def merge_sort(items):
    if len(items) <= 1:
        return items

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

    left = merge_sort(left)
    right = merge_sort(right)

    return merge(left, right)

def merge(left, right):
    merged = []
    left_index = 0
    right_index = 0

    while left_index < len(left) and right_index < len(right):
        if left[left_index] > right[right_index]:
            merged.append(right[right_index])
            right_index += 1
        else:
            merged.append(left[left_index])
            left_index += 1

    merged += left[left_index:]
    merged += right[right_index:]

    return merged

items = [6,20,8,19,56,23,87,41,49,53]
print(merge_sort(items))
JavaScript 中的归并排序
function mergeSort(items) {if(items.length <= 1) return items
    const mid = Math.floor(items.length / 2)
    const left = items.slice(0, mid)
    const right = items.slice(mid)
    return merge(mergeSort(left), mergeSort(right))
}

function merge(left, right) {const merged = []
    let leftIndex = 0
    let rightIndex = 0
    while(leftIndex < left.length && rightIndex < right.length) {if(left[leftIndex] > right[rightIndex]) {merged.push(right[rightIndex])
            rightIndex++
        } else {merged.push(left[leftIndex])
            leftIndex++
        }
    } 
    return merged.concat(left.slice(leftIndex)).concat(right.slice(rightIndex))
}

let items = [6, 20, 8, 19, 56, 23, 87, 41, 49, 53]
console.log(mergeSort(items))

抉择排序

抉择排序（Selection sort）从列表的未排序局部中，反复抉择最小的元素，并将其与未排序局部的第一个元素替换，这个过程始终继续到整个列表排序实现。

红色是以后最小值，黄色是排序列表，蓝色是以后我的项目。

抉择排序的历史

抉择排序是一种简略直观的排序算法，自计算机科学晚期就已存在。相似的算法很可能是由钻研人员在 1950 年代独立开发的。

它是最早开发的排序算法之一，并且依然是用于教育目标和简略排序工作的风行算法。

抉择排序的长处

抉择排序用于某些应用程序中，在这些应用程序中，简略性和易用性比效率更重要。它也可用作向学生介绍排序算法及其属性的教学工具，因为它易于了解和实现。

抉择排序的毛病

只管抉择排序很简略，但与归并排序或疾速排序等其余排序算法相比，它的效率不是很高。它在最坏状况下的工夫复杂度为 \(O(n^2) \)，并且对大型列表进行排序可能须要很长时间。

抉择排序也不是稳固的排序算法，这意味着它可能无奈保留相等元素的程序。

抉择排序的用例

抉择排序与冒泡排序和插入排序相似，可用于小型数据集排序，其简略性也使其成为排序算法教学和学习的有用工具。其余用处包含：

  • 对内存无限的数据进行排序 它只须要恒定数量的额定内存来执行排序，这使得它在内存应用受限的状况下很有用。
  • 对具备惟一值的数据进行排序 它不依赖于大部分排序的输出，这使其成为具备惟一值的数据集的不错抉择，而其余排序算法可能必须执行额定的查看或优化。

抉择排序的实现

  1. 遍历列表，抉择最小的项。
  2. 将最小的项与以后地位的项进行替换。
  3. 对列表的其余部分反复上述过程。
在 Python 中的抉择排序
def selection_sort(items):
    for i in range(len(items)):
        min_idx = i
        for j in range(i+1, len(items)):
            if items[min_idx] > items[j]:
                min_idx = j
        items[i], items[min_idx] = items[min_idx], items[i]
    return items

items = [6,20,8,19,56,23,87,41,49,53]
print(selection_sort(items))
在 JavaScript 中的抉择排序
function selectionSort(items) {
    let minIndex;
    for(let i = 0; i < items.length; i++) {
         minIndex = i;
         for(let j = i + 1; j < items.length; j++) {if(items[j] < items[minIndex]) {minIndex = j;}
         }
         let temp = items[i];
         items[i] = items[minIndex];
         items[minIndex] = temp;
    }
    return items
}

let items = [6, 20, 8, 19, 56, 23, 87, 41, 49, 53];
console.log(selectionSort(items));

基数排序

基数排序（Radix sort）是一种非比拟型整数排序算法，其原理是将整数按位数切割成不同的数字，而后按每个位数别离比拟。因为整数也能够表白字符串（比方名字或日期）和特定格局的浮点数，所以基数排序也不是只能利用于整数。

其最坏状况下的性能为 \({O(w\cdot n)} \)，其中 \(n \) 是密钥数量，\(w \) 是密钥长度。

基数排序的历史

基数排序由 Herman Hollerith 在 19 世纪末首次引入，作为一种对穿孔卡片上的数据进行高效排序的办法，其中每一列代表数据中的一个数字。

起初，它被 20 世纪中期的几位钻研人员改编并推广，用于对二进制数据进行排序，按二进制示意中的每一个比特对数据进行分组。但它也被用来对字符串数据进行排序，在排序中每个字符都被视为一个数字。

近年来，基数排序作为并行和分布式计算环境中的一种排序算法再次受到关注，因为它很容易并行化，并且能够用来以分布式形式对大数据集进行排序。

IBM 的一种卡片分类器，对一大组穿孔卡片进行基数排序。图片起源：Wikimedia Commons, Public Domain.

基数排序的长处

基数排序是一种线性工夫排序算法，这意味着它的工夫复杂度与输出数据的大小成正比。这使它成为对大型数据集进行排序的无效算法，只管它可能不如其余对较小数据集的排序算法无效。

它的线性工夫复杂性和稳定性使其成为对大型数据集进行排序的有用工具，它的可并行性使其对分布式计算环境中的数据排序十分有用。

基数排序也是一种稳固的排序算法，这意味着它保留了相等元素的绝对程序。

基数排序的用例

基数排序可用于须要对大型数据集进行高效排序的各种应用程序。它对字符串数据和定长键的排序特地有用，也可用于并行和分布式计算环境中。

  • 并行处理 基数排序通常是对大数据集进行排序的首选（优于归并排序、疾速排序和桶排序）。而且和桶排序一样，基数排序能够无效地对字符串数据进行排序，这使得它适宜于自然语言解决利用。
  • 对有固定长度键的数据进行排序 当对有固定长度键的数据进行排序时，基数排序特地无效，因为它能够通过一次查看每个键的数字来执行排序。

基数排序的实现

  1. 比拟列表中的每一项的数字。
  2. 依据数字对项进行分组。
  3. 按大小对各组进行排序。
  4. 对每个组进行递归排序，直到每个项都处于正确的地位。
Python 中的基数排序
def radix_sort(items):
    max_length = False
    tmp, placement = -1, 1

    while not max_length:
        max_length = True
        buckets = [list() for _ in range(10)]

        for i in items:
            tmp = i // placement
            buckets[tmp % 10].append(i)
            if max_length and tmp > 0:
                max_length = False

        a = 0
        for b in range(10):
            buck = buckets[b]
            for i in buck:
                items[a] = i
                a += 1

        placement *= 10
    return items

items = [6,20,8,19,56,23,87,41,49,53]
print(radix_sort(items))
JavaScript 中的基数排序
function radixSort(items) {
    let maxLength = false;
    let tmp = -1;
    let placement = 1;
    while(!maxLength) {
        maxLength = true;
        let buckets = Array.from({length: 10}, () => []);
        for(let i = 0; i < items.length; i++) {tmp = Math.floor(items[i]/placement);
            buckets[tmp % 10].push(items[i]);
            if(maxLength && tmp > 0) {maxLength = false;}
        }
        let a = 0;
        for(let b = 0; b < 10; b++) {let buck = buckets[b]
            for(let j = 0; j < buck.length; j++) {items[a] = buck[j];
                a++;
            }
        }
        placement *= 10;
    }
    return items;
}


let items = [6, 20, 8, 19, 56, 23, 87, 41, 49, 53];
console.log(radixSort(items));

梳排序

梳排序（Comb sort）比拟相距肯定间隔的元素对，如果它们乱序则替换它们。对之间的间隔最后设置为正在排序的列表的大小，而后在每次通过时缩小一个因子（称为“膨胀因子”），直到达到最小值 \(1 \)，反复此过程，直到列表齐全排序。

梳排序算法相似于冒泡排序算法，但比拟元素之间的差距更大，这个更大的差距容许更大的值更快地挪动到列表中的正确地位。

梳排序的历史

梳状排序算法是一种绝对较新的排序算法，由 Włodzimierz Dobosiewicz 和 Artur Borowy 于 1980 年首次提出。该算法的灵感来自应用梳子理顺缠结的头发的想法，它应用相似的过程理顺未排序值的列表。

梳排序的长处

梳排序在最坏状况下的工夫复杂度为 \(O(n^2) \)，但在实践中，因为应用了膨胀因子，它通常比其余 \(O(n ^2) \) 排序算法（如冒泡排序）更快。膨胀因子使算法可能疾速将大值移向正确的地位，从而缩小对列表进行齐全排序所需的次数。

梳排序的用例

梳排序是一种绝对简略且高效的排序算法，在各种利用中有很多用例。

  • 对具备大范畴值的数据进行排序 在比拟元素之间应用更大的间隙容许更大的值更快的挪动到它们在列表中的正确地位。
  • 在实时应用程序中对数据进行排序 作为一种稳固的排序算法，梳排序保留了相等元素的绝对程序。这对于在须要保留相等元素程序的实时应用程序中的数据排序十分有用。
  • 在内存受限的环境中对数据进行排序 梳排序不须要额定的内存来对数据进行排序，这对于在没有额定内存或内存受限的环境中对数据进行排序十分有用。

梳排序的实现

  1. 从项之间较大的间距（\(gap \)）开始。
  2. 比拟间距末端的项，如果程序错则替换它们。
  3. 放大间距并反复该过程，直到 \(gap \) 为 \(1 \)。
  4. 最初对残余的项进行冒泡排序。
Python 中的梳排序
def comb_sort(items):
    gap = len(items)
    shrink = 1.3
    sorted = False
    while not sorted:
        gap //= shrink
        if gap <= 1:
            sorted = True
        else:
            for i in range(len(items)-gap):
                if items[i] > items[i+gap]:
                    items[i],items[i+gap] = items[i+gap],items[i]
    return bubble_sort(items)

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

items = [6,20,8,19,56,23,87,41,49,53]
print(comb_sort(items))
JavaScript 中的梳排序
function combSort(items) {
    let gap = items.length;
    let shrink = 1.3;
    let sorted = false;
    while(!sorted) {gap = Math.floor(gap / shrink);
        if(gap <= 1) {sorted = true;} else {for(let i = 0; i < items.length - gap; i++) {if(items[i] > items[i + gap]) {[items[i], items[i+gap]] = [items[i+gap], items[i]]
                }
            }
        }
    }
    return bubbleSort(items);
}

function bubbleSort(items) {
    let swapped;
    do {
        swapped = false;
        for(let i = 0; i < items.length - 1; i++) {if(items[i] > items[i+1]) {[items[i], items[i+1]] = [items[i+1], items[i]]
                swapped = true;
            }
        }
    } while(swapped)
    return items;
}


let items = [6, 20, 8, 19, 56, 23, 87, 41, 49, 53];
console.log(combSort(items));

Timsort

Timsort 是一种混合稳固的排序算法，源自归并排序和插入排序，旨在较好地解决真实世界中各种各样的数据。

它的工作原理是将输出数据分成更小的子数组，而后应用插入排序对这些子数组进行排序，而后应用归并排序将这些已排序的子数组组合起来，生成一个齐全排序的数组。

Timsort 的最坏状况工夫复杂度为 \(O(n \log n) \)，这使得它能够高效的对大型数据集进行排序。它也是一种稳固的排序算法，这意味着它保留了相等元素的绝对程序。

Timsort 的历史

Timsort 由 Tim Peters 于 2002 年开发，用于 Python 编程语言。它是一种混合排序算法，联合了插入排序和归并排序技术，旨在无效地对各种不同类型的数据进行排序。

因为它在解决不同类型数据方面的效率和多功能性，它起初被其余几种编程语言采纳，包含 Java 和 C#。

Timsort 排序的长处

Timsort 的一个要害个性是它可能无效地解决不同类型的数据，它通过检测”运行（runs）” 来做到这一点，runs 是曾经排序的元素序列。而后，Timsort 以一种形式组合这些 runs，以最大限度地缩小生成齐全排序数组所需的比拟和替换次数。

Timsort 的另一个重要个性是它可能解决局部排序的数据。在这种状况下，Timsort 能够检测到局部排序的 runs，并应用插入排序对其进行疾速排序，从而缩小对数据进行齐全排序所需的工夫。

Timsort 排序的用例

作为一种高级算法，Timsort 可用于在内存受限的零碎上对数据进行排序。

在编程语言排序 Timsort 因为其解决不同类型数据的效率和能力，常常被用作这些语言中的默认排序算法。
对真实世界的数据进行排序 Timsort 在对可能局部排序或蕴含已排序子数组的实在数据进行排序时特地无效，因为它可能检测这些 runs 并应用插入排序来疾速排序，从而缩小了对数据进行齐全排序所需的工夫。
对不同类型的数据进行排序 它旨在无效地解决不同类型的数据，包含数字、字符串和自定义对象。它能够检测雷同类型的数据 runs，并应用归并排序无效地组合它们，从而缩小所需的比拟和替换次数。

Timsort 排序的实现

  1. 将一个未排序的类别分成更小的、已排序的子列表。
  2. 合并子列表以造成更大的排序列表。
  3. 反复这个过程，直到整个列表排序结束。
Python 中的 Timsort 实现
def insertion_sort(arr, left=0, right=None):
    if right is None:
        right = len(arr) - 1

    for i in range(left + 1, right + 1):
        key_item = arr[i]
        j = i - 1
        while j >= left and arr[j] > key_item:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key_item

    return arr

def merge(left, right):
    if not left:
        return right

    if not right:
        return left

    if left[0] < right[0]:
        return [left[0]] + merge(left[1:], right)

    return [right[0]] + merge(left, right[1:])

def timsort(arr):
    min_run = 32
    n = len(arr)

    for i in range(0, n, min_run):
        insertion_sort(arr, i, min((i + min_run - 1), n - 1))

    size = min_run
    while size < n:
        for start in range(0, n, size * 2):
            midpoint = start + size - 1
            end = min((start + size * 2 - 1), (n-1))
            merged_array = merge(left=arr[start:midpoint + 1],
                right=arr[midpoint + 1:end + 1]
            )
            arr[start:start + len(merged_array)] = merged_array

        size *= 2

    return arr

items = [6,20,8,19,56,23,87,41,49,53]
print(timsort(items))
JavaScript 中的 Timsort 实现
function timsort(arr) {
  const minRun = 32;
  const n = arr.length;

  for (let i = 0; i < n; i += minRun) {insertionSort(arr, i, Math.min(i + minRun - 1, n - 1));
  }

  let size = minRun;
  while (size < n) {for (let start = 0; start < n; start += size * 2) {
      const midpoint = start + size - 1;
      const end = Math.min(start + size * 2 - 1, n - 1);
      const merged = merge(arr.slice(start, midpoint + 1),
        arr.slice(midpoint + 1, end + 1)
      );
      arr.splice(start, merged.length, ...merged);
    }
    size *= 2;
  }

  return arr;
}

function insertionSort(arr, left = 0, right = arr.length - 1) {for (let i = left + 1; i <= right; i++) {const keyItem = arr[i];
    let j = i - 1;
    while (j >= left && arr[j] > keyItem) {arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = keyItem;
  }
  return arr;
}

function merge(left, right) {
  let i = 0;
  let j = 0;
  const merged = [];

  while (i < left.length && j < right.length) {if (left[i] < right[j]) {merged.push(left[i]);
      i++;
    } else {merged.push(right[j]);
      j++;
    }
  }

  return merged.concat(left.slice(i)).concat(right.slice(j));
}

let items = [6, 20, 8, 19, 56, 23, 87, 41, 49, 53];
console.log(timsort(items));

比拟所有排序算法

请留神，表中列出的工夫复杂度和空间复杂度是 最坏状况下 的复杂度，理论性能可能因具体实现和输出数据而异。

算法 工夫复杂度 空间复杂度 就地排序 稳固排序 自适应排序
冒泡排序 \(O(n^2) \) \(O(1) \) 是 是 否
疾速排序 \(O(n \log n) \) \(O(\log n) \) 是 否 是
桶排序 \(O(n+k) \) \(O(n+k) \) 否 是 否
Shell 排序 \(O(n \log n) \) \(O(1) \) 是 否 否
归并排序 \(O(n \log n) \) \(O(n) \) 否 是 否
抉择排序 \(O(n^2) \) \(O(1) \) 是 否 是
基数排序 \(O(w \cdot n \)) \(O(w+n) \) 否 是 否
梳排序 \(O(n^2) \) \(O(1) \) 是 否 是
Timesort \(O(n \log n) \) \(O(n) \) 是 是 是

哪些是最罕用的排序算法？

最罕用的排序算法可能是疾速排序，它宽泛用于许多编程语言，包含 C、C++、Java 和 Python，以及许多软件应用程序和库。疾速排序因其在解决不同类型数据时的效率和通用性而受到青眼，并且常常被用作编程语言和软件框架中的默认排序算法。

然而，归并排序和 Timsort 等其余排序算法因为其效率和独特的个性也罕用于各种应用程序。

最初

学习算法能够晋升本人的逻辑能力，真正重要的是享受「学」的过程。尽管不肯定就能间接用上，然而能在编程过程中思路更加清晰，工程能力也会更好。

参考：

  • Lucero del Alba – 10 Best Sorting Algorithms Explained（特别感谢）
  • wikipedia – Sorting algorithm

正文完
算法
发表至： 算法
2023-05-18
 0
关于c++:leetcode笔记215-数组中的第K个最大元素
原地Hash
关于算法:算法学习之路
关于算法:CSC-413学习情况