S15-08 算法-排序算法
[TOC]
概述
排序
排序(Sorting) 是一个非常非常非常常见的功能，在平时生活中也是随处可见的。
如何排序：
需求：对一组身高不等的10个人进行排序。
人来排序：
思路：
如果是人来排序事情会非常简单，因为人只要扫过去一眼就能看出来谁最高谁最低。
然后让最低(或者最高)的站在前面，其他人依次后移。
按照这这样的方法。 依次类推就可以了。
特点：
可以统筹全局，直接获取到最高或者最低的结果。
不需要考虑空间的问题，因为通常情况下都有足够的空间来相互推嚷。
缺点：
容易出错。
数据量非常庞大时，很难进行排序，比如有1000000的数据量。
计算机排序：
思路：
- 计算机有些笨拙，它只能执行指令，所以没办法一眼扫过去。
- 计算机也很聪明，只要你写出了正确的指令，可以让它帮你做无数次类似的事情而不用担心出现错误。
- 并且计算机排序也无需担心数据量的大小。想象一下，让人排序10000个，甚至更大的数据项你还能一眼扫过去吗?
- 人在排序时不一定要固定特有的空间，他们可以相互推推嚷嚷就腾出了位置，还能互相前后站立。但是计算机必须有严密的逻辑和特定的指令。
特点：
计算机不能像人一样，一眼扫过去这样通览所有的数据。
它只能根据计算机的比较操作原理，在同一个时间对两个队员进行比较。
在人类看来很简单的事情，计算机的算法却不能看到全景。
因此，它只能一步步解决具体问题和遵循一些简单的规则。
排序算法
虽然排序算法从名称来看非常容易理解，但是从计算机科学发展以来，在此问题上已经有大量的研究。
由于排序非常重要而且可能非常耗时，所以它已经成为一个计算机科学中广泛研究的课题，而且人们已经研究出一套成熟的方案来实现排序。因此，幸运的是你并不需要是发明某种排序算法，而是站在巨人的肩膀上即可。
排序算法(Sorting algorithm) 就是研究如何对一个集合进行高效排序的算法，也是在面试时非常常见的面试题型之一。
维基百科解释：在计算机科学与数学中，一个排序算法是一种能将一串资料依照特定排序方式排列的算法。
分类：在计算机科学所使用的排序算法通常依据以下标准分类。
- 计算的时间复杂度：使用大O表示法，也可以实际测试消耗的时间。
- 内存使用量：甚至是其他电脑资源比如外部排序，使用磁盘来存储排序的数据。
- 稳定性：稳定排序算法会让原本有相等键值的纪录维持相对次序。
- 排序的方法：插入、交换、选择、合并等等。
常见排序算法
常见的排序算法非常多：
- 1、冒泡排序
- 2、选择排序
- 3、插入排序
- 4、归并排序
- 5、快速排序
- 6、堆排序
- 7、希尔排序
- 8、计数排序
- 9、桶排序
- 10、基数排序
- 11、内省排序
- 12、平滑排序
时间复杂度
讲解思路
因为我们要学习多种排序算法，所以我对他们的学习思路进行了统一的安排：
- 1、介绍某种排序算法。如果该排序算法有一些历史背景或者故事也会一起介绍。
- 2、分析某种排序算法的思路步骤。
- 3、某种排序算法的图解。
- 4、排序算法的代码实现过程，一步步手写实现。
- 5、排序算法的复杂度分析。
- 6、排序算法的小结。
冒泡排序
冒泡排序
我们要学习非常多种类的排序算法，那么我们可以先从一个最简单的排序算法入手：冒泡排序。
冒泡排序(Bubble Sort) 是一种简单的排序算法，它通过重复地遍历待排序的元素，比较相邻元素并交换位置，直到整个列表有序。这个过程像气泡一样逐渐把较大的元素“冒”到序列的顶端，因此得名“冒泡排序”。
算法步骤
- 从序列的第一项开始，依次比较相邻的两个元素。
- 如果当前元素大于下一个元素，则交换它们的位置。
- 遍历完一轮后，最大的元素会被“冒泡”到序列的末尾。
- 重复这个过程，每次遍历时可以少比较一个元素，因为每一轮结束后，最大的元素已经排到了最后。
- 当没有需要交换的元素时，排序完成。
图解
代码实现
1、冒泡排序的代码实现
2、交换函数swap()
3、测试：
4、优化：检测是否有交换
排序算法测试工具
1、编写一个工具，帮助测试排序算法
2、定义一个测试是否排序正确的方法isSorted()
3、使用工具方法测试冒泡排序
时间复杂度
在冒泡排序中，每次比较两个相邻的元素，并交换他们的位置，如果左边的元素比右边的元素大，则交换它们的位置。这样的比较和交换的过程可以用一个循环实现。
时间复杂度：
最好情况：
O(n)即待排序的序列已经是有序的。
此时仅需遍历一遍序列，不需要交换操作。
最坏情况：
O(n²)即待排序的序列是逆序的。
需要进行n-1轮排序，每一轮中需要进行n-i-1次比较和交换操作。
平均情况：
O(n²)即待排序的序列是随机排列的。
每一对元素的比较和交换都有1/2的概率发生，因此需要进行n-1轮排序，每一轮中需要进行n-i-1次比较和交换操作。
由此可见，冒泡排序的时间复杂度主要取决于数据的初始顺序，最坏情况下时间复杂度是O(n²)，不适用于大规模数据的排序。
总结
冒泡排序适用于数据规模较小的情况，因为它的时间复杂度为O(n²)，对于大数据量的排序会变得很慢。
同时，它的实现简单，代码实现也容易理解，适用于学习排序算法的初学者。
但是，在实际的应用中，冒泡排序并不常用，因为它的效率较低。
因此，在实际应用中，冒泡排序通常被更高效的排序算法代替，如快速排序、归并排序等。
选择排序
选择排序
选择排序(Selection Sort)：是一种简单的排序算法。其基本思想是每一轮遍历中都从未排序的部分中选择最小/最大元素，然后将其与未排序部分的第一个元素交换，逐步缩小待排序的范围，直到排序完成。
选择排序的优点：交换次数较少
- 如果某个元素位于正确的最终位置，则它不会被移动。
- 选择排序每轮交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。
- 在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。
选择排序的实现方式很简单，并且容易理解，因此它是学习排序算法的很好的选择。
算法步骤
算法步骤：
- 初始化：从数组第一个元素开始，默认当前元素为最小值的索引。
- 查找极值：遍历未排序部分，记录最小值的索引。
- 交换位置：将最小值与当前起始位置的元素交换，确定该元素的最终位置。
- 循环迭代：重复上述步骤，每次迭代后未排序范围缩小一位，直到所有元素有序。
图解
代码实现
1、选择排序的代码实现
2、测试：
3、优化：如果最初选择的最小值就是本轮的最小值，则不交换索引位置。
时间复杂度
时间复杂度：选择排序的时间复杂度是比较容易分析的。
最好情况：
O(n²)，待排序的数组本身就是有序的。- 内层循环每次都需要比较 n-1 次，因此比较次数为 n(n-1)/2，交换次数为 0。
最坏情况：
O(n²)，待排序的数组是倒序排列的。- 每次内层循环都需要比较 n-i-1 次，因此比较次数为 n(n-1)/2，交换次数也为 n(n-1)/2。
平均情况：
O(n²)，待排序的数组是随机排列的。- 每个元素在内层循环中的位置是等概率的，因此比较次数和交换次数的期望值都是 n(n-1)/4。
总结
虽然选择排序的实现非常简单，但是它的时间复杂度较高，对于大规模的数据排序效率较低。
如果需要对大规模的数据进行排序，通常会选择其他更为高效的排序算法，例如快速排序、归并排序等。
总的来说，选择排序适用于小规模数据的排序和排序算法的入门学习，对于需要高效排序的场合，可以选择其他更为高效的排序算法。
插入排序
插入排序
插入排序(Insertion Sort)： 是一种简单的排序算法，它的工作原理与手动整理一副牌的过程非常相似。我们在未排序区间选择一个基准元素，将该元素与其左侧已排序区间的元素逐一比较大小，并将该元素插入到正确的位置。
算法步骤
插入排序的流程如下：
- 首先，假设数组的第一个元素已经排好序了，因为它只有一个元素，所以可以认为是有序的。
- 然后，从第二个元素开始，不断与前面的有序数组元素进行比较。
- 如果当前元素小于前面的有序数组元素，则把当前元素插入到前面的合适位置。
- 否则，继续与前面的有序数组元素进行比较。
- 以此类推，直到整个数组都有序。
- 循环步骤2~5，直到最后一个元素。
- 完成排序。
图解
代码实现
1、插入排序的代码实现
2、测试
时间复杂度
时间复杂度：
最好情况：
O(n)，待排序数组是有序的。- 每个元素只需要比较一次就可以确定它的位置，因此比较次数为 n-1，移动次数为 0。
最坏情况：
O(n²)，待排序数组是倒序排列的。- 每个元素都需要比较和移动 i 次，其中 i 是元素在数组中的位置。因此比较次数为 n(n-1)/2，移动次数为 n(n-1)/2。
平均情况：
O(n²)，待排序数组是随机排列的。总结：
如果数组部分有序，插入排序可以比冒泡排序和选择排序更快。
如果数组完全逆序，插入排序的时间复杂度比较高，不如快速排序或归并排序。
总结
插入排序是一种简单直观的排序算法，它的基本思想就是将待排序数组分为已排序部分和未排序部分，然后将未排序部分的每个元素插入到已排序部分的合适位置。
插入排序的时间复杂度为 O(n²)，虽然这个复杂度比较高，但是插入排序的实现非常简单，而且在某些情况下性能表现也很好。
比如，如果待排序数组的大部分元素已经排好序，那么插入排序的性能就会比较优秀。
总之，插入排序虽然没有快速排序和归并排序等高级排序算法的复杂性和高效性，但是它的实现非常简单，而且在一些特定的场景(大部分元素已经排好序)下表现也很好。
归并排序
归并排序
归并排序(Merge Sort)：是一种基于分治策略的高效排序算法，通过递归拆分和有序合并实现排序：
分解阶段：将数组递归拆分为最小单位（单个元素），此时每个子数组自然有序。
合并阶段：自底向上合并相邻子数组，通过双指针比较元素大小，将较小值依次存入临时数组，最终形成有序序列。
历史：这个算法最早出现在1945年，由约翰·冯·诺伊曼(John von Neumann，现代计算机之父，冯·诺依曼结构、普林斯顿结构)首次提出。当时他在为美国政府工作，研究原子弹的问题。由于计算机，他在研究中提出了一种高效计算的方法，这个方法就是归并排序。
分治法实现：在实现中，我们可以使用“分治法”来完成这个过程，即将大问题分解成小问题来解决。
算法复杂度： O(n logn)，是一种比较高效的排序算法，因此在实际应用中被广泛使用。
虽然归并排序看起来比较复杂，但是只要理解了基本思路，实现起来并不困难，而且它还是一个非常有趣的算法。
思路分析
归并排序是一种基于分治思想的排序算法，其基本思路可以分为三个步骤：
分解阶段(Divide)：从顶至底递归地将数组从中点切分为两个子数组：
- 计算数组中点 mid ，递归划分左子数组(区间
[left, mid])和右子数组(区间[mid + 1, right])。 - 递归执行步骤
1.，直至子数组区间长度为 1 时终止。
合并阶段(Merge)：合并过程中比较每个子数组的元素并将它们有序地合并成一个新的数组：
- 可以使用两个指针 i 和 j 分别指向两个子数组的开头，比较它们的元素大小，并将小的元素插入到新的有序数组中。
- 如果其中一个子数组已经遍历完，就将另一个子数组的剩余部分直接插入到新的有序数组中。
- 最后返回这个有序数组。
递归终止条件：归并排序使用递归算法来实现分解过程，当子数组的长度为1时，认为这个子数组已经有序，递归结束。
总体来看，归并排序的基本思路是分治法，分成子问题分别解决，然后将子问题的解合并成整体的解。
图解
代码实现
方式一：创建新数组合并
1、归并排序的代码实现
2、测试
方式二：原数组基础上合并
时间复杂度
时间复杂度：
最好情况：
O(logn)，待排序数组是有序的。- 每个子数组都只需要合并一次，即只需要进行一次归并操作。
最坏情况：
O(n logn)，待排序数组是逆序的。- 每个子数组都需要进行多次合并。
平均情况：
O(n logn)，待排序数组是随机的。- 待排序数组中任意两个元素都是等概率出现的。
总结：假设数组长度为 n，需要进行 logn 次归并操作；每次归并操作需要 O(n) 的时间复杂度；因此，归并排序的时间复杂度为 O(n logn)。
总结
归并排序是一种非常高效的排序算法，它的核心思想是分治，即将待排序数组分成若干个子数组，分别对这些子数组进行排序，最后将排好序的子数组合并成一个有序数组。
归并排序的时间复杂度为 O(nlogn)，并且在最好、最坏和平均情况下都可以达到这个时间复杂度。
虽然归并排序看起来比较复杂，但是只要理解了基本思路，实现起来并不困难，而且它是一种非常高效的排序算法。
快速排序
快速排序
快速排序(Quick Sort，划分交换排序)：是一种 高效 的排序算法，采用 分治法(Divide and Conquer) 策略。它的核心思想是通过一次排序将数据分为独立的两部分，其中一部分的所有元素都比另一部分小，再递归地对这两部分进行排序。
历史：快速排序的发明人是一位名叫 Tony Hoare(东尼·霍尔)的计算机科学家。Tony Hoare 在1960年代初期发明了快速排序，是在一份ALGOL60 （一种编程语言，作者也是）手稿中。为了让稿件更具可读性，他采用了这种新的排序算法。当时，快速排序还没有正式命名，后来被 Tony Hoare 命名为 quicksort，也就是快速排序的意思。由于快速排序的思想非常巧妙，因此在计算机科学中得到了广泛的应用。
速度影响因素：虽然它的名字叫做“快速排序”，但并不意味着它总是最快的排序算法，它的实际运行速度取决于很多因素，如输入数据的分布情况、待排序数组的长度等等。
算法原理：
- 基准选择(Pivot)：选择一个元素作为基准(pivot)，通常选择中间元素、第一个元素或最后一个元素。
- 分区(Partition)：将数组分为两部分：所有比基准小的元素放在左边，比基准大的放在右边。
- 递归排序：对左右两个子数组递归执行上述步骤。
原地排序：快速排序是一种原地排序算法，不需要额外的数组空间。
时间复杂度：快速排序的时间复杂度是 O(n logn)，在最坏情况下是 O(n²)。但是这种情况出现的概率非常小，因此快速排序通常被认为是一种非常高效的排序算法。
虽然快速排序看起来比较复杂，但是只要理解了基本思路，实现起来并不困难。
思路分析
快速排序的思路可以分解成以下几个步骤：
- 选择基准：我们需要选择一个基准元素，通常选择第一个或最后一个元素作为基准元素。
- 定义双指针：我们定义两个指针 i 和 j，分别指向数组的左右两端。
- 从右向左找：我们从右侧开始，向左移动 j 指针，直到找到一个小于或等于基准元素的值。
- 从左向右找：我们从左侧开始，向右移动 i 指针，直到找到一个大于或等于基准元素的值。
- 交换元素：如果 i 指针小于或等于 j 指针，交换 i 和 j 指针所指向的元素。
- 遍历执行：重复步骤 3-5，直到 i 指针大于 j 指针，这时，我们将基准元素与 j 指针所指向的元素交换位置，将基准元素放到中间位置。
- 遍历结果：我们将数组分为两部分，左侧部分包含小于或等于基准元素的元素，右侧部分包含大于基准元素的元素。
- 递归排序：对左右两部分分别进行递归调用快速排序，直到左右两部分只剩下一个元素。
- 结束：整个数组就变得有序了。
图解
代码实现
1、快速排序的代码实现
2、测试
时间复杂度
快速排序的时间复杂度主要取决于基准元素的选择、数组的划分、递归深度等因素。
时间复杂度：下面是快速排序的复杂度算法分析过程：
- 最好情况：
O(n logn)，每次划分后，两部分的大小都相等，即基准元素恰好位于数组的中间位置。- 此时递归的深度为 O(log n)，每一层需要进行 n 次比较。
- 最坏情况：
O(n²)，每次划分后，其中一部分为空，即基准元素是数组中的最大或最小值。- 此时递归的深度为 O(n)，每一层需要进行 n 次比较。
- 优化策略：采用三数取中法或随机选择基准元素可以有效避免最坏情况的发生。
- 平均情况：
O(n logn)，每次划分后，两部分的大小大致相等，- 此时递归的深度为 O(log n)，每一层需要进行大约 n 次比较。
注意：快速排序是一个原地排序算法，不需要额外的数组空间。
总结
快速排序的性能优于许多其他排序算法，因为它具有良好的局部性和使用原地排序的优点。
它在大多数情况下的时间复杂度为 O(n log n)，但在最坏情况下会退化到 O(n^2)。
为了避免最坏情况的发生，可以使用一些优化策略，比如随机选择基准元素和三数取中法。
总之，快速排序是一种高效的排序算法，它在实践中被广泛使用。
堆排序
堆排序
堆排序(Heap Sort)：是一种基于二叉堆数据结构的比较排序算法。它通过构建最大堆或最小堆，逐步将堆顶元素(最大值或最小值)与末尾元素交换，并调整剩余元素以维持堆结构，从而实现排序。
算法原理：
- 堆的定义
- 最大堆：每个父节点的值都大于或等于其子节点的值，根节点为最大值。
- 最小堆：每个父节点的值都小于或等于其子节点的值，根节点为最小值。
- 堆的数组表示：二叉堆可以用数组实现，节点索引关系为：
- 父节点索引：
parent = Math.floor((i - 1) / 2) - 左子节点索引：
left = 2 * i + 1 - 右子节点索引：
right = 2 * i + 2
- 父节点索引：
- 核心步骤
- 构建最大堆：从最后一个非叶子节点开始，逐步向上调整数组，使其满足最大堆性质。
- 排序阶段：将堆顶元素(最大值)与末尾元素交换，缩小堆范围，重新构建一个最大堆。
- 重复：直到堆范围缩小至1，完成排序。
对比选择排序：堆排序和选择排序有一定的关系，因为它们都利用了“选择”这个基本操作。
- 选择排序的基本思想是在待排序的序列中选出最小/最大的元素，将其放置到序列的起始位置。
- 堆排序也是一种选择排序算法，它使用最大堆来维护一个有序序列，然后不断选择出最大的值。
时间复杂度：O(n logn)。
注意：学习堆排序之前最好先理解堆结构，这样更有利于对堆排序的理解。
思路分析
算法步骤：堆排序可以分成两大步骤：构建最大堆和排序
构建最大堆：
- 遍历待排序序列，从最后一个非叶子节点开始，依次对每个节点进行调整。
- 假设当前节点的下标为 i，左子节点的下标为 2i+1，右子节点的下标为 2i+2，父节点的下标为 (i-1)/2。
- 对于每个节点 i，比较它和左右子节点的值，找出其中最大的值，并将其与节点 i 进行交换。
- 重复进行这个过程，直到节点 i 满足最大堆的性质。
- 依次对每个非叶子节点进行上述操作，直到根节点，这样我们就得到了一个最大堆。
排序：
- 将堆的根节点(最大值)与堆的最后一个元素交换，这样最大值就被放在了正确的位置上。
- 将堆的大小减小一，并将剩余的元素重新构建成一个最大堆。
- 重复进行步骤1 和步骤2，直到堆的大小为 1，这样我们就得到了一个有序的序列。
图解
代码实现
1、堆排序的代码实现
2、测试
时间复杂度
堆排序的时间复杂度分析较为复杂，因为它既涉及到堆的建立过程，也涉及到排序过程。
时间复杂度： O(n logn)
下面我们分别对这两个步骤的时间复杂度进行分析。
步骤一：原地建堆过程：
O(n logn)- 堆的建立过程包括 n/2 次堆的下滤操作，每次下滤的时间复杂度O(logn)，因此它的时间复杂度为 O(n logn)。
步骤二：排序过程：
O(n logn)排序过程需要执行 n 次堆的删除最大值操作，每次操作都需要将堆的最后一个元素与堆顶元素交换，然后下滤堆。
每次向下调整操作的时间复杂度为 O(log n)，因此整个排序过程的时间复杂度为 O(n logn)。
综合：堆排序的时间复杂度为
O(n logn)。
空间复杂度：O(1)
需要注意的是，堆排序的空间复杂度为 O(1)，因为它只使用了常数个辅助变量来存储堆的信息。
总结
堆排序是一种高效的排序算法，它利用堆这种数据结构来实现排序。
堆排序具有时间复杂度为 O(n logn) 的优秀性能，并且由于它只使用了常数个辅助变量来存储堆的信息，因此空间复杂度为 O(1)。
但是，由于堆排序的过程是不稳定的，即相同元素的相对位置可能会发生变化，因此在某些情况下可能会导致排序结果不符合要 求。
总的来说，堆排序是一种高效的、通用的排序算法，它适用于各种类型的数据，并且可以应用于大规模数据的排序。
希尔排序
希尔排序
希尔排序(Shell Sort)：是插入排序的改进版本，通过将数组分割成多个子序列进行插入排序，逐步缩小子序列的间隔，最终完成整体排序。
核心思想：是通过较大的间隔跳跃式移动元素，减少后续小间隔排序的比较和交换次数，从而提升效率，可以通过调整步长来进一步优化。
历史：
希尔排序的名字来源于它的发明者Donald Shell（唐纳德·希尔），1959年，希尔排序算法诞生了。
在简单排序算法诞生后的很长一段时间内，人们不断尝试发明各种各样的排序算法，但是当时的排序算法的时间复杂度都是O(N²)，看起来很难超越。
当时计算机学术界充满了 “排序算法不可能突破O(N²)” 的声音，这与人类100米短跑不可能突破10秒大关的想法一样。
这是因为很多著名的排序算法，如冒泡排序、选择排序、插入排序等，它们的时间复杂度都是 O(N²) 级别的。
因此，人们普遍认为，除非发生突破性的创新，否则排序算法的时间复杂度是不可能达到O(N log N) 级别的。
在这种情况下，希尔排序的提出成为了一种重要的突破。
回顾插入排序
回顾插入排序的过程：
- 由于希尔排序基于插入排序，所以有必须回顾一下前面的插入排序。
- 我们设想一下，在插入排序执行到一半的时候，标记符左边这部分数据项都是排好序的，而标识符右边的数据项是没有排序的。
- 这个时候，取出指向的那个数据项，把它存储在一个临时变量中，接着，从刚刚移除的位置左边第一个单元开始，每次把有序的数据 项向右移动一个单元，直到存储在临时变量中的数据项可以成功插入。
插入排序的问题：
- 假设一个很小的数据项在很靠近右端的位置上，这里本来应该是较大的数据项的位置。
- 把这个小数据项移动到左边的正确位置，所有的中间数据项都必须向右移动一位。
- 如果每个步骤对数据项都进行N次移动，平均下来是移动N/2，N个元素就是 N*N/2 = N²/2。
- 所以我们通常认为插入排序的效率是O(N²)
- 如果有某种方式，不需要一个个移动所有中间的数据项，就能把较小的数据项移动到左边，那么这个算法的执行效率就会有很大的改进。
思路分析
希尔排序的做法：
- 比如下面的数字
81,94,11,96,12,35,17,95,28,58,41,75,15。 - 我们先让间隔为5进行排序
(35,81),(94,17),(11,95),(96,28),(12,58),(35,41),(17,75),(95,15) - 排序后的新序列，一定可以让数字离自己的正确位置更近一步。
- 我们再让间隔为3进行排序
(35,28,75,58,95),(17,12,15,81),(11,41,96,94)。 - 排序后的新序列，一定可以让数字离自己的正确位置又近了一步。
- 我们让间隔为1，也就是正确的插入排序。此时数字都离自己的位置更近，需要复制的次数一定会减少很多。
间隔序列
算法原理：
- 动态间隔Gap 选择一个初始间隔（如
n/2），将数组分割成多个子序列，每个子序列包含间隔为gap的元素。 - 子序列插入排序 对每个子序列进行插入排序，使元素逐渐接近最终位置。
- 逐步缩小间隔 重复上述过程，缩小间隔（如
gap = gap/2），直到间隔为 1，此时进行一次标准的插入排序。
时间复杂度依赖间隔序列：第一步的间隔序列的选择比较重要，间隔序列选择的不同会影响排序的效率。
常见间隔序列：
- 希尔原始序列：公式为
floor(n/2ᵏ)，如gap = n/2, gap = gap/2，直到gap = 1。 - Hibbard序列：公式为
2ᵏ - 1，如1, 3, 7, 15, ...，时间复杂度可优化至 O(n^(3/2))。 - Sedgewick序列：结合数学公式生成，性能更优。
代码实现-原始序列
1、希尔排序的代码实现
2、测试
代码实现-Hibbard
时间复杂度
时间复杂度：
希尔排序的效率和增量是有关系的。但是，它的效率证明非常困难，甚至某些增量的效率到目前依然没有被证明出来。
希尔原始序列：经过统计
- 最坏情况：
O(N²) - 平均情况：好于
O(N²)
- 最坏情况：
Hibbard序列：增量的算法为
2ᵏ - 1。 也就是为1 3 5 7...。- 最坏情况：O(N3/2)
- 平均情况：O(N5/4)，未被证明。
Sedgewick序列：
{1，5，19，41，109，… }序列中的项或9*4^i - 9*2^i + 1或4^i - 32^i + 1- 最坏情况：O(N4/3)，未被证明。
- 平均情况：O(N7/6)，未被证明。
总之，我们使用希尔排序大多数情况下效率都高于简单排序。
总结
希尔排序是一种改进版的插入排序，从历史的角度来看，它是一种非常非常重要的排序算法，因为它解除了人们对原有排序的固有认知。
希尔排序的时间复杂度取决于步长序列的选择，目前最优的步长序列还没有被证明，因此希尔排序的时间复杂度依然是一个开放的问题。
但是现在已经有很多更加优秀的排序算法：归并排序、快速排序等，所以从实际的应用角度来说，希尔排序已经使用的非常非常少了。
因为，我们只需要了解其核心思想即可。
测试多种排序算法
排序算法面试题
给你一个整数数组 nums，请你将该数组升序排列。
