Swift实现常用排序算法总结

排序算法基础

排序算法，是一种能将一串数据按照特定的排序方式进行排列的一种算法，一个排序算法的好坏，主要从时间复杂度，空间复杂度，稳定性来衡量。

时间复杂度

时间复杂度是一个函数，它描述了该算法的运行时间，考察的是当输入值大小趋近无穷时的情况。数学和计算机科学中使用这个大 O 符号用来标记不同”阶“的无穷大。这里的无穷被认为是一个超越边界而增加的概念，而不是一个数。

想了解时间复杂度，我想讲讲常见的 O(1)，O(log n)，O(n)，O(n log n)，O(n^2) ，计算时间复杂度的过程，常常需要分析一个算法运行过程中需要的基本操作，计量所有操作的数量。

O（1）常数阶

O（1）中的 1 并不是指时间为 1，也不是操作数量为 1，而是表示操作次数为一个常数，不因为输入 n 的大小而改变，比如哈希表里存放 1000 个数据或者 10000 个数据，通过哈希码查找数据时所需要的操作次数都是一样的，而操作次数和时间是成线性关系的，所以时间复杂度为 O（1）的算法所消耗的时间为常数时间。

O（log n）对数阶

O（log n）中的 log n 是一种简写，loga n 称作为以 a 为底 n 的对数，log n 省略掉了 a，所以 log n 可能是 log2 n，也可能是 log10 n。但不论对数的底是多少，O（log n）是对数时间算法的标准记法，对数时间是非常有效率的，例如有序数组中的二分查找，假设 1000 个数据查找需要 1 单位的时间， 1000,000 个数据查找则只需要 2 个单位的时间，数据量平方了但时间只不过是翻倍了。如果一个算法他实际的得操作数是 log2 n + 1000， 那它的时间复杂度依旧是 log n， 而不是 log n + 1000，时间复杂度可被称为是渐近时间复杂度，在 n 极大的情况，1000 相对 与 log2 n 是极小的，所以 log2 n + 1000 与 log2 n 渐进等价。

O（n）线性阶

如果一个算法的时间复杂度为 O(n)，则称这个算法具有线性时间，或 O(n) 时间。这意味着对于足够大的输入，运行时间增加的大小与输入成线性关系。例如，一个计算列表所有元素的和的程序，需要的时间与列表的长度成正比。遍历无序数组寻最大数，所需要的时间也与列表的长度成正比。

O（n log n）线性对数阶

排序算法中的快速排序的时间复杂度即 O（n log n），它通过递归 log2n 次，每次遍历所有元素，所以总的时间复杂度则为二者之积， 复杂度既 O（n log n）。

O（n^2）平方阶

冒泡排序的时间复杂度既为 O（n^2），它通过平均时间复杂度为 O（n）的算法找到数组中最小的数放置在争取的位置，而它需要寻找 n 次，不难理解它的时间复杂度为 O（n^2）。时间复杂度为 O（n^2）的算法在处理大数据时，是非常耗时的算法，例如处理 1000 个数据的时间为 1 个单位的时间，那么 1000,000 数据的处理时间既大约 1000,000 个单位的时间。

时间复杂度又有最优时间复杂度，最差时间复杂度，平均时间复杂度。部分算法在对不同的数据进行操作的时候，会有不同的时间消耗，如快速排序，最好的情况是 O（n log n），最差的情况是 O（n^2），而平均复杂度就是所有情况的平均值，例如快速排序计算平均复杂度的公式为

时间复杂度效率比较

除了上述所说的时间复杂度，下表中展示了其他一些时间复杂度，以及这些时间复杂度之间的比较。

想O(n^3)、O(n!)等这样的时间复杂度，过大的n会使算法变得不现实，都是时间的噩梦，所以这种不切实际的复杂度，一般都不会去考虑这样的算法。

空间复杂度

和时间复杂度一样，有 O(1)，O(log n)，O(n)，O(n log n)，O(n^2)，等等。实际写代码的过程中完全可以用空间来换取时间。比如判断2017年之前的某一年是不是闰年，通常可以使通过一个算法来解决。但还有另外一种做法就是将2017年之前的闰年保存到一个数组中。如果某一年存在这个数组中就是闰年，反之就不是。一般来说时间复杂度和空间复杂度是矛盾的。到底优先考虑时间复杂度还是空间复杂度，取决于实际的应用场景。

