折半插入排序算法与其他排序算法比较

20/22折半插入排序算法与其他排序算法比较第一部分折半插入排序算法概述 2第二部分折半插入排序算法与冒泡排序比较 5第三部分折半插入排序算法与选择排序比较 7第四部分折半插入排序算法与希尔排序比较 10第五部分折半插入排序算法与归并排序比较 12第六部分折半插入排序算法与快速排序比较 15第七部分折半插入排序算法与堆排序比较 17第八部分折半插入排序算法与桶排序比较 20

第一部分折半插入排序算法概述关键词关键要点折半插入排序算法概述

1.折半插入排序算法，也称为折半查找插入排序算法，是一种高效的排序算法，因其将折半查找与插入排序巧妙结合而得名。

2.算法原理：将待排序数据分成已排序和未排序两部分，每次从未排序部分选取一个元素，通过折半查找在已排序部分找到相应位置，将其插入，最终达到整体有序的目的。

3.算法特点：折半插入排序算法具有较高的平均时间复杂度为O(nlogn)，在接近有序或完全有序的情况下，其时间复杂度可降至O(n)。

折半插入排序算法与冒泡排序算法比较

1.相同点：

-都是简单易懂、实现容易的排序算法。

-都适用于小规模数据排序。

-都属于稳定排序算法，即对于具有相同值的元素，其相对顺序在排序后保持不变。

2.不同点：

-冒泡排序算法的时间复杂度为O(n^2)，而折半插入排序算法的时间复杂度为O(nlogn)。

-冒泡排序算法在有序或接近有序的情况下，性能较差，而折半插入排序算法在有序或接近有序的情况下，性能较好。

-冒泡排序算法的多次比较和交换操作使其效率较低，而折半插入排序算法通过折半查找减少了比较次数，提高了效率。

折半插入排序算法与快速排序算法比较

1.相同点：

-都属于比较型排序算法，即通过比较元素的值来确定其相对顺序。

-都具有较高的平均时间复杂度为O(nlogn)。

2.不同点：

-快速排序算法是一种分治排序算法，通过递归将待排序数据划分成较小的子问题，再分别对子问题进行排序，最终合并排序结果。

-折半插入排序算法则是一种直接排序算法，通过逐个比较和插入元素的方式对数据进行排序。

-快速排序算法在平均情况下性能优于折半插入排序算法，但在最坏情况下，其时间复杂度退化至O(n^2)。

-折半插入排序算法在任何情况下时间复杂度都为O(nlogn)，因此更适合处理小规模数据或接近有序的数据。

折半插入排序算法与归并排序算法比较

1.相同点：

-都属于比较型排序算法。

-都具有较高的平均时间复杂度为O(nlogn)。

-都属于稳定排序算法。

2.不同点：

-归并排序算法是一种分治排序算法，通过递归将待排序数据划分为较小的子问题，分别对子问题进行排序，再合并排序结果。

-折半插入排序算法则是一种直接排序算法，通过逐个比较和插入元素的方式对数据进行排序。

-在空间复杂度方面，归并排序算法需要额外的空间来存储临时数据，而折半插入排序算法不需要。

-折半插入排序算法在处理小规模数据或接近有序的数据时性能较好，而归并排序算法在处理大规模数据时性能较好。

折半插入排序算法与堆排序算法比较

1.相同点：

-都属于比较型排序算法。

-都具有较高的平均时间复杂度为O(nlogn)。

2.不同点：

-堆排序算法是一种基于堆数据结构的排序算法，通过构建堆并不断调整堆的结构来实现排序。

-折半插入排序算法则是一种直接排序算法，通过逐个比较和插入元素的方式对数据进行排序。

-堆排序算法的空间复杂度为O(n)，而折半插入排序算法的空间复杂度为O(1)。

-堆排序算法在处理大规模数据时性能较好，而折半插入排序算法在处理小规模数据或接近有序的数据时性能较好。

折半插入排序算法与基数排序算法比较

1.相同点：

-都属于非比较型排序算法。

2.不同点：

-基数排序算法是一种按位比较的排序算法，通过将数据按位分组，然后根据每一位的数字值进行排序，最终达到整体有序的目的。

-折半插入排序算法则是一种比较型排序算法，通过比较元素的值来确定其相对顺序。

