排序算法的时间复杂度

排序算法的时间复杂度展示了排序技术在输入量相关的操作次数方面的表现。找到复杂度的关键在于，它被用来根据不同的数据量和资源需求，在各种排序技术中找到最佳的排序算法。时间复杂度的优化可以减少所需的计算量。因此，在处理大量数据时，可以减少时间消耗。

什么是时间复杂度？

复杂度没有正式的定义。它只是定义了任务执行的效率。

算法的时间复杂度表明，如果我们改变输入数据的量，时间的消耗会如何变化。请注意，对于算法或程序，为给定输入生成输出的总时间并不是时间复杂度。时间复杂度主要讨论基于输入大小的时间增长。

在计算机科学中，算法的时间复杂度通常用大O符号表示。

复杂度类型

在数据结构中，有两种复杂度可以确定算法的效率。它们是

空间复杂度：空间复杂度是程序执行所消耗的总内存。

时间复杂度：它被定义为预期的指令执行次数，而不是总的执行时间。由于时间是一个依赖现象，时间复杂度可能会因处理器速度、使用的编译器等外部因素而异。

为什么需要时间复杂度？

• 它独立于硬件比较算法。
• 它帮助我们选择最有效的解决方案。

常见时间复杂度

O(1)：表示常数时间。时间复杂度O(1)通常意味着算法将具有恒定的时间，无论输入大小如何。哈希表是常数时间的完美示例。

O(log n)：算法花费的时间与输入大小的对数成正比，即O(log n)。这意味着如果输入大小增加，则算法执行的时间消耗也随输入数组大小的对数而增加。

O(n)：也称为线性时间复杂度。它表示当输入数组的大小线性增加时，生成输出所需的时间消耗也线性增加。换句话说，如果我们三倍输入大小，算法执行的时间消耗也将增加三倍。

O(n²)：O(n²)时间复杂度表示，如果输入大小增加，算法执行的时间消耗会二次方增长。通常，嵌套循环会显示O(n2)时间复杂度，其中每个元素都与每个其他元素进行比较。

O(n log n)：时间复杂度O(n log n)是一种混合增长模式——比O(n²)快，但比O(n)或O(log n)慢。它通常适用于高效算法，尤其是排序算法。让我们分解一下。

• n是输入大小（例如数组中的元素数量）。
• log n 来自于分治法，其中输入被反复减半。
• 在一起，n log n 表示我们对每个 n 个元素执行 log n 次对数运算。

其中 n 是输入大小。

常用排序算法的时间复杂度

冒泡排序的时间复杂度

冒泡排序，也称为下沉排序，是一种简单的排序算法，它逐个遍历给定列表。它将当前元素与下一个元素进行比较，并在需要时进行值交换。列表的遍历将继续进行，直到不需要进行任何交换，这表明给定列表已完全排序。该算法是一种比较排序，之所以称为冒泡排序，是因为较大的元素先冒出来，并在排序数组中找到自己的位置。

• 最坏情况时间复杂度：O(n²)
• 平均情况时间复杂度：O(n²)
• 最佳情况时间复杂度：O(n)

当给定列表已排序时，会出现最佳情况。这就是为什么在输入量非常大时不考虑冒泡排序。

阅读更多 冒泡排序算法

插入排序的时间复杂度

插入排序的工作方式与手中扑克牌的排序方式相似。假设第一张牌已经洗好，然后我们选择一张未洗的牌。如果选择的未洗牌大于第一张牌，它将被放在右边；否则，它将被放在左边。同样，所有未洗的牌都被拿起并放到它们的确切位置。

• 最坏情况时间复杂度：O(n²)
• 平均情况时间复杂度：O(n²)
• 最佳情况时间复杂度：O(n)

当给定列表已排序时，会出现最佳情况。最坏的情况发生在给定列表按降序排列，而我们要按升序排列其元素时。由于最坏和平均情况的时间复杂度均为二次方，因此插入排序不适用于大型数据集。

阅读更多 插入排序算法

选择排序的时间复杂度

在选择排序中，在每次传递中，从数组的未排序元素中选择最小值，并将其插入到数组中的适当位置。它也是最简单的算法。它是一种原地比较排序算法。在此算法中，数组被分为两部分；第一部分是已排序部分，另一部分是未排序部分。最初，数组的已排序部分为空，未排序部分是给定的数组。已排序部分放在左边，未排序部分放在右边。

• 最坏情况时间复杂度：O(n²)
• 平均情况时间复杂度：O(n²)
• 最佳情况时间复杂度：O(n)

与冒泡排序类似，选择排序也有同样的缺点。它不适合对大型数据集进行排序。选择排序之所以受到青睐，是因为它简单，并且在辅助内存受限的情况下很有用。

阅读更多 选择排序算法

快速排序的时间复杂度

快速排序是一种利用分治技术的排序算法。它选择一个基准元素，并将其放在已排序数组的适当位置。

• 最坏情况时间复杂度：O(n²)
• 平均情况时间复杂度：O(n log n)
• 最佳情况时间复杂度：O(n log n)