稳定性

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri = rj，且 ri 在 rj 之前，而在排序后的序列中，ri 仍在 rj 之前，则称这种排序算法是稳定的；否则称为不稳定的。

当相等的元素是无法分辨的，比如像是整数，稳定性并不是一个问题。然而，假设以下的数对将要以他们的第一个数字来排序。

(4, 1)  (3, 1)  (3, 7) （5, 6）

在这个状况下，有可能产生两种不同的结果，一个是让相等键值的纪录维持相对的次序，而另外一个则没有：

(3, 1)  (3, 7)  (4, 1)  (5, 6)  （维持次序）
(3, 7)  (3, 1)  (4, 1)  (5, 6)  （次序被改变）

不稳定排序算法可能会在相等的键值中改变纪录的相对次序，这导致我们无法准确预料排序结果（除非你把数据在你的大脑里用该算法跑一遍），但是稳定排序算法从来不会如此。例如冒泡排序即稳定的存在，相等不交换则不打乱原有顺序。而快速排序有时候则是不稳定的。

常见排序算法

本文介绍6种常用排序算法，包括冒泡、选择、插入、快排、堆排、希尔排序。下面从排序算法的原理、解题步骤、实现代码三个方面去介绍排序。

冒泡排序

原理解析

引自维基百科冒泡排序（英语：Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

冒泡排序的理念十分简单：不断比较相邻的两个元素，如果它们的顺序不符合要求就互相调换。

解题步骤

步骤如下：
* 比较相邻的元素。如果第一个比第二个大，就交换他们两个，直到把最大的元素放到数组尾部。
* 遍历长度减一，对剩下的元素从头重复以上的步骤。
* 直到没有任何一对数字需要比较时完成。

假如需要对 1 4 6 2 8 这五个数按照从大到小的排序进行排列，那么我们应该怎么入手解决呢？

首先，比较第 1 位数和第 2 位数的大小。很明显 1 要小于 4，所以我们把 1 和 4 的位置互换一下。

然后，我们继续比较第 2位数和第 3 位数，发现 1 要小于 6，因此把 1 和 6 的位置互换。

继续比较第 3 位和第 4 位数，1 要小于 2，根据要求把 1 和 2 的位置互换。

最后比较第 4 位和第 5 位数，显然 1 小于 8，同理把 1 和 8 的位置互换。

经过这样一轮操作，我们已经不知不觉中把数字 1 的位置放好了，1 是这五个数字中数值最小的，应该排在最后一位。
我们回过头来，看看刚刚才的排序过程，1 的位置经由交换慢慢“浮”到数列的顶端，是不是很像气泡上浮的过程，这也是冒泡排序算法这个名字的由来。

第一轮操作结束后，我们把五个数字中数值最小的 1 摆放好了。第二轮操作我们将会把五个数字中数值第二小的 2 摆放好。仔细想想这个规律，是不是很有意思？同样按照第一轮的规则进行操作，先比较第 1 位和第 2 位数，依此类推，过程如下。

实现代码

func bubbleSort() {//冒泡排序
    var list = [61,5,33,44,22]
    for i in 0..<list.count {//找到符合条件的数进行交换
        for j in i+1..<list.count {
            if list[j] > list[i] {
                let temp = list[j]
                list[j] = list[i]
                list[i] = temp
            }
        }
    }
    
    print(list)
}

最好的情况下，即待排序的数组本身是有序的，比较的次数是 n-1 次，没有数据交换，时间复杂度为O(n)。最坏的情况下，即待排序的数组是完全逆序的情况，此时需要比较 n*(n-1)/2 次。因此时间复杂度是O(n^2)。

选择排序

原理解析

引自维基百科选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

选择排序的基本思想就是通过 n-i 次关键字之间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录做交换，而不是像冒泡排序那样，每一次比较之后，符合条件的都做一次交换。选择排序相对于冒泡排序做的交换次数更少。

解题步骤

