排序算法

回顾

我们前面已经介绍了 3 种最常见的排序算法：

java 实现冒泡排序讲解

QuickSort 快速排序到底快在哪里？

SelectionSort 选择排序算法详解（java 实现）

然而天下排序千千万，今天老马就和大家一起把最常见的几种都学习一遍。

堆排序

堆排序（英语：Heapsort）是指利用堆这种数据结构所设计的一种排序算法。

堆是一个近似完全二叉树的结构，并同时满足堆的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。

最大堆

若以升序排序说明，把数组转换成最大堆(Max-Heap Heap)，这是一种满足最大堆性质(Max-Heap Property)的二叉树：对于除了根之外的每个节点i, A[parent(i)] ≥ A[i]。

堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：

重复从最大堆取出数值最大的结点(把根结点和最后一个结点交换，把交换后的最后一个结点移出堆)，并让残余的堆维持最大堆性质。

输入图片说明

同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子:

输入图片说明

堆节点的访问

通常堆是通过一维数组来实现的。

在数组起始位置为0的情形中：

则父节点和子节点的位置关系如下：

(01) 索引为i的左孩子的索引是 (2*i+1);

(02) 索引为i的左孩子的索引是 (2*i+2);

(03) 索引为i的父结点的索引是 floor((i-1)/2);

堆节点的访问

堆的操作

在堆的数据结构中，堆中的最大值总是位于根节点（在优先队列中使用堆的话堆中的最小值位于根节点）。

堆中定义以下几种操作：

最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点

创建最大堆（Build Max Heap）：将堆中的所有数据重新排序

堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算

堆排序算法图解

这个图解来自 图解排序算法(三)之堆排序，画的非常漂亮。

基本思想

将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。

将其与末尾元素进行交换，此时末尾就为最大值。

然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。

步骤

步骤一 构造初始堆

将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。

a. 假设给定无序序列结构如下

输入图片说明

b. 此时我们从最后一个非叶子结点开始（叶子结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。

输入图片说明

c. 找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换。

输入图片说明

d. 这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。

输入图片说明

此时，我们就将一个无序的序列构造成了一个大顶堆。

步骤二 调整堆

将堆顶元素与末尾元素进行交换，使末尾元素最大。

然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。

a. 将堆顶元素9和末尾元素4进行交换

输入图片说明

b. 重新调整结构，使其继续满足堆定义

输入图片说明

c. 再将堆顶元素8与末尾元素5进行交换，得到第二大元素8.

输入图片说明

后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序

输入图片说明

简单总结

再简单总结下堆排序的基本思路：

a. 将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;

b. 将堆顶元素与末尾元素交换，将最大元素”沉”到数组末端;

c. 重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

java 实现

说明

为了和前面的逻辑保持一致，我们暂时依然使用 list 去实现这个堆排序。

实现

插入排序

插入排序（英语：Insertion Sort）是一种简单直观的排序算法。

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

插入排序在实现上，通常采用in-place排序（即只需用到 O(1) 的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

算法步骤

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

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

排序

java 实现

java 实现

希尔排序（Shellsort）

也称递减增量排序算法，是插入排序的一种更高效的改进版本。

希尔排序是非稳定排序算法。

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

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

算法实现

希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。

这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。

假设有一个很小的数据在一个已按升序排好序的数组的末端。如果用复杂度为O(n^2)的排序（冒泡排序或插入排序），可能会进行n次的比较和交换才能将该数据移至正确位置。

而希尔排序会用较大的步长移动数据，所以小数据只需进行少数比较和交换即可到正确位置。

一个更好理解的希尔排序实现：将数组列在一个表中并对列排序（用插入排序）。重复这过程，不过每次用更长的列来进行。最后整个表就只有一列了。

将数组转换至表是为了更好地理解这算法，算法本身仅仅对原数组进行排序（通过增加索引的步长，例如是用i += step_size而不是i++）。

例子

例如，假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我们以步长为5开始进行排序，我们可以通过将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样：

然后我们对每列进行排序：

将上述四行数字，依序接在一起时我们得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]。

这时10已经移至正确位置了，然后再以3为步长进行排序：

排序之后变为：

最后以1步长进行排序（此时就是简单的插入排序了）。

步长序列如何选择？

Donald Shell 最初建议步长选择为 n/2 并且对步长取半直到步长达到1。

虽然这样取可以比 O(n^2) 类的算法（插入排序）更好，但这样仍然有减少平均时间和最差时间的余地。

已知的最好步长序列是由 Sedgewick 提出的(1, 5, 19, 41, 109,…)，

另一个在大数组中表现优异的步长序列是（斐波那契数列除去0和1将剩余的数以黄金分割比的两倍的幂进行运算得到的数列）：