-基数排序算法适用于处理具有相同位数的数据，其时间复杂度为O(n*k)，其中n为数据量，k为数据中关键字段的最大位数。

-折半插入排序算法的时间复杂度为O(nlogn)，在某些情况下比基数排序算法更有效。折半插入排序算法概述

折半插入排序算法（BinaryInsertionSort）是一种高效、稳定的排序算法，它将待排序的元素进行有序排列，时间复杂度为O(n^2)，空间复杂度为O(1)。

#算法流程

1.将待排序序列的第一个元素视为一个有序子序列。

2.从第二个元素开始，将其与有序子序列中的元素进行比较，找到其合适的位置并插入。

3.重复步骤2，直到所有元素都插入到合适的位置，形成一个有序序列。

#算法举例

给定一个待排序序列：[5,3,1,2,4]：

1.将5作为有序子序列的第一个元素：[5]。

2.将3与5进行比较，找到3的合适位置并插入：[3,5]。

3.将1与[3,5]中的元素进行比较，找到1的合适位置并插入：[1,3,5]。

4.将2与[1,3,5]中的元素进行比较，找到2的合适位置并插入：[1,2,3,5]。

5.将4与[1,2,3,5]中的元素进行比较，找到4的合适位置并插入：[1,2,3,4,5]。

最终，待排序序列变为：[1,2,3,4,5]，排序完成。

#算法特点

*折半插入排序算法是一种稳定的排序算法，这意味着具有相同值的元素在排序后的顺序与排序前的顺序相同。

*折半插入排序算法的时间复杂度为O(n^2)，这与其他常见的排序算法如冒泡排序、选择排序和堆排序相同。

*折半插入排序算法的空间复杂度为O(1)，因为它只需要少量额外的内存来存储临时变量，而无需使用额外的数组或链表。第二部分折半插入排序算法与冒泡排序比较关键词关键要点折半插入排序算法与冒泡排序的思想对比

1.折半插入排序算法的基本思想是，将待排序的元素依次插入到前面已经排好序的子序列中，直到所有元素都插入完毕。而冒泡排序的基本思想是，通过两两比较相邻的元素，将较大的元素向后移动至正确的位置，并不断重复此过程，直至整个序列有序。

2.折半插入排序算法的时间复杂度为O(nlogn)，而冒泡排序的时间复杂度为O(n^2)。这意味着，当待排序的元素较多时，折半插入排序算法的效率要高于冒泡排序算法。

3.折半插入排序算法的空间复杂度为O(1)，而冒泡排序的空间复杂度也为O(1)。这意味着，这两种排序算法都不需要额外的空间来存储临时数据。

折半插入排序算法与冒泡排序的性能对比

1.折半插入排序算法的平均时间复杂度和最好时间复杂度均为O(nlogn)，而冒泡排序算法的平均时间复杂度和最好时间复杂度都是O(n^2)。这意味着，折半插入排序算法在大多数情况下都要优于冒泡排序算法。

2.折半插入排序算法的最坏时间复杂度为O(n^2)，而冒泡排序算法的最坏时间复杂度也为O(n^2)。这意味着，当待排序的元素已经基本有序时，这两种排序算法的速度都会变慢。

3.折半插入排序算法的空间复杂度为O(1)，而冒泡排序的空间复杂度也为O(1)。这意味着，这两种排序算法都不需要额外的空间来存储临时数据。

折半插入排序算法与冒泡排序的应用对比

1.折半插入排序算法常用于对少量数据进行排序，因为它的时间复杂度为O(nlogn)，比冒泡排序算法的O(n^2)要低。

2.冒泡排序算法常用于对大型数据进行排序，因为它的空间复杂度为O(1)，比折半插入排序算法的O(n)要低。

3.折半插入排序算法和冒泡排序算法都可以用于对各种类型的数据进行排序，包括数字、字符串和对象。折半插入排序算法与冒泡排序比较

#算法概述

折半插入排序算法：将待排序的序列划分为有序序列和无序序列两部分，每次从无序序列中选取一个元素，在有序序列中找到合适的位置进行插入，直到所有元素都变为有序序列。

冒泡排序算法：不断比较相邻的两个元素，如果逆序则交换这两个元素的位置，直到整个序列变为有序序列。

#效率比较

时间复杂度：