步骤如下：
* 遍历数组，找到最小的元素，将其置于数组起始位置。
* 从上次最小元素存放的后一个元素开始遍历至数组尾，将最小的元素置于开始处。
* 重复上述过程，直到元素排序完毕。

以数组 arr = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7] 为例，先直观看一下每一步的变化，后面再介绍细节

第一次从数组 [8, 5, 2, 6, 9, 3, 1, 4, 0, 7] 中找到最小的数 0，放到数组的最前面（与第一个元素进行交换）：

                               min
                                ↓
8   5   2   6   9   3   1   4   0   7
↑                               ↑
└───────────────────────────────┘

交换后：

0   5   2   6   9   3   1   4   8   7

在剩余的序列中 [5, 2, 6, 9, 3, 1, 4, 8, 7] 中找到最小的数 1，与该序列的第一个个元素进行位置交换：

                       min
                        ↓
0   5   2   6   9   3   1   4   8   7
    ↑                   ↑
    └───────────────────┘

交换后：

0   1   2   6   9   3   5   4   8   7

在剩余的序列中 [2, 6, 9, 3, 5, 4, 8, 7] 中找到最小的数 2，与该序列的第一个个元素进行位置交换（实际上不需要交换）：

       min
        ↓
0   1   2   6   9   3   5   4   8   7
        ↑

重复上述过程，直到最后一个元素就完成了排序。

                   min
                    ↓
0   1   2   6   9   3   5   4   8   7
            ↑       ↑
            └───────┘
                           min
                            ↓
0   1   2   3   9   6   5   4   8   7
                ↑           ↑
                └───────────┘
                       min
                        ↓
0   1   2   3   4   6   5   9   8   7
                    ↑   ↑
                    └───┘
                       min
                        ↓
0   1   2   3   4   5   6   9   8   7
                        ↑   
                                   min
                                    ↓
0   1   2   3   4   5   6   9   8   7
                            ↑       ↑
                            └───────┘  
                               min
                                ↓
0   1   2   3   4   5   6   7   8   9
                                ↑      
                                   min
                                    ↓
0   1   2   3   4   5   6   7   8   9
                                    ↑

实现代码

func chooseSort() {//选择排序
    var list = [61,5,33,44,22]
    for i in 0..<list.count {
        var min = i//记录当前最小的数，比较i+1后更大的数进行记录
        for j in i+1..<list.count {
            if list[j] < list[min] {
                min = j
            }
        }
        
        let temp = list[min]
        list[min] = list[i]
        list[i] = temp
    }
    
    print(list)
}

注意简单选择排序中的数据交换是放在第一层for循环内部，当寻找到目标下标才进行数据交换。而冒泡排序的数据交互是放在第二层for循环内，因此排序相同的数据冒泡执行的交换次数会大于或等于选择排序。但是通过仔细分析时间复杂度可以得出，无论是在最好还是最差的情况下，比较的次数都是n*(n-1)/2。所以选择排序的时间复杂度也是O(n^2)。虽然和冒泡排序的时间复杂度相等，但简单选择排序在性能上要略微优于冒泡排序。

插入排序

原理解析

引自维基百科插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

解题步骤

步骤如下：
* 从第一个元素开始，该元素可以认为已经被排序
* 取出下一个元素，在已经排序的元素序列中从后向前扫描
* 如果该元素（已排序）大于新元素，将该元素移到下一位置
* 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
* 将新元素插入到该位置后
* 重复步骤2~5

我们需要整理一个无序数组为［8，3，5，4，6］。
取出第一个数字8，得到新的数组［8］。无序数组变为［3，5，4，6］。
取出第二个数字3，插入新的数组里，3比8小，得到［3，8］。无序数组变为［5，4，6］。
取出第三个数字5，插入新的数组里，5比3大，比8小，得到［3，5，8］。无序数组变为［4，6］。
取出第四个数字4，插入新的数组里，4比3大，比5小，得到［3，4，5，8］。无序数组变为［6］。
最后取出6，插入新数组里，6比5大，比8小，得到［3，4，5，6，8］。排序完成。

我们可以将需要交换位置的数字直接向右移动，然后将新的数字直接复制到正确的位置：

