iOS 开发 - 数据结构与算法学习之排序篇

作者：iOSer

2022 年 1 月 10 日
本文字数：16447 字
阅读完需：约 54 分钟

（一）冒泡排序

摘要冒泡排序相对来说，多少都有些了解，就是多循环几轮，每一轮找出最大值放在尾部，直到数组中的元素有序为止。
在这基础上，探讨一下有没有高阶的方法，比如 1.提前结束循环，或者 2.循环中提前终止，进行下一个循环。这个是要探讨的重点
算法这部分用的编辑语言是 JAVA，编译工具是 Eclipse，JAVA 与 Swift 有些不同，逻辑是相通的，咱的核心就是看逻辑，尽量不要把自己局限在某一种代码语言中。

##逻辑将序列中的元素按照一定的比较规则每每相邻的元素比较并交换。直到序列完全有序为止。

流程

这里是将一个序列处理成从小到大的有序序列：

从头开始比较每一对相邻元素，如果第一个比第二个大，就交换它们的位置。最后一个元素就是最大的元素。
忽略上一步中找到的最大元素，继续 1 中的操作，直到全部元素有序为止。实现

循环从尾部开始循环，进行相邻元素比较和交换。让每一轮获得的最大元素放到尾部，下次循环避开最大元素坐标

    for (int end = array.length-1; end > 0; end--) {        for (int begin = 1; begin <= end; begin++) {            if (cmp(begin, begin-1) < 0) {                swap(begin, begin-1);            }        }    }

复制代码

技巧

Q：为什么大循环从尾部开始？A：示例中是将每一轮大的值放在尾部，为了下次循环避开尾部，所以从尾部开始。

Q：可以更加高效吗？A：可以从两个方面来提高它的效率

某一次循环中已经完全有序，则可以终止。序列尾部已经达到局部有序，那么就可以不再遍历这部分这两种可以通过设置标示实现。具体可以看进阶部分

进阶（含两个）

如果序列已经完全有序，可以提前终止循环。

在每一次循环中设置 isSorted（已经有序）标示，如果在遍历中发生了交换，就设置为 false，在遍历结束后判断这个标示，如果是 true 就证明整个序列已经有序，退出循环。

    for (int end = array.length - 1; end > 0; end--) {        boolean isSorted = true;        for (int begin = 1; begin <= end; begin++) {            if (cmp(begin, begin-1) < 0) {                swap(begin, begin-1);                isSorted = false;            }        }        if (isSorted) break;    }

复制代码

如果序列尾部已经局部有序，可以记录最后一次交换的位置，减少交换的次数