-折半插入排序算法：对于包含n个元素的序列，其平均时间复杂度为O(n^2)，最坏时间复杂度为O(n^2)。

-冒泡排序算法：对于包含n个元素的序列，其平均时间复杂度为O(n^2)，最坏时间复杂度为O(n^2)。

空间复杂度：

-折半插入排序算法：不需要额外空间，其空间复杂度为O(1)。

-冒泡排序算法：不需要额外空间，其空间复杂度为O(1)。

#稳定性比较

稳定性：当待排序序列中存在相等元素时，排序算法是否保持这些元素的相对顺序。

-折半插入排序算法：是稳定的。

-冒泡排序算法：是不稳定的。

#适用场景

折半插入排序算法：适用于待排序序列基本有序或已经部分有序的情况，此时其效率较高。

冒泡排序算法：适用于待排序序列元素较少的情况，此时其效率较高。

#结论

总体而言，折半插入排序算法比冒泡排序算法更有效，但冒泡排序算法更简单易懂。在实际应用中，应根据具体情况选择合适的排序算法。第三部分折半插入排序算法与选择排序比较关键词关键要点折半插入排序算法与选择排序的时间复杂度比较

1.折半插入排序算法的时间复杂度为O(n^2)，选择排序算法的时间复杂度也为O(n^2)。

2.在最好情况下，折半插入排序算法和选择排序算法的时间复杂度均为O(n)。

3.在平均情况下，折半插入排序算法和选择排序算法的时间复杂度均为O(n^2)。

4.在最坏情况下，折半插入排序算法和选择排序算法的时间复杂度均为O(n^2)。

折半插入排序算法与选择排序的稳定性比较

1.折半插入排序算法是一种稳定排序算法，这意味着对于相同键值的元素，它们在排序后的顺序与排序前的顺序相同；

2.选择排序算法不是一种稳定排序算法，这意味着对于相同键值的元素，它们在排序后的顺序可能与排序前的顺序不同。折半插入排序算法与选择排序比较

折半插入排序算法和选择排序算法都是一种简单、高效的排序算法，它们都属于插入排序算法的一种。这两种算法的基本思想都是将待排序的元素依次插入到已经排好序的子序列中，直到所有元素都插入完毕。

#算法流程

折半插入排序算法和选择排序算法的流程如下：

*折半插入排序算法：

1.将第一个元素作为已经排好序的子序列。

2.从第二个元素开始，依次将每个元素插入到已经排好序的子序列中。

3.对于每个元素，使用折半查找算法找到它在已经排好序的子序列中的正确位置。

4.将该元素插入到找到的位置。

5.重复步骤2-4，直到所有元素都插入完毕。

*选择排序算法：

1.将第一个元素作为最小元素。

2.从第二个元素开始，依次将每个元素与最小元素进行比较。

3.如果当前元素小于最小元素，则将当前元素作为最小元素。

4.重复步骤2-3，直到所有元素都比较完毕。

5.将最小元素与第一个元素交换位置。

6.重复步骤1-5，直到所有元素都排序完毕。

#时间复杂度

折半插入排序算法和选择排序算法的时间复杂度都是O(n^2)。但是，折半插入排序算法在某些情况下比选择排序算法更有效率。例如，当待排序的元素已经基本有序时，折半插入排序算法只需要O(n)的时间复杂度就可以完成排序。

#空间复杂度

折半插入排序算法和选择排序算法的空间复杂度都是O(1)。也就是说，它们不需要额外的空间来完成排序。

#稳定性

折半插入排序算法和选择排序算法都不是稳定的排序算法。也就是说，当待排序的元素中有相同的值时，这些元素在排序后的位置可能会发生改变。

#适用场景

折半插入排序算法和选择排序算法都适合于对小规模的数据进行排序。折半插入排序算法在某些情况下比选择排序算法更有效率，例如，当待排序的元素已经基本有序时。选择排序算法则更适合于对已经基本有序的数据进行排序。

#总结

折半插入排序算法和选择排序算法都是简单、高效的排序算法。它们都属于插入排序算法的一种，基本思想都是将待排序的元素依次插入到已经排好序的子序列中，直到所有元素都插入完毕。折半插入排序算法在某些情况下比选择排序算法更有效率，例如，当待排序的元素已经基本有序时。选择排序算法则更适合于对已经基本有序的数据进行排序。第四部分折半插入排序算法与希尔排序比较关键词关键要点折半插入排序算法与希尔排序在排序效率上的比较