[ 3，5，8，4｜6 ]   记住4
          ＊

[ 3，5，8，8｜6 ]  将8转移到右侧
        -->

[ 3，5，5，8｜6 ]  将5转移到右侧
     -->

[ 3，4，5，8｜6 ]  将4复制粘贴到新的位置
     ＊

实现代码

func insertSort() {//插入排序
    var list = [61,5,33,44,22]
    
    var nlist = [list[0]]//建立一个空数，符合条件的插入，没插入的尾后添加
    for i in 1..<list.count {
        var max: Int? = nil
        for j in 0..<nlist.count {
            if list[i] > nlist[j] {
                max = i
                nlist.insert(list[i], at: j)
                break
            }
        }
        
        if max == nil {
            nlist.append(list[i])
        }
    }
    
    print(nlist)

}

func insertSortOne() {//插入排序 通过交换
    var list = [61,5,33,44,22]
    
    for i in 1..<list.count {
        var y = i//从i往前找，符合条件交换
        
        while y>0 && list[y] > list[y-1] {
            let temp = list[y]
            list[y] = list[y-1]
            list[y-1] = temp
            y -= 1
        }
    }
    
    print(list)
    
}

func insertSortTwo() {//插入排序 通过移动
    var list = [61,5,33,44,22]
    
    for i in 1..<list.count {
        var y = i//从i往前找，符合条件移动
        let temp = list[y]
        while y>0 && temp > list[y-1] {
            list[y] = list[y-1]
            y -= 1
        }
        
        list[y] = temp//找到y赋值
    }
    
    print(list)
    
}

最好的情况下，完全没有任何数据移动，时间复杂度是O(n)。最坏的情况下，比较的次数为 (n+2) (n-1)/2，移动的次数最大值为(n+4) (n-1)/2。如果按照序列的好坏程度是随机的，且概率都是相同的，则平均比较次数以及平均移动次数都约为 n^2/4次，所以时间复杂度为O(n ^ 2)。通过和冒泡以及简单选择排序对比，不难看出直接插入排序的性能稍微比前两者好上一些。

对于插值排序算法来说，O(n^2)是它最差和平均性能表现。因为它的函数里含有两个循环。其它类型的排序算法，比如快速排序和归并排序，在输入数据量很大的情况下，可以达到O(nlogn)的效果。

插值排序对于小数据量的排序来说非常快。在一些标准程序库里，如果数据大小不大于10，它们会用插值排序来取代快速排序。

快速排序

原理解析

引自维基百科快速排序（英语：Quicksort），又称划分交换排序（partition-exchange sort），简称快排，一种排序算法，最早由东尼·霍尔提出。在平均状况下，排序n个项目要O(nlog n)次比较。在最坏状况下则需要 O(n^2)次比较，但这种状况并不常见。事实上，快速排序O(nlog n)通常明显比其他算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地达成。

快速排序（Quicksort）是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

解题步骤

步骤：
* 从数列中挑出一个元素，称为 “基准”（pivot），
* 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
* 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

实现从大到小排序，快排的思想就是从左向右查找，比基准小的交换到右边区域，从右向左查找，比基准大的交换到左边区域。

也就是找到一个pivot，从左向右查找，如果比基准大的，继续查找，比基准小的，记录当前位置，然后从右向左查找，如果比基准小的，继续查找，比基准大的，记录当前位置，然后和左边的记录进行交换，再把基准数和中间数进行交换，保证基准在中间，两边分的区大于或小于基准。查找结束以左边等于右边的查找位置结束，然后继续以上步骤继续分区查找。

根据下图理解步骤

实现代码

func quickSort(list: inout [Int], left: Int, right: Int) {
    if left > right {//左边往右边移，右边往左边移动，最后过了就停止
        return
    }
    
    var i, j, pivot: Int
    
    i = left
    j = right
    pivot = list[left]
    
    while i != j {
        
        while list[j] <= pivot && i < j {//右边大的往左移动
            j -= 1
        }
        
        while list[i] >= pivot && i < j {//左边小的往右移动
            i += 1
        }
        
        if i < j {//找到两个对方区域的值进行交换
            let temp = list[i]
            list[i] = list[j]
            list[j] = temp
        }
    }
    
    list[left] = list[i]//此时i和j相等，处于中间位置，替换pivot值
    list[i] = pivot
    
    //重复以上动作
    quickSort(list: &list, left: left, right: i-1)
    quickSort(list: &list, left: i+1, right: right)
}