sortedIndex 是在遍历完成后，记录了最后发生交换的位置，从这个位置到序列的尾部，没有发生交换，即这部分的元素是有序的，下次遍历就不用再遍历这部分了。

    for (int end = array.length - 1; end > 0; end--) {        // sortedIndex 的初始值在数组完全有序的时候有用        int sortedIndex = 1; // sortedIndex 的值可以是其他值，-1 或者其他。目的是达到有序的时候就不需要再进行下面的代码        for (int begin = 1; begin <= end; begin++) {            if (cmp(begin, begin-1) < 0) {                swap(begin, begin-1);                sortedIndex = begin;            }        }        end = sortedIndex;    }

复制代码

时间和空间复杂度

最好、平均时间复杂度：O(n^2)
最坏时间复杂度：O(n)
空间复杂度：O(1)

（二）选择排序

摘要
选择排序的逻辑是先遍历比较出序列中最大的，然后把最大的放在最后位置。
遵循这个逻辑，用代码实现时，做到 1.减少比较次数之外，这里引入一个新的指标 - 稳定性，2.保证排序过程中的稳定性也是一个优化处理

代码逻辑

从头遍历序列，分别和尾部元素比较，记录最大的元素坐标遍历完成后，和尾部位置交换位置忽略尾部已经交换的元素，执行 1 和 2 步骤

实现

依据逻辑来看，最大值是放在尾部，并放置后，下次循环排除这个放置最大值的位置，for 循环从尾部开始最合适。

小循环开始前，需要先创建变量记录最大值坐标，这里使用的是 0 位置坐标，那么小循环开始时，就可以直接从 1 位置遍历，这就减少比较次数。

    for (int end = array.length-1; end > 0; end--) {        int maxIndex = 0;        for (int begin = 1; begin <= end; begin++) {            if (cmp(maxIndex, begin) < 0) {                maxIndex = begin;            }        }        swap(maxIndex, end);    }

复制代码

进阶

开始前，先解释一下稳定性，稳定性是尽量保持序列中两个元素在排序前和排序后的相对位置。比如下面伪代码：

// a1 与 a2 的值相等a1 = a2 = 3
// 序列中 a1 值的位置在 a2 前面array = [5, a1, 4, a2, 2]
// 排序之后, a1 值位置在 a2 前面，保持了稳定性array = [2, a1, a2, 4, 5]

复制代码

为什么稳定性重要？

序列中需要保证多次排序后数据位置的相对稳定。比如信息表中，以 age 从小到大排序，不希望 age 相等的一组数据中，它的名称在每一次排序之后都会有不同的顺序。

稳定性的优化

这里为了保证排序之后的稳定性，就当出现最大值时，也更新最大值的坐标。

为什么这样就可以保证稳定性？

首先最大值被交换到尾部之后，下次遍历比较的时候，就不再比较这个位置，小循环的比较是从头开始的，如果出现等于最大值时，不更新最大值的位置，排序之后，相等的值，最靠前的值就被放在了最后面，改变了之前序列中相等值的相对位置。

    for (int end = array.length-1; end > 0; end--) {        int maxIndex = 0;        for (int begin = 1; begin <= end; begin++) {            if (cmp(maxIndex, begin) <= 0) { // 保证稳定性                maxIndex = begin;            }        }        swap(maxIndex, end);    }

复制代码

时间和空间复杂度

最好、平均、最坏时间复杂度：O(n^2)，n 的 2 次方
空间复杂度：O(1)
属于稳定排序

（三）插入排序

摘要
插入排序是先假定一部分序列是有序的，这部分序列也可以是 0 个元素。另外需要排序的元素就一个个的插入到这个有序的序列中。因为要插入的序列本来就是有序的，所以只要找到合适的插入位置，那么就可以结束这轮循环。
代码中处理的就是界定遍历边界，和减少遍历次数，提高效率。这里的有序序列是元素从左开始，由小到大。

逻辑

这里可以想象扑克牌排序，手中拿着一组由小到大的牌，每次拿起一张牌，就会插入到合适的位置，继续保持由小到大的牌面。

这里提高效率，主要是保持序列的空间长度，在原有的序列中操作，不额外创建新的序列空间。

流程

1、执行过程中，会分为两部分：

头部已经排序好的
尾部等待排序的

2、从头扫描每一个元素：

每当扫描到一个元素，就将它插入到头部合适的位置，依然保持头部有序
插入位置的元素序列就统一往后移动

实现

在遍历序列时，会有一个 begin 做界限，begin 之前的序列部分是有序的，后面的部分是无序的。

每一次就是把 begin 位置上的元素插入到有序的部分中，先看代码：

for (int begin = 0; begin < array.length; begin++) {    int cur = begin;    while (cur > 0 && cmp(cur, cur - 1) < 0) {        swap(cur, cur - 1);        cur--;    }}

复制代码

代码中有两个继续 while（插入循环）的条件，第一个是 cur > 0, 防止序列索引越界。

另外一个是 cmp 方法，因为上面说过 begin 之前的序列是有序的，所以当发现一次前一个位置的值小于或等于当前位置的值，那么就可以结束。不可能再出现前一个位置元素大于当前位置元素的情况了。

这就是减少遍历比较的有底气的地方。

进阶

上面代码中可以看到，每发现符合 while 条件的，就交换元素位置，这里就将交换转换为挪动：

先备份备份待插入元素
头部有序数组中比待插入元素大的，向后移动一位
将待插入元素放入到最终合适的位置

for (int begin = 0; begin < array.length; begin++) {    int cur = begin;    E v = array[cur];    while (cur > 0 && cmp(v, array[cur-1]) < 0) {        array[cur] = array[cur-1];        cur--;    }    array[cur] = v;}

复制代码

逆序对（Inversion）

逆序对(自己的理解)：

在序列中，出现违反有序原则的每一对元素，都是逆序对，这一对元素不需要相邻，这对元素可以被重复和其他元素配对，成为一对新的逆序对，下看面例子

数组 [2,7,4,5,9,8] 的逆序对有 [7,4]、[7,5]、[9,8]

接下来可以思考一下，能影响到插入排序的因素是什么，整体看下来，序列中当发现有逆序对，才进行交换并继续遍历下一个。发现一个不是逆序对的，就结束遍历了。

那么就可以总结，插入排序的时间复杂度和序列中的逆序对的数量成正比。

时间和空间复杂度

最坏、平均时间复杂度：O(n^2)
最好时间复杂度：O(n)
空间复杂度：O(1)
属于稳定排序

（四）归并排序

摘要
归并排序就是将序列不断向下拆分成最小的序列（只有两个元素），然后从这个地方开始排序，然后向上合并成新的序列和排序，直到合并为一个序列（这时，这个序列就是有序的）
代码实现上用了递归的思路处理，归并排序在时间复杂度上比前 3 种有优势，具体可以用到什么样的场景，暂时没有想到，就先学习下逻辑，增长见识。

逻辑

归并排序多少有些空间换取时间的思想，所以代码实现中会创建一个临时的序列。具体的逻辑如下：

将序列不断平均分成两个子序列，直到各子序列中只有一个元素
不断合并子序列为有序序列，直到成为一个序列为止

实现

创建一个长度是序列一半长度的临时序列，用于序列的合并。

    leftArray = (E[])new Comparable[array.length >> 1];
    sort(0, array.length);

复制代码

这里是递归的思想，将序列不断拆分到最小单位（只有两个元素）。这个递归稍微一些难理解它的执行顺序，这里特别梳理一下。

递归思路：

方法中存在递归代码时，当代码执行到递归方法处，会直接执行递归方法，直到满足结束条件时，会一层层返回，并执行递归方法之后的代码块。

这里也就可以推断出，凡是使用递归方法，必须要有一个终止递归的条件，否则递归方法会进入死循环。

大致的执行循序是通过递归一直拆分，直到元素小于等于 2 个的时候，就向上返回，并执行 merge 方法来合并序列。

/* * 对 [begin, end) 范围的数据进行归并排序 * */private void sort(int begin, int end) {    if (end - begin < 2) return;
    int mid = (begin + end) >> 1;    sort(begin, mid);    sort(mid, end);    merge(begin, mid, end);}

复制代码

合并排序有两点比较有意思的处理：

看 while 循环时，为什么只判断 li<le，不用判断右侧？因为左侧是临时序列，这里要将有序的元素依次放入 array 中，所以只需要考虑两种极端情况，临时序列都比右侧小，那么临时序列元素放进去后，右侧序列是不需要动的。右侧序列都比临时序列小，那么就会整体把右侧序列往前放，放完之后是不会结束 while 循环，会继续将临时序列放进去，直到临时序列元素放完。
这里看 array 一直只有一个，所以这个序列中的部分位置有序也是在 array 上操作，为了达到这个效果，就用 begin 和 end 来获得到在序列中的真实位置。这样的处理好处就是不用额外创建空间来处理。

在排序的时候有一个疑问，难道不会有左侧序列或者右侧序列本就不是有序的吗？

答案肯定是不会。因为递归思想来看，当执行完合并排序，才会向上执行，在上层再执行合并排序时，这个序列已经在下层排序完成了。

private void merge(int begin, int mid, int end) {    int li = 0, le = mid - begin;    int ri = mid, re = end;    int ai = begin;
    // 备份左边数组    for (int i = li; i < le; i++) {        leftArray[i] = array[begin + i];    }
    // 如果左边没有结束    while (li < le) {        if (ri < re && cmp(array[ri], leftArray[li]) < 0) { // 增加稳定性            array[ai++] = array[ri++];        } else {            array[ai++] = leftArray[li++];        }    }}

复制代码

代码中的合并思路，可以用到合并两个有序序列的场景中，是一个非常好的思想。

时间和空间复杂度

最坏、平均时间复杂度：O(nlogn)
最好时间复杂度：O(nlogn)
空间复杂度：O(n)
属于稳定排序

（五）快速排序

摘要
快速排序和归并排序有一些相似的地方，就是在中间位置拆分成两部分，分别做处理。
这里也是用到递归思想，但是与归并排序的先拆分再排序处理的思想不同，快速排序是先处理排序，然后再拆分。

本质

每一次确定一个轴点元素，然后和序列中的其他元素比较，放在元素的左右任何位置位置，完成之后，这个轴点元素的位置就明确了。

理解这个快速应该就是去搞定一个元素的位置，不管其他元素元素位置，就少了比较处理（因为绝情，所以快吗？- 我的理解）

逻辑

序列中选择一个元素，设置为轴点元素（pivot）
利用 pivot 将序列分割成两个子序列
把小于 pivot 的元素放在序列的左侧
把大于 pivot 的元素放在序列的右侧
把等于 pivot 的元素可以放在左侧或者右侧都可
将子序列继续进行如上 1 2 的操作，直到无法再进行分割为止

流程

以 0 坐标为轴点，随机获取轴点元素，和 0 位置元素更换
序列头尾元素交替和轴点元素比较和调整替换，将小于轴点元素放在轴点坐标左侧，大于轴点元素放在轴点坐标右侧。
以轴点元素为中线，分割成两个子序列，继续 1 2 操作（递归性质）
直到首尾坐标相等（即序列中只有一个元素）为止

实现

将序列分为子序列的递归方法。凡是递归方法，必须要有终止递归的判断条件，否则会造成死循环，需要特别注意

    /**     * 在 [begin, end) 范围内进行比较     * @param begin     * @param end     */    private void sort(int begin, int end) {        if ((end - begin) < 2) return;
        int mid = pivotIndex(begin, end);        // 分割为两个子序列        sort(begin, mid);        sort(mid+1, end);    }

复制代码

以轴点坐标分割线，调整序列中的的元素，并返回新的轴点坐标。当已经比较交换完成轴点坐标时，一定要将轴点元素赋值到新的轴点坐标中。

这里的代码有一个巧妙的点，就是比较并交换头尾位置

这里用大循环嵌套两个小循环的方式，达到头部和尾部交替和轴点元素比较并交换位置，这个方式非常巧妙。

首先咱要明确目的，就是序列中小于轴点的元素放在它的左边，大于轴点的元素放在它的右边。在不增加额外内存空间的情况下，就可以用这样的方式去处理。

具体的逻辑可以着重看一下代码，这里说几个需要注意的点

这里的比较是首尾交替比较，用三个 while 循环达到这样的目的
begin 和 end 就相当于两个指针，通过交换之后就变换比较的方向，这一点非常巧妙。

    /**     * 在 [begin, end) 返回内构造轴点坐标     * @param begin     * @param end     * @return     */    private int pivotIndex(int begin, int end) {        // 通过随机数获取坐标(begin 和 end 范围内），和 begin 坐标元素进行交换，避免出现 2^n        swap(begin, begin + (int)(Math.random()*(end - begin)));        // 轴点元素        E pivot = array[begin];
        // end 指向最后一个元素        end--;
        // 头部尾部交替比较        while (begin < end) {            // 尾部进行比较            while (begin < end) {                if (cmp(pivot, array[end]) < 0) {                    end--;                } else {                    array[begin] = array[end];                    begin++;                    break;                }            }
            // 头部比较            while (begin < end) {                if (cmp(pivot, array[begin]) > 0) {                    begin ++;                } else {                    array[end] = array[begin];                    end--;                    break;                }            }        }
        // 将轴点元素放入最终的位置        array[begin] = pivot;        return begin;    }

复制代码

问题

Q：为什么获取轴点坐标开始时，要获取序列中的随机一个元素和轴点坐标元素交换？A：防止轴点左右元素数量极端不均匀

Q：序列的边界是怎么设置的，为什么要这样处理？A：序列边界是 [begin, end),左闭右开，这样设置方便能获取序列的长度，最后一个坐标也可以很好获得

进阶

随机选择轴点元素。这是防止例如序列是从大到小的有序序列这种极端情况出现。

时间和空间复杂度

最好、平均时间复杂度：O(nlogn)
最坏时间复杂度：O(n^2)
空间复杂度：O(logn)
属于不稳定排序

（六）堆排序

摘要
堆排序需要用到一种数据结构，大顶堆。大顶堆是一种二叉树结构，本质是父节点的数大于它的左右子节点的数，左右子节点的大小顺序不限制，也就是根节点是最大的值。
这里就是不断的将大顶堆的根节点的元素和尾部元素交换，交换到大顶堆没有可以被交换的元素为止。后面再说大顶堆的逻辑。

逻辑

首先将序列通过大顶堆排序。然后不断的从堆中取出顶部元素放在尾部，直到大顶堆元素为空。

流程

对序列进行原地建堆操作
重复下面操作，直到堆元素数量为 1a. 交换堆顶元素与尾元素 b. 堆的元素数量减 1c. 对 0 位置进行 1 次自下而上的下滤

下面在代码中解释原地建堆和自下而上的下滤这两个词的逻辑。

实现

首先进行原地建堆。原地建堆是先将序列按照大顶堆的排序逻辑处理序列。

大顶堆的序列逻辑是父节点的值大于它的左右子节点的值，可以想象成一个二叉树。这里的原地排序用到了 siftDown 方法，而且在循环中只循环到序列一半数量，为什么？这个在下面看 siftDown 方法时详细探究一下。

// 原地建堆// 自下而上的下滤heapSize = array.length;for (int i = (heapSize >> 1) - 1; i >= 0; i--) {    siftDown(i);}

复制代码

交换堆顶和尾部元素，然后将需要比较的序列元素数量减少 1，并将要进行比较的序列再使用 siftDown 方法过滤，保持序列的大顶堆的性质。然后继续开始的交换，直到可以比较的序列数量为 1 就截止。

while (heapSize > 1) {    // 交换堆顶元素和尾部元素    swap(0, --heapSize);
    // 对 0 位置进行 siftDown（恢复堆的性质）    siftDown(0);}

复制代码

大顶堆的 siftDown 方法

这里来探究一下 siftDown（下滤）。

二叉树的父节点和子节点的关系符合这样的公式
leftChilder = partner * 2 + 1
rightChilder = parnter * 2 + 1 + 1
half （叶子）节点的数量是总节点数量的 1/2

siftDown 方法主要是将 index 位置上的元素放在合适的位置上。那么什么位置是合适的位置呢？

依据大顶堆的父节点值大于左右子节点的值的性质来看，只要是保证 index 位置的元素大于它的左右子节点就好。

看下面代码，如果 index < half 才进行循环比较，那么就有一个问题，当 index >= half 为什么不用比较？

这就要提到很巧妙的点，首先看大顶堆的性质，左右子节点没有具体顺序的要求，其次子节点的值小于父节点。那么就可以依据二叉树的叶子节点性质，如果 index 的位置是在叶子节点位置，那么就本来比它的父节点要小，就不用比较（这个是建立在序列本来符合大顶堆的顺序，出现一个位置的元素有变化时进行的过滤处理）。

这也是上面的原地排序中，只从一半的位置开始，是因为从这个位置开始，肯定会给它的子节点比较，过滤出大的，并放在合适位置。

代码中有三个巧妙的点

循环从序列的一半位置开始比较，如果位置不在前半部分，就不进行比较，这个在上面分析过
在比较的时候，获取到它左右子节点中最大的节点比较。在获取右子节点的时候看右子节点是否存在 rightIndex<heapSize。因为大顶堆是符合完全二叉树的（尽量往左子树安排元素）。
说是二叉树，但是没有实际的节点，还是一个线性序列，通过公式来获取左右子树的位置，这个就是心中有树，没有树也是树

/* * 让 index 位置的元素下滤 */private void siftDown(int index) {    E element = array[index];
    int half = heapSize >> 1; // 取出非叶子节点    // 第一个叶子结点的索引 == 非叶子节点的数量    // 必须保证 index 是非叶子节点    while (index < half) {        // index 的节点有2种情况        // 1、只有左子节点        // 2、同时有左右子节点
        // 默认左子节点跟它进行比较        int childIndex = (index << 1) + 1;        E child = array[childIndex];        // 右子节点        int rightIndex = childIndex + 1;        if (rightIndex < heapSize && cmp(array[rightIndex], child) > 0) {            child = array[ childIndex = rightIndex];        }
        if (cmp(child, element) < 0) break;
        // 将子节点存放到index位置        array[index] = child;        // 重新设置 index        index = childIndex;    }    array[index] = element;}

复制代码

时间和空间复杂度

最好、平均时间复杂度：O(nlogn)
最坏时间复杂度：O((nlogn)
空间复杂度：O(1)
属于不稳定排序

题外话

这次的排序用到了二叉树和大顶堆的一些知识，可能看下来有诸多疑问，这里就先请诸位看官有个印象，后续我会分享二叉树的知识，然后在回过头来看堆排序，会让你思路大开。

（七）希尔排序

摘要
看希尔排序需要先想象出一个二维的矩阵，在这个矩阵中，有多少列数据全看步长（一定的规则得到）。处理完之后，就再接着用另一个步长组成矩阵处理。直到步长全部使用完。
这里的巧妙之处就是没有把序列先处理成二维数组，而是通过与步长配合，依旧在一维的序列中处理。

逻辑

希尔排序相当于把序列当作一个矩阵，逐列进行排序。当全部排序完成，整个序列就完全有序

矩阵的列数取决于步长序列

流程

创建步长序列
从最大步长开始，整列排序，直到排序完成

实现

创建步长序列，这里是有一个数组存放步长数据。步长是序列的长度减半直到步长为 0 结束。这里必定会有步长是 1 的数据，所以不用担心序列没有完全排序完。

List<Integer> shellStepSequence() {    List<Integer> stepSequence = new ArrayList<>();    int step = array.length;    while ((step >>= 1) > 0) {        stepSequence.add(step);    }    return stepSequence;}

复制代码

按照步长序列遍历，序列就会按照不同的步长去处理排序。然后通过不断地缩小步长来使得序列逐渐成为一维的序列。

    List<Integer> stepSequence = shellStepSequence();    for (Integer step : stepSequence) {        sort(step);    }

复制代码

把每一列进行排序。数组中的索引是 col+rowstep。这个地方就是巧妙的地方了，通过 col+rowstep 来处理每一列中的元素比较排序处理。用这种方式就相当于把一个一维数组给拆分成每一行最多有 step 的元素的多列序列，即二维数组。

而这里的巧妙就是，给我们营造了一个二维序列的空间，实际的比较和交换逻辑还是在一维数组上进行，不用额外创造空间，这样的逻辑，真的是牛。

/* * 分成 step 列进行排序 */void sort(int step) {    // col： 第几列    for (int col = 0; col < step; col++) {        // 对第 col 列进行排序        // 对 [0, array.length) 进行插入排序        for (int begin = col + step; begin < array.length; begin+=step) {            int cur = begin;            while (cur > col && cmp(cur, cur - step) < 0) {                swap(cur, cur - step);                cur -= step;            }        }    }}

复制代码

时间和空间复杂度

最好、平均时间复杂度：O(1)
最坏时间复杂度：O(n^2)
空间复杂度：O(1)
属于不稳定排序

（八）计数排序

摘要
计数排序本质就是统计不同元素出现的次数，然后将元素依次从小到大放置，每个元素看统> 计的次数，就紧挨着放置几个同样的元素。
看似简单的处理，在算法中，会依据统计的元素次数推算出每个元素的索引位置，这就是算法的魅力。

逻辑

统计每个整数在序列中出现的次数，进而推导出每个整数在有序序列中的索引。

这是通过空间换取时间的方式。

流程

获取序列中的最大值
统计每个元素出现的次数
按照顺序进行赋值

实现

根据获取到的最大值，创建序列统计序列中的元素出现的次数。创建的序列大小是 max+1，让最大值也可以放在统计序列中。

    // 找出最大值    int max = array[0];    for (int i = 1; i < array.length; i++) {        if (array[i] > max) {            max = array[i];        }    }    // 开辟内存空间，存储每个整数出现的次数    int[] counts = new int[1 + max];counts 数组的索引就是序列中的元素，存放的是序列中元素出现的次数。
    // 统计每个整数出现的次数    for (int i = 0; i < array.length; i++) {        counts[array[i]]++;    }

复制代码

现在就通过遍历 counts 数组排序序列中的元素，这里设置一个 index 变量，用于多次出现的元素，每放置一个元素，index 就减 1，直到 index 为 0 时，再遍历下一个索引位置。

    // 根据整数出现次数，对整数进行排序    int index = 0;    for (int i = 0; i < counts.length; i++) {        while (counts[i]-- > 0) {            array[index++] = i;        }    }

复制代码

缺点

无法对负整数进行排序，这里只能排序 0 到 max 元素的序列极其浪费内存空间是不稳定的排序

进阶

看上面实现计数排序的缺点，这里就去更改它的缺点。

可以对负整数排序，获取序列中的 min 和 max，创建计数数组的长度为 max-min。在计数数组中，当前位置 count 加上上一个位置的 count。那么当前元素在序列中的索引就是计数数组中的 count - 1。

比较难理解的是计数数组的 count 和 array 元素的索引的对应关系。

这块可以理解，计数数组中存放着该元素的起始位置和有几个相同的元素。即类似于 range(index, count) 的情况

首先是找到序列中的 min 和 max。

    // 找出最大值    int max = array[0];    int min = array[0];    for (int i = 1; i < array.length; i++) {        if (array[i] > max) {            max = array[i];        }        if (array[i] < min) {            min = array[i];        }    }

复制代码

接下来就是计数排序的重点了。这里做了两次处理，第一次统计序列中元素出现的次数。第二次将统计数组中每个索引位置的数字加上前一个索引位置的数字。这就可以计算出每个元素在序列中的位置就是 array[i]-min

    // 开辟内存空间，存储次数                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    int[] counts = new int[max-min+1];    // 统计每个整数出现的次数    for (int i = 0; i < array.length; i++) {        counts[array[i]-min]++;    }    // 累加次数    for (int i = 1; i < counts.length; i++) {        counts[i] += counts[i-1];    }

复制代码

最后将序列从后往前遍历，通过计算出的索引，依次排序。从最后开始遍历就是增加序列的稳定性。

    // 从后往前遍历数组，放在有序数组中的位置    int[] newArray = new int[array.length];    for (int i = array.length - 1; i >= 0; i--) {        newArray[--counts[array[i]-min]] = array[i];    }    // 将有序数组覆盖到 array    for (int i = 0; i < newArray.length; i++) {        array[i] = newArray[i];    }

复制代码

技巧点/注意点

计数数组中的索引是序列元素-min 从后往前遍历数组，是保证数组的稳定性，如果从头开始，相同元素在原来数组中的相对位置会发生变化计数数组中的 count 在赋值一次后要进行 -- 操作。计数排序的精妙点就在通过两次的统计，就可以计算出每个元素在序列中的位置。

时间和空间复杂度

最好、最坏、平均时间复杂度：O(n+k)
空间复杂度：O(n+k)
属于稳定排序

k 是整数的取值范围

（九）基数排序

摘要
基数排序是进行整数序列的排序，它是将整数从个位开始，直到最大数的最后一位截止，每一个进位（比如个位、十位、百位）的数进行排序比较。
每个进位做的排序比较是用计数排序的方式处理，所以基数排序离不开计数排序。

逻辑

对整数依次从个位数、十位数...进行排序。基数排序非常适合用于整数排序

对每一轮的排序可以使用计数排序的方法处理

基数排序和计数排序来做个简单的比较时，可以看到基数排序每一个进位都要进行一次计数排序，所以比较循环多一些。但是每个进制上的数范围是 0 到 9 这 10 个数，所以需要开辟的空间相对可控和少一些。下面来详细了解一下。

流程

获取序列中的最大值，确定排序的最大位数
从个位起，使用计数排序的方式处理序列

实现

找出最大值, max 的初始值为序列的 first 元素。循环从 1 开始。

    int max = array[0];    for (int i = 1; i < array.length; i++) {        if (array[i] > max) {            max = array[i];        }    }

复制代码

对序列从个位开始排序（计数排序的方式）。这里要留意，divider 的每一次增加是 divider *= 10，相当于向前进一位。

这里的每一轮比较排序中，交换的是序列中的元素，而不是某个进位上的数字，这个要特别注意。

    for (int divider = 1; divider <= max; divider *= 10) {        CountingSort(divider);    }

复制代码

下面的排序就是用计数排序来处理，对计数排序不太明白的可以看上一期介绍计数排序。

这里有两点需要留意：

这里直接开辟了 10 个存储空间，是因为，每一个进位上的数只有 0 到 9 这 10 个数
这里通过 divider % 10 这个方式获取到该进位上的数字。

    private void CountingSort(int divider) {
        // 开辟内存空间，存储次数        int[] counts = new int[10];        // 统计每个整数出现的次数        for (int i = 0; i < array.length; i++) {            counts[array[i] / divider % 10]++;        }        // 累加次数        for (int i = 1; i < counts.length; i++) {            counts[i] += counts[i-1];        }
        // 从后往前遍历数组，放在有序数组中的位置        int[] newArray = new int[array.length];        for (int i = array.length - 1; i >= 0; i--) {            newArray[--counts[array[i] / divider % 10]] = array[i];        }        // 将有序数组覆盖到 array        for (int i = 0; i < newArray.length; i++) {            array[i] = newArray[i];        }    }

复制代码

时间和空间复杂度

最好、最坏、平均时间复杂度：O(d*(n+k))
空间复杂度：O(n+k)
属于稳定排序

d 是最大值的位数，k 是进制

（十）桶排序

摘要
桶排序和基数排序类似，相当于基数排序的另外一种逻辑。它是将取值范围当做创建桶的数量，桶的长度就是序列的大小。通过处理比较元素的数值，把元素放在桶的特定位置，然后遍历桶，就可以得到有序的序列。

逻辑

创建一定数量的桶（数组或者链表）。制定规则将序列中的元素均匀地分布在不同的桶中。然后对每个桶内排序，最后合并非空的桶。

流程

创建一定数量的桶
元素均匀分布在桶中（根据规则来看）
桶内排序
合并非空的桶

下面还用无序的整数元素序列，将这个序列给排序有序。

实现

获取序列中的最大值，这里按照最大值有多少位，来确定外部循环多少次后得到有序的序列，也就是每一位都会循环遍历比较。

    // 获取最大值    int max = array[0];    for (int i = 1; i < array.length; i++) {        if (max < array[i]) {            max = array[i];        }    }

复制代码

桶排序实现方法

每一个整数的进制位是 0 到 9 这 10 个数，所以这里就创建 10 个桶，分别对应这 10 个数，每个桶的高度就是序列的长度。

下一步就是创建记录每个桶大小的数组，来放置元素个数，在取出桶中的元素时，就可以确定遍历的长度，减少遍历无用的空间。同时这是元素在桶中的索引位置。

    // 桶数组    int[][] buckets = new int[10][array.length];    // 每个桶中的元素数量    int[] bucketSizes = new int[buckets.length];

复制代码

接下来，就是根据最大值的进位数量，从个位进位开始对元素进行处理排序，bucketSizes记录对应位置数值的数量，并提供给 buckets 数组在桶中的元素索引位置。

这里比较难理解一些，比如有 23 和 43 这两个数据，若从个位开始处理，因为个位都是 3，那么放在桶中的位置应该是 buckets[3][0]。如果是这样，23 会被后来的 43 覆盖。那么就用一个记录 3 数值出现次数的数组，即 bucketSizes[3]，当存放 23 之后，bucketSizes[3] 加 1, 那么后面放 43 的时候，它的位置就是 buckets[3][1], 避免了覆盖。

当所有元素放置完成之后，就遍历 buckets 桶，依次取出元素，在遍历桶循环时，每个桶遍历的最大值就是 bucketSizes 中的数量，就不需要把桶的长度全部遍历完，减少遍历次数。

    for (int divider = 1; divider <= max; divider *= 10) {        for (int i = 0; i < array.length; i++) {            int no = array[i] / divider % 10;            buckets[no][bucketSizes[no] ++] = array[i];        }    }
    int index = 0;    for (int i = 0; i < buckets.length; i++) {        for (int j = 0; j < bucketSizes[i]; j++) {            array[index ++] = buckets[i][j];        }        bucketSizes[i] = 0;    }

复制代码

时间和空间复杂度

时间复杂度：O(n + n * logn - n * logm)
空间复杂度：O(n+m)
属于稳定排序

m 是桶的数量

面试基础

iOS 面试基础知识（一）
https://github.com/iOS-Mayday/heji
iOS 面试基础知识（二）
https://github.com/iOS-Mayday/heji
iOS 面试基础知识（三）
https://github.com/iOS-Mayday/heji
iOS 面试基础知识（四）
https://github.com/iOS-Mayday/heji
iOS 面试基础知识（五）
https://github.com/iOS-Mayday/heji

发布于: 刚刚阅读数: 2

iOSer

关注

微信搜索添加微信 mayday1739 进微信群哦 2020.09.12 加入

更多大厂面试资料进企鹅群931542608

发布

暂无评论

创作场景

iOS 开发 - 数据结构与算法学习之排序篇

（一）冒泡排序

流程

技巧

进阶（含两个）

时间和空间复杂度

（二）选择排序

代码逻辑

实现

进阶

为什么稳定性重要？

稳定性的优化

时间和空间复杂度

（三）插入排序

逻辑

流程

实现

进阶

逆序对（Inversion）

时间和空间复杂度

（四）归并排序

逻辑

实现

递归思路：

合并排序有两点比较有意思的处理：

在排序的时候有一个疑问，难道不会有左侧序列或者右侧序列本就不是有序的吗？

时间和空间复杂度

（五）快速排序

本质

逻辑

流程

实现

问题

进阶

时间和空间复杂度

（六）堆排序

逻辑

流程

实现

大顶堆的 siftDown 方法

代码中有三个巧妙的点

时间和空间复杂度

题外话

（七）希尔排序

逻辑

流程

实现

时间和空间复杂度

（八）计数排序

逻辑

流程

实现

缺点

进阶

技巧点/注意点

时间和空间复杂度

（九）基数排序

逻辑

流程

实现

时间和空间复杂度

（十）桶排序

逻辑

流程

实现

桶排序实现方法

时间和空间复杂度

面试基础

iOSer

评论