1.平均比较次数：在平均情况下，折半插入排序算法的平均比较次数大约为n*log2n，而希尔排序算法的平均比较次数大约为n*(log2n)^2。因此，折半插入排序算法在平均情况下更有效。

2.最坏情况比较次数：在最坏情况下，折半插入排序算法的最坏情况比较次数为n^2，而希尔排序算法的最坏情况比较次数大约为n*(log2n)^2。因此，折半插入排序算法在最坏情况下更有效。

3.最佳情况比较次数：在最佳情况下，折半插入排序算法和希尔排序算法的最佳情况比较次数都为n。因此，在最佳情况下，这两种算法具有相同的效率。

折半插入排序算法与希尔排序在稳定性上的比较

1.稳定性定义：稳定性是指当两个元素具有相同的键值时，排序算法不会改变它们之间的相对顺序。

2.折半插入排序算法的稳定性：折半插入排序算法是一种稳定的排序算法，因为它在比较两个元素时，除了比较它们的键值之外，还会比较它们的索引。因此，如果两个元素具有相同的键值，则它们的相对顺序将不会被改变。

3.希尔排序算法的稳定性：希尔排序算法是一种不稳定的排序算法，因为它在比较两个元素时，只会比较它们的键值，而不会比较它们的索引。因此，如果两个元素具有相同的键值，则它们的相对顺序可能会被改变。折半插入排序算法与希尔排序比较

#相同点

*都是插入排序算法，基本思想都是将待排序数据插入到已排序的部分。

*时间复杂度都为O（nlogn），空间复杂度为O（1）。

*都适用于小规模数据排序。

#不同点

*排序过程不同：折半插入排序算法采用折半查找的方式来寻找待插入元素的合适位置，而希尔排序采用增量序列的方式来减少比较次数。

*性能表现不同：折半插入排序算法在数据量较小的时候性能优于希尔排序，而在数据量较大时，希尔排序的性能要优于折半插入排序算法。

#具体比较

*时间复杂度：

*折半插入排序算法的时间复杂度为O(nlogn)，最优时间复杂度为O(n)，平均时间复杂度为O(nlogn)，最坏时间复杂度为O(n^2)。

*希尔排序的时间复杂度为O(nlogn)，最优时间复杂度为O(n)，平均时间复杂度为O(nlogn)，最坏时间复杂度为O(n^2)。

*空间复杂度：

*折半插入排序算法的空间复杂度为O(1)，因为它不需要额外的空间来存储中间结果。

*希尔排序的空间复杂度也为O(1)，因为它不需要额外的空间来存储中间结果。

*性能表现：

*折半插入排序算法在数据量较小的时候性能优于希尔排序。这是因为折半插入排序算法在数据量较小的时候，查找待插入元素的合适位置只需要进行log(n)次比较，而希尔排序则需要进行n次比较。

*希尔排序在数据量较大时性能优于折半插入排序算法。这是因为希尔排序在数据量较大时，通过增量序列可以减少比较次数，从而提高排序效率。

#总结

折半插入排序算法和希尔排序都是性能优良的插入排序算法，它们的时间复杂度都为O(nlogn)，空间复杂度为O(1)。折半插入排序算法在数据量较小的时候性能优于希尔排序，而在数据量较大时，希尔排序的性能要优于折半插入排序算法。因此，在选择排序算法时，需要根据具体的数据量来选择合适的算法。第五部分折半插入排序算法与归并排序比较关键词关键要点时间复杂度比较

1.折半插入排序算法的时间复杂度为O(n^2)，而归并排序的时间复杂度为O(nlogn)。

2.当数据量较小时，折半插入排序算法的效率可能与归并排序算法相当，但随着数据量的增加，归并排序算法的优势会越来越明显。

3.在需要对大量数据进行排序的情况下，归并排序算法是比折半插入排序算法更好的选择。

空间复杂度比较

1.折半插入排序算法的空间复杂度为O(1)，而归并排序的空间复杂度为O(n)。

2.这是因为折半插入排序算法不需要额外的空间来存储临时数据，而归并排序算法需要使用一个与原数组大小相同的临时数组。

3.在内存有限的情况下，折半插入排序算法是比归并排序算法更好的选择。

稳定性比较