快排的时间复杂度为时间复杂度 O(n log n)。最差情况，递归调用 n 次，即空间复杂度为 O(n)。最好情况，递归调用 log n 次，空间复杂度为 O(log n)，空间复杂度一般看最差情况，时间可以平均，但空间一定得满足，所以空间复杂度为 O(n)。

当待排序元素类似[6,1,3,7,3]且基准元素为6时，经过分区，形成[1,3,3,6,7],两个3的相对位置发生了改变，所是快速排序是一种不稳定排序。

堆排序

原理解析

引自维基百科堆排序（英语：Heapsort）是指利用堆 “堆 (数据结构)”)这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

堆排序（Heap Sort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

解题步骤

步骤：
*   最大堆调整（Max_Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
*   创建最大堆（Build_Max_Heap）：将堆所有数据重新排序
*   堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算

通常堆是通过一维数组来实现的。在数组起始位置为0的情形中：

* 父节点 i 的左子节点在位置 (2 * i + 1);
* 父节点 i 的右子节点在位置 (2 * i + 2);
* 子节点 i 的父节点在位置 floor((i - 1) / 2);

floor 函数的作用是向下取整，所以左子节点右子节点都能通过这个公式找到正确的父节点。

最大堆调整（MAX‐HEAPIFY）的作用是保持最大堆的性质，是创建最大堆的核心子程序，作用过程如图所示：

调整大顶堆的公式要准守任意一个节点i可以实现：i>=2i+1，i>=2i+2。也就是父节点大于等于左右两个子节点。

所以从小到大的排序思路是：把一堆数字调整成大顶堆–>堆顶元素和末尾元素交换–>去掉末尾元素，继续大顶堆调整–>重复以上动作

创建最大堆（Build-Max-Heap）的作用是将一个数组改造成一个最大堆，接受数组和堆大小两个参数，Build-Max-Heap 将自下而上的调用 Max-Heapify 来改造数组，建立最大堆。因为 Max-Heapify 能够保证下标 i 的结点之后结点都满足最大堆的性质，所以自下而上的调用 Max-Heapify 能够在改造过程中保持这一性质。如果最大堆的数量元素是 n，那么 Build-Max-Heap 从 Parent(n) 开始，往上依次调用 Max-Heapify。流程如下：

实现代码

func heapSort(arr:inout Array<Int>) {
    //1.构建大顶堆
    for i in (0...(arr.count/2-1)).reversed(){//从二叉树的一边的最后一个节点开始
        //从第一个非叶子结点从下至上，从右至左调整结构
        adjustHeap(arr: &arr, i: i, length: arr.count)
    }
    //2.调整堆结构+交换堆顶元素与末尾元素
    for j in (1...(arr.count-1)).reversed(){
        arr.swapAt(0, j)//将堆顶元素与末尾元素进行交换
        adjustHeap(arr: &arr, i: 0, length: j)//重新对堆进行调整
    }
}

/**
 * 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
 */
func adjustHeap(arr:inout Array<Int>,i:Int,length:Int) {
    var i = i;
    let temp = arr[i];//先取出当前元素i
    var k=2*i+1
    while k<length {//从i结点的左子结点开始，也就是2i+1处开始
        if(k+1<length && arr[k]<arr[k+1]){//如果左子结点小于右子结点，k指向右子结点
            k+=1;
        }
        if(arr[k] > temp){//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
            arr[i] = arr[k];
            i = k;//记录当前节点
        }else{
            break;
        }
        k=k*2+1//下一个节点
    }
    arr[i] = temp;//将temp值放到最终的位置
}

上述代码中总过分为两个for循环。第一个for循环就是将现在的待排序序列构建为一个最大堆，也就是maxHeap()函数的任务。第二个for循环就是逐步将每个最大值的根节点和末尾元素进行交换，然后再调整为最大堆。