当枢轴元素将给定列表分成两半时，会出现最佳情况。当枢轴元素可能将给定列表分成两半，也可能不分成两半时，会出现平均情况。当给定列表已排序时，会出现最坏情况。

阅读更多 快速排序算法

归并排序的时间复杂度

归并排序基于分治法。归并排序首先递归地将给定列表分成两半。然后，它递归地对两半进行排序，然后将它们合并以获得排序列表。

• 最坏情况时间复杂度：O(n log n)
• 平均情况时间复杂度：O(n log n)
• 最佳情况时间复杂度：O(n log n)

我们可以看到，在所有情况下，时间复杂度都是O(n log(n))。因此，这种排序算法用于对大型数据集进行排序。

阅读更多 归并排序算法

堆排序的时间复杂度

堆排序使用一种基于二叉堆数据结构的比较排序技术。也可以将其视为选择排序的优化，在选择排序中，我们首先找到最小（或最大）元素，将其与第一个（或最后一个）元素交换，然后对其余元素重复相同的过程。在堆排序中，使用二叉堆以便我们能够快速找到并移动最大元素。

• 最坏情况时间复杂度：O(n log n)
• 平均情况时间复杂度：O(n log n)
• 最佳情况时间复杂度：O(n log n)

我们可以看到，在所有情况下，时间复杂度都是O(n log(n))。因此，即使有大量元素，对元素进行排序的整体性能也很好。

阅读更多 堆排序算法

基数排序的时间复杂度

基数排序的过程类似于按字母顺序对学生姓名进行排序。在这种情况下，由于英语字母有26个字母，因此形成26个基数。在第一次传递中，学生姓名根据其姓名的第一个字母的升序进行分组。之后，在第二次传递中，他们的姓名根据第二个字母的升序进行分组。过程一直持续到我们找到排序列表。换句话说，它按数字（或字母）进行排序。

• 最坏情况时间复杂度：O(n*d)
• 平均情况时间复杂度：O(n*d)
• 最佳情况时间复杂度：O(n*d)

在所有三种情况下，基数排序都花费O(n*d)时间，其中 n 是元素数量，d 是最大元素中的数字位数。它是一种在范围不大但有限制的情况下常用的算法。

例如，按时间对事件进行排序，按成绩对学生进行排序，按日期、年份、月份、时间等对事件进行排序。

阅读更多 基数排序算法

计数排序的时间复杂度

计数排序算法不通过比较元素来进行排序。它通过计算具有不同键值的对象（如哈希）来执行排序。之后，它执行一些算术运算来计算每个对象在输出序列中的索引位置。计数排序不用作通用排序算法。

• 最坏情况时间复杂度：O(n + k)
• 平均情况时间复杂度：O(n + k)
• 最佳情况时间复杂度：O(n + k)

其中，n 和 k 分别是 inputArray[] 和 countArray[] 的大小。

当范围不大于要排序的对象数量时，计数排序是有效的。它可以用于对负输入值进行排序。

阅读更多 计数排序算法

希尔排序的时间复杂度

希尔排序是由唐纳德·希尔发明的一种原地比较排序算法。它是插入排序的泛化，通过比较相隔多个位置的元素来克服插入排序的缺点。

• 最坏情况时间复杂度：O(n²)
• 平均情况时间复杂度：O(n log(n))
• 最佳情况时间复杂度：O(n log(n))

最佳情况发生在不需要排序时，即数组已排序。最坏情况发生在必须按相反顺序对数组元素进行排序时。也就是说，假设我们要按升序对数组元素进行排序，但其元素是按降序排列的。

阅读更多 希尔排序算法

桶排序的时间复杂度

桶排序是一种排序技术，它将元素分成不同的桶或组。将元素放入桶后，可以使用任何其他排序算法对它们进行排序。最终，排序后的元素按顺序收集在一起。

• 最坏情况时间复杂度：O(n²)
• 平均情况时间复杂度：O(n + k)
• 最佳情况时间复杂度：O(n + k)

其中 n 是要排序的元素数量，k 是桶的数量。

当一个桶接收到输入数组的所有元素时，会出现最坏情况。当不需要排序时，即输入数组已排序时，会出现最佳情况。

阅读更多 桶排序算法

让我们总结一下上面的时间复杂度。

结论

我们已经看到，每种排序算法都有其优点和缺点。因此，在使用任何算法之前，必须了解其所有方面。选择一个算法而不是另一个算法完全取决于其使用场景。

排序算法时间复杂度选择题

1) ___________ 是一种将元素分成不同桶的排序技术。

1. 集合排序
2. 计数排序
3. 桶排序
4. 选择排序

2) 哪种排序技术在最坏、平均和最佳情况下都具有O(n²)的时间复杂度？

1. 堆排序
2. 选择排序
3. 基数排序
4. 计数排序

3) 哪种排序技术使用分治法？

1. 合并排序
2. 选择排序
3. 计数排序
4. 冒泡排序

4) 哪种排序算法按数字（或字母）进行排序？

1. 希尔排序
2. 基数排序
3. 快速排序
4. 冒泡排序

5) 哪种排序算法在最坏情况下没有O(n2)的时间复杂度？

1. 快速排序
2. 插入排序
3. 冒泡排序
4. 合并排序