1.折半插入排序算法和归并排序算法都是稳定的排序算法。

2.这意味着如果两个元素在排序前的顺序相同，那么在排序后它们的顺序也相同。

3.在需要对包含重复元素的数据进行排序的情况下，折半插入排序算法和归并排序算法都是很好的选择。折半插入排序算法与归并排序比较

折半插入排序算法和归并排序都是常用的排序算法，它们都有自己的优缺点。

*时间复杂度

在平均情况下，折半插入排序算法的时间复杂度为O(n^2)，而在最坏情况下，其时间复杂度也是O(n^2)。归并排序算法的平均时间复杂度和最坏时间复杂度都是O(nlogn)，这意味着它比折半插入排序算法要快，尤其是对于大规模的数据集。

*空间复杂度

折半插入排序算法和归并排序算法的空间复杂度都是O(n)，这意味着它们都需要额外的空间来存储排序后的数据。但是，归并排序算法需要额外的空间来存储合并后的数据，因此在某些情况下，它的空间复杂度可能略高于折半插入排序算法。

*稳定性

折半插入排序算法和归并排序算法都是稳定的排序算法，这意味着如果两个元素在排序前具有相同的键值，那么在排序后它们仍将具有相同的顺序。这对于某些应用来说非常重要，例如当您需要对数据进行排序并保持其原始顺序时。

*实现的难易程度

折半插入排序算法的实现比归并排序算法要简单得多。这是因为折半插入排序算法只需要几个简单的步骤，而归并排序算法涉及更多的步骤和递归。

总体而言，归并排序算法比折半插入排序算法更有效，尤其是在处理大规模数据集时。但是，折半插入排序算法的实现更简单，并且在某些情况下（例如当数据已经部分有序时）它的性能可能更好。

下面是一个表，总结了折半插入排序算法和归并排序算法的主要区别：

|特征|折半插入排序算法|归并排序算法|

||||

|时间复杂度（平均）|O(n^2)|O(nlogn)|

|时间复杂度（最坏）|O(n^2)|O(nlogn)|

|空间复杂度|O(n)|O(n)|

|稳定性|是|是|

|实现的难易程度|简单|困难|

结论

折半插入排序算法和归并排序算法都是有效的排序算法，它们都有自己的优缺点。在选择哪种算法时，您需要考虑数据集的大小、需要排序的数据的类型以及算法的实现难易程度。第六部分折半插入排序算法与快速排序比较关键词关键要点【时间复杂度】：

1.折半插入排序算法的时间复杂度为O(n^2)，而快速排序算法的时间复杂度为O(nlogn)。

2.当数据量较小时，折半插入排序算法比快速排序算法效率更高，当数据量较大时，快速排序算法比折半插入排序算法效率更高。

3.快速排序算法的平均时间复杂度为O(nlogn)，但是最坏情况下的时间复杂度为O(n^2)。

【空间复杂度】：

折半插入排序算法与快速排序比较

#比较指标

对比快速排序和折半插入排序算法，主要从时间复杂度、空间复杂度、稳定性、元素分布情况和现实应用场景等多个指标进行比较分析，以便更好地理解两者之间的区别。

#时间复杂度

*平均时间复杂度：

-折半插入排序：O(n^2)。

-快速排序：O(nlogn)。

*最好时间复杂度：

-折半插入排序：O(n)。

-快速排序：O(nlogn)。

*最坏时间复杂度：

-折半插入排序：O(n^2)。

-快速排序：O(n^2)。

#空间复杂度

*折半插入排序：O(1)。

*快速排序：O(logn)。

#稳定性

*折半插入排序：稳定。

*快速排序：不稳定。

#元素分布情况

*折半插入排序：对于接近有序的数据序列，性能较好，适合小数据量排序。

*快速排序：对于随机分布或顺序颠倒的数据序列，性能较好，适合大数据量排序。

#现实应用场景

*折半插入排序：适用于对小规模数据或基本有序数据进行排序的场景，如嵌入式系统、单片机等资源受限环境。

*快速排序：适用于对大规模数据进行排序的场景，如数据库、文件系统、网络数据处理等。

#综合评价

*折半插入排序：算法简单易懂、实现容易、适合小规模数据排序、稳定，但时间复杂度较高。

*快速排序：算法效率较高、时间复杂度为O(nlogn)、不稳定、适合大规模数据排序。