(1, 9, 34, 182, 836, 4025, 19001, 90358, 428481, 2034035, 9651787, 45806244, 217378076, 1031612713,…)

java 代码实现

实现

这里为了简单，我们步长直接选择列表长度的一半，并且依次折半。

整体实现也不难，大家可以回顾下 插入排序

这里为了便于大家理解，我们特意添加了日志。

归并排序（英语：Merge sort，或mergesort）

是创建在归并操作上的一种有效的排序算法，效率为 O(nlogn)（大O符号）。1945年由约翰·冯·诺伊曼首次提出。

该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。

概述

采用分治法:

分割：递归地把当前序列平均分割成两半。

集成：在保持元素顺序的同时将上一步得到的子序列集成到一起（归并）。

java 实现递归法

递归法（Top-down）

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列设定两个指针，最初位置分别为两个已经排序序列的起始位置比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置重复步骤3直到某一指针到达序列尾将另一序列剩下的所有元素直接***到合并序列尾

java 实现

实际上代码实现也不难，不过递归多多少少让人看起来不太习惯。

我们后面会结合测试日志，再进行讲解。

java 迭代实现

相信很多小伙伴都知道迭代可以使得代码变得简洁，但是会让调试和理解变得复杂。

我们来一起学习一下迭代的实现方式。

迭代法（Bottom-up）

原理如下（假设序列共有 n 个元素）：

将序列每相邻两个数字进行归并操作，形成 ceil(n/2) 个序列，排序后每个序列包含两/一个元素若此时序列数不是1个则将上述序列再次归并，形成 ceil(n/4) 个序列，每个序列包含四/三个元素重复步骤2，直到所有元素排序完毕，即序列数为1

迭代实现

相对递归，这个代码就要显得复杂很多。

不过这种迭代的方式性能更好，实现如下。

counting sort 计数排序

计数排序（Counting sort）是一种稳定的线性时间排序算法。

该算法于1954年由 Harold H. Seward 提出。

通过计数将时间复杂度降到了 O(N)。

基础版

算法步骤

找出原数组中元素值最大的，记为***x。创建一个新数组count，其长度是***x加1，其元素默认值都为0。遍历原数组中的元素，以

原数组中的元素作为count数组的索引，以原数组中的元素出现次数作为count数组的元素值

。创建结果数组result，起始索引index。遍历count数组，找出其中元素值大于0的元素，将其对应的索引作为元素值填充到result数组中去，每处理一次，count中的该元素值减1，直到该元素值不大于0，依次处理count中剩下的元素。返回结果数组 result。

java 实现

改良版

空间浪费

实际上我们创建一个比最大元素还要大1的数组，只是为了放下所有的元素而已。

但是它有一个缺陷，那就是存在空间浪费的问题。

比如一组数据{101,109,102,110}，其中最大值为110，按照基础版的思路，我们需要创建一个长度为111的计数数组，但是我们可以发现，它前面的[0,100]的空间完全浪费了，那怎样优化呢？

将数组长度定为 ***x-min+1，即不仅要找出最大值，还要找出最小值，根据两者的差来确定计数数组的长度。

改良版本实现

自己的思考

算法的本质

这个算法的本质是什么呢？

个人理解只需要保证两点：

（1）每一个元素，都有自己的一个元素位置

（2）相同的元素，次数会增加。

算法的巧妙之处在于直接利用数值本身所谓索引，直接跳过了排序比较；利用技数，解决了重复数值的问题。

算法的不足

这个算法的巧妙之处，同时也是对应的限制：那就是只能直接比较数字。如果是字符串呢？

一点想法

我最初的想法就是可以使用类似于 HashMap 的数据结构。这样可以解决元素过滤，次数统计的问题。

但是无法解决排序问题。

当然了，如果使用 TreeMap 就太赖皮了，因为本身就是利用了树进行排序。

TreeMap 版本

我们这里使用 TreeMap 主要有下面的目的：

（1）让排序不局限于数字。

（2）大幅度降低内存的浪费，不多一个元素，也不少一个元素。

思想实际上依然是技术排序的思想。

桶排序（Bucket sort）

或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶里。

每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。

桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间 O(n)。

桶排序是计数排序的扩展版本，计数排序可以看成每个桶只存储相同元素，而桶排序每个桶存储一定范围的元素，通过映射函数，将待排序数组中的元素映射到各个对应的桶中，对每个桶中的元素进行排序，最后将非空桶中的元素逐个放入原序列中。

桶排序需要尽量保证元素分散均匀，否则当所有数据集中在同一个桶中时，桶排序失效。

算法流程

桶排序以下列程序进行：

设置一个定量的数组当作空桶子。寻访序列，并且把项目一个一个放到对应的桶子去。对每个不是空的桶子进行排序。从不是空的桶子里把项目再放回原来的序列中。

算法

java 实现

实现