在构建堆的过程中，由于是是完全二叉树从最下层最右边非终端节点开始构建，将它与子节点进行比较，对于每个非终端节点而言，最多进行两次比较和交换操作，因此构建堆的时间复杂度为O(n)。在整个排序过程中，第 i 次去堆顶记录重建堆需要时间为logi ,并且需要取 n - 1次堆记录，所以重建对的时间复杂度为O(nlogn)。所以对的时间复杂度为O(nlogn)。
空间上只需一个暂存单元。由于记录的比较是跳跃进行的，所以堆排序是一种不稳定的排序。最后要提醒一点，由于初始构建堆的所需的比较次数比较多。所以，一般不适合排序个数较少的数组。

希尔排序

原理解析

引自维基百科希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

• 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
• 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

与插入排序通过对比相邻的两个元素的大小并在必要时候交换位置，希尔排序是通过比较相隔很远的两个元素。

两个元素之间的距离称为间隔。如果两个元素在比较之后需要交换位置，则直接更换彼此的位置。这个过程减少了插值排序中很多不必要的中间复制过程，即从两个元素更换位置前需要不断交换相邻元素的位置直到目的位置。
这里的最主要的思想就是，元素通过每次移动较大间隔，整个数组可以快速形成局部排序好的情况。这个会让接下来的交换变得更加快速。因为元素之间不需要进行过多次的位置交换。

一旦某一距离长度的间隔比值交换完成，间隔会变得越来越小，然后进行相应间隔的比值交换，这样的过程不断重复，直到间隔为1，也就是与插值排序同样过程的情况。然而，在希尔排序中，由于大部分数据在此时已经整理完毕，所以最后间隔为1的比值交换速度非常快。

解题步骤

步骤如下：
* 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
* 随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

以n=10的一个数组49, 38, 65, 97, 26, 13, 27, 49, 55, 4为例

第一次增量 gap = 10 / 2 = 5

49   38   65   97   26   13   27   49   55   4

1A                       1B

     2A                       2B

          3A                       3B

               4A                       4B

                    5A                       5B

1A,1B，2A,2B等为分组标记，数字相同的表示在同一组，大写字母表示是该组的第几个元素， 每次对同一组的数据进行直接插入排序。即分成了五组(49, 13) (38, 27) (65, 49) (97, 55) (26, 4)这样每组排序后就变成了(13, 49) (27, 38) (49, 65) (55, 97) (4, 26)，下同。

第二次增量 gap = 5 / 2 = 2

13   27   49   55   4    49   38   65   97   26

1A        1B        1C        1D        1E

     2A        2B        2C        2D        2E

第三次增量 gap = 2 / 2 = 1

4   26   13   27   38    49   49   55   97   65

1A  1B   1C   1D   1E    1F   1G   1H   1I   1J

第四次增量 gap = 1 / 2 = 0 排序完成得到数组：

4   13   26   27   38    49   49   55   65   97

实现代码

func shellSort(arr: inout [Int]) {//希尔排序
    var j: Int
    var gap = arr.count / 2//获取增量
    
    while  gap > 0 {
        for i in 0 ..< gap {
            j = i + gap
            while j < arr.count {
                if arr[j] < arr[j - gap] {
                    let temp = arr[j]
                    var k = j - gap
                    while (k >= 0 && arr[k] > temp) {//插入排序
                        arr[k + gap] = arr[k]
                        k -= gap
                    }
                    arr[k + gap] = temp
                }
                
                j += gap
            }
            
        }
        gap /= 2//增量减半
    }
}

• 希尔排序时间复杂度
  希尔排序的时间复杂度与增量(即，步长gap)的选取有关。例如，当增量为1时，希尔排序退化成了直接插入排序，此时的时间复杂度为O(N²)，而Hibbard增量的希尔排序的时间复杂度为O(N3/2)。

• 希尔排序稳定性
  希尔排序是不稳定的算法，它满足稳定算法的定义。对于相同的两个数，可能由于分在不同的组中而导致它们的顺序发生变化。
  算法稳定性 – 假设在数列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。则这个排序算法是稳定的！