算法可视化：从入门到精通 10 大排序算法
在本文中，我们将通过动图可视化加文字的形式，循序渐进全面介绍不同类型的算法及其用途（包括原理、优缺点及使用场景）并提供 Python 和 JavaScript 两种语言的示例代码。除此之外，每个算法都会附有一些技术说明，比如使用大 \(O\) 符号来分析不同算法的时间复杂度和空间复杂度等，也提到了一些多数人都很容易理解的一些高级概述。
篇幅很长，耐心读完它，您会受益匪浅。
提要
什么是排序算法？
- 排序算法有什么用？
- 为什么排序算法如此重要？
- 算法的评价标准
数据结构中不同类型的排序算法
- 基于比较的排序算法
- 基于非比较的排序算法
- 就地排序算法
- 稳定的排序算法
- 自适应排序算法
您需要了解的 10 大排序算法
- 冒泡排序
- 插入排序
- 快速排序
- 桶排序
- 壳排序
- 归并排序
- 选择排序
- 基数排序
- 梳排序
- 排序
- 比较所有排序算法
- 什么是最常见的排序算法？
什么是排序算法？
从本质上讲，排序算法是一种计算机程序，它将数据组织成特定的顺序，例如字母顺序或数字顺序，通常是升序或降序。
排序算法有什么用？
排序算法主要用于以高效的方式重新排列大量数据，以便更容易地对其进行搜索和操作。它们还用于提高搜索和合并等其他算法的效率，这些算法的操作依赖于排序数据。
为什么排序算法如此重要？
排序算法用于按特定顺序组织数据，这使得搜索、访问和分析更加容易。在许多应用中，排序是数据处理流程的关键部分，排序算法的效率对系统的整体性能产生重大影响。
- 在数据库中 排序用于按特定顺序检索记录，例如按日期、字母顺序或数字顺序。这使用户可以快速找到他们需要的数据，而无需手动搜索大量未分类的数据。
- 在搜索引擎中 按相关性顺序排列搜索结果。通过以这种方式对结果进行排序，用户可以快速找到他们想要的信息，而不必筛选不相关的结果。
- 在许多科学和工程应用中 研究人员可以进行数据分析和模拟，以深入了解复杂系统，并对未来行为做出更准确的预测。
算法的评价标准
评估一个排序算法的好坏，通常依照以下标准进行评价：
- 时间复杂度 是指在计算机科学与工程领域完成一个算法所需要的时间，是衡量一个算法优劣的重要参数，使用大 \(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 次。
然而，它很容易理解和实现，并且经常被用作排序的入门以及更复杂算法的构建块，但如今它在实践中很少被使用。
冒泡排序的用例
冒泡排序是一种简单的的算法，可用于对小型列表或元素数组进行排序。它易于实现和理解，因此可以在简单和清晰比性能更重要的情况下使用。
- 教育目的 它经常被用在计算机科学课程中，作为简单排序算法的一个例子。学生们可以通过学习冒泡排序来了解基本的排序技术，并通过学习冒泡排序来了解算法的工作原理。
- 对小数据集进行排序 它可用来对最多几百个元素的小型数据集进行排序。在性能不是关键问题的情况下，冒泡排序可以成为对小列表进行排序的一种快速而简单的方法。
- 预排序数据 它可以用作更复杂的排序算法的一个初步步骤。例如，如果数据已经被部分排序，在运行更复杂的算法之前，可以用冒泡排序来进一步排序数据。
- 构建更复杂算法的模块 它通常与归并排序或快速排序结合使用，并使用插入排序对小型子数组进行排序，因为这些其他算法可以在更大的数据集上表现更好的性能。
冒泡排序的实现
- 使用嵌套循环来遍历各个项。
- 比较列表中的相邻的两项。
- 如果顺序不对，就进行交换。
- 直到列表被排序完成。
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) \) 。但与冒泡排序不同的是，
插入排序可用于对数据集进行就地排序，这意味着它不需要额外的内存来存储中间结果。
插入排序的用例
插入排序简单高效，常用于输入数据已经排序或输入数据规模较小的情况。它还用于对小型数据集进行排序和构建更复杂算法的块，就像冒泡排序一样。
- 部分排序的数据 它非常适合数据已经部分排序的情况。在这种情况下，算法可以快速地将新元素插入到正确的位置，而不需要复杂的排序操作。
- 在线分拣 它通常用于输入数据事先未知的在线排序应用程序中。在这些情况下，算法可以在收到输入数据时对其进行增量排序。
- 自适应排序 插入排序是自适应排序的候选者，因为它可以利用输入数据中的现有顺序。随着输入数据变得更加有序，算法的性能也会提高。
插入排序的实现
- 取一个未排序的列表，选择第一个项作为 "枢轴（pivot）"。
- 遍历列表，将枢轴插入到排序后列表中的正确位置。
- 对列表中的下一个项重复这一过程。
- 继续下去，直到列表排序完毕。
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）是一种流行的分而治之排序算法，其基于将数组划分为两个子数组的原则——一个包含小于“枢轴”元素的元素，另一个包含大于“枢轴”元素的元素，然后递归地对这两个子数组进行排序。
快速排序的基本步骤包括：
- 从数组中选择一个“枢轴”元素。
- 将数组分成两个子数组，一个包含小于枢轴的元素，另一个包含大于枢轴的元素。
- 使用快速排序递归地对两个子数组进行排序。
- 合并两个排序的子数组。
快排的历史
快速排序由 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 矩阵中的数据进行排序，然后对其进行转换以生成压缩数据。
快速排序的实现
- 选取“枢轴”点，最好是中位数，将列表分为两部分。
- 快速对左侧部分和右侧部分进行排序。
- 继续直到列表排序完毕。
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) \) 下限的影响。
桶排序的基本步骤包括：
- 设置一个定量的数组当作空桶子。
- 遍历列表，并且把项一个一个放到对应的桶子去。
- 对每个不是空的桶子进行排序。
- 从不是空的桶子里把项再放回原来的列表中。
桶排序的历史
桶排序的实现早在 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) \) 。此外，它需要额外的内存来存储桶，这对于非常大的数据集来说可能是个问题。
桶排序的用例
就像快速排序一样，桶排序可以很容易地并行化并用于外排序，但是桶排序在处理均匀分布的数据时特别有用。
- 对浮点数进行排序 在这种情况下，划分为固定数量的桶区间，每个桶代表输入数据的一个子区间。然后将这些数字放入相应的桶中，并使用另一种算法（例如插入排序）进行排序。最后，排序后的数据被连接成一个数组。
- 对字符串进行排序 根据字符串的第一个字母分组到桶中。然后使用另一种算法对每个桶中的字符进行排序，或递归的使用桶排序。对字符串中的每个后续字母重复此过程，直到整个集合排序完毕。
- 直方图生成 这可用于生成数据的直方图，用于表示一组值的频率分布。在这种情况下，将数据范围划分为固定数量的桶，并统计每个桶中值的数量。生成的直方图可用于可视化数据的分布。
桶排序的实现
- 将项的列表拆分为一定数量的“桶”。
- 每个桶使用不同排序算法进行排序。
- 然后将这些桶合并回一个排序列表中。
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 排序的实现
- 将 \( n \) 个元素的数组划分为 \( n/2 \) 个子序列。
- 第一个数据和第 \( n/2 \) + \( 1 \) 个数据进行比较，第 \( 2 \) 个数据和第 \( n/2 \) + \( 2 \) 个数据进行比较，依次类推，完成第一轮排序。
- 然后，它变成 \( n/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) \) ，这使得它比冒泡排序、插入排序或选择排序等其他流行的排序算法更高效。
归并排序也是一种稳定排序算法，这意味着它保留了相等元素的相对顺序。
归并排序的缺点
归并排序在内存使用方面有一些缺点，该算法在划分步骤中需要额外的内存来存储列表的两半，以及在合并过程中需要额外的内存来存储最终排序的列表。在对非常大的列表进行排序时，这可能是一个问题。
归并排序的用例
归并排序是一种通用排序算法，可以并行化以对大型数据集进行排序和外排序（类似快速排序和桶排序），它也常用作更复杂算法（如冒泡排序和插入排序）的构建块。
- 稳定排序 归并排序的稳定排序意味着它保留了相等元素的相对顺序。这使得它在维护相等元素的顺序很重要的情况下非常有用，例如在金融应用程序中或出现于可视化目的对数据进行排序时。
- 实现二进制搜索 它用于有效地搜索排序列表中的特定元素，因为它依赖于排序的输入。归并排序可用于有效地对二分搜索和其他类似算法的输入进行排序。
归并排序的实现
- 使用递归将列表拆分为较小的排序子列表。
- 将子列表重新合并在一起，在合并时对项目进行比较和排序。
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) \)，并且对大型列表进行排序可能需要很长时间。
选择排序也不是稳定的排序算法，这意味着它可能无法保留相等元素的顺序。
选择排序的用例
选择排序与冒泡排序和插入排序类似，可用于小型数据集排序，其简单性也使其成为排序算法教学和学习的有用工具。其他用途包括：
- 对内存有限的数据进行排序 它只需要恒定数量的额外内存来执行排序，这使得它在内存使用受限的情况下很有用。
- 对具有唯一值的数据进行排序 它不依赖于大部分排序的输入，这使其成为具有唯一值的数据集的不错选择，而其他排序算法可能必须执行额外的检查或优化。
选择排序的实现
- 遍历列表，选择最小的项。
- 将最小的项与当前位置的项进行交换。
- 对列表的其余部分重复上述过程。
在 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.
基数排序的优点
基数排序是一种线性时间排序算法，这意味着它的时间复杂度与输入数据的大小成正比。这使它成为对大型数据集进行排序的有效算法，尽管它可能不如其他对较小数据集的排序算法有效。
它的线性时间复杂性和稳定性使其成为对大型数据集进行排序的有用工具，它的可并行性使其对分布式计算环境中的数据排序非常有用。
基数排序也是一种稳定的排序算法，这意味着它保留了相等元素的相对顺序。
基数排序的用例
基数排序可用于需要对大型数据集进行高效排序的各种应用程序。它对字符串数据和定长键的排序特别有用，也可用于并行和分布式计算环境中。
- 并行处理 基数排序通常是对大数据集进行排序的首选（优于归并排序、快速排序和桶排序）。而且和桶排序一样，基数排序可以有效地对字符串数据进行排序，这使得它适合于自然语言处理应用。
- 对有固定长度键的数据进行排序 当对有固定长度键的数据进行排序时，基数排序特别有效，因为它可以通过一次检查每个键的数字来执行排序。
基数排序的实现
- 比较列表中的每一项的数字。
- 根据数字对项进行分组。
- 按大小对各组进行排序。
- 对每个组进行递归排序，直到每个项都处于正确的位置。
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) \) 排序算法（如冒泡排序）更快。收缩因子使算法能够快速将大值移向正确的位置，从而减少对列表进行完全排序所需的次数。
梳排序的用例
梳排序是一种相对简单且高效的排序算法，在各种应用中有很多用例。
- 对具有大范围值的数据进行排序 在比较元素之间使用更大的间隙允许更大的值更快的移动到它们在列表中的正确位置。
- 在实时应用程序中对数据进行排序 作为一种稳定的排序算法，梳排序保留了相等元素的相对顺序。这对于在需要保留相等元素顺序的实时应用程序中的数据排序非常有用。
- 在内存受限的环境中对数据进行排序 梳排序不需要额外的内存来对数据进行排序，这对于在没有额外内存或内存受限的环境中对数据进行排序非常有用。
梳排序的实现
- 从项之间较大的间距（\( gap \)）开始。
- 比较间距末端的项，如果顺序错则交换它们。
- 缩小间距并重复该过程，直到 \( gap \) 为 \( 1 \)。
- 最后对剩余的项进行冒泡排序。
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 排序的实现
- 将一个未排序的类别分成更小的、已排序的子列表。
- 合并子列表以形成更大的排序列表。
- 重复这个过程，直到整个列表排序完毕。
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 等其他排序算法由于其效率和独特的特性也常用于各种应用程序。
最后
学习算法可以提升自己的逻辑能力，真正重要的是享受「学」的过程。虽然不一定就能直接用上，但是能在编程过程中思路更加清晰，工程能力也会更好。
参考：