#适用于场景上的对比

*当数据量较小时，折半插入排序和快速排序的性能差异不大，此时可以根据具体情况选择合适的算法。

*当数据量较大时，快速排序的性能优势明显，适合使用快速排序进行数据排序。

*当数据具有明显的分布规律时，折半插入排序的性能可能优于快速排序。

*当数据稳定性是一个重要考虑因素时，折半插入排序是更好的选择。第七部分折半插入排序算法与堆排序比较关键词关键要点【时间复杂度】：

1.折半插入排序算法与堆排序都是非递减排序算法，但两者的时间复杂度不同。

2.折半插入排序的时间复杂度为O(n^2)，而堆排序的时间复杂度为O(nlogn)。

3.当数据量较小时，折半插入排序算法的效率更高，而当数据量较大时，堆排序算法的效率更高。

【空间复杂度】：

折半插入排序算法与堆排序比较

#算法原理

折半插入排序算法：

折半插入排序算法是一种插入排序算法的变种，它通过将待排序元素插入到已经排序的序列中来实现排序。在折半插入排序算法中，首先将待排序序列分为两个部分：已排序部分和未排序部分。然后，从未排序部分中选择一个元素，通过比较将它插入到已排序部分的适当位置。如此反复，直到所有元素都被插入到已排序部分中。

堆排序算法：

堆排序算法是一种基于比较的排序算法，它通过将待排序元素构建成一个二叉堆，然后通过调整堆结构来实现排序。在堆排序算法中，首先将待排序序列构建成一个二叉堆，然后从堆顶开始依次取出元素，并将其插入到已排序序列中。如此反复，直到堆中没有元素为止。

#时间复杂度

折半插入排序算法：

折半插入排序算法的时间复杂度为O(n^2)，其中n为待排序元素的数量。这是因为在折半插入排序算法中，每个元素都需要与已排序部分中的所有元素进行比较，才能确定其插入位置。

堆排序算法：

堆排序算法的时间复杂度为O(nlogn)，其中n为待排序元素的数量。这是因为在堆排序算法中，构建二叉堆的时间复杂度为O(n)，调整堆结构的时间复杂度为O(logn)。

#空间复杂度

折半插入排序算法：

折半插入排序算法的空间复杂度为O(1)，这是因为折半插入排序算法不需要额外的空间来存储数据。

堆排序算法：

堆排序算法的空间复杂度为O(n)，这是因为堆排序算法需要额外的空间来存储二叉堆。

#稳定性

折半插入排序算法：

折半插入排序算法是不稳定的排序算法，这意味着对于相同的元素，在排序后的序列中，它们的相对顺序可能会发生变化。

堆排序算法：

堆排序算法是稳定的排序算法，这意味着对于相同的元素，在排序后的序列中，它们的相对顺序将保持不变。

#适用场景

折半插入排序算法：

折半插入排序算法适用于需要对少量数据进行排序的情况，以及需要对已经基本有序的数据进行排序的情况。

堆排序算法：

堆排序算法适用于需要对大量数据进行排序的情况，以及需要对数据进行快速排序的情况。

#总体比较

总的来说，折半插入排序算法和堆排序算法都是高效的排序算法，但它们各自有其优缺点。折半插入排序算法的时间复杂度较低，但空间复杂度较高；堆排序算法的时间复杂度较高，但空间复杂度较低。折半插入排序算法是不稳定的，而堆排序算法是稳定的。在实际应用中，应根据具体情况选择合适的排序算法。第八部分折半插入排序算法与桶排序比较关键词关键要点折半插入排序算法与桶排序的复杂度比较

1.平均时间复杂度：折半插入排序算法的平均时间复杂度为O(nlog^2n)，桶排序的平均时间复杂度为O(n+k)，其中n是待排序元素的个数，k是桶的个数。当n远大于k时，桶排序的平均时间复杂度更优。

2.最坏时间复杂度：折半插入排序算法的最坏时间复杂度为O(n^2)，桶排序的最坏时间复杂度为O(n^2)。当数据分布非常不均匀时，折半插入排序算法和桶排序的最坏时间复杂度都可能达到O(n^2)。

3.空间复杂度：折半插入排序算法的空间复杂度为O(1)，桶排序的空间复杂度为O(n+k)。桶