本文内容介绍大纲

排序介绍

  排序࿰c;就是使一串记录࿰c;按照其中的某个或某些关键字的大小࿰c;递增或递减的排列起来的操作。

  平时的上下文中࿰c;如果提到排序࿰c;通常指的是排升序（非降序）。

  通常意义上的排序࿰c;都是指的原地排序(in place sort)

稳定性

  两个相等的数据࿰c;如果经过排序后࿰c;排序算法能保证其相对位置不发生变化࿰c;则我们称该算法是具备稳定性的排序算法。

一、直接插入排序

算法演示：

@H_696_163@1.原理

整个区间被分为

1.有序区间

2.无序区间

  每次选择无序区间的第一个元素࿰c;在有序区间内选择合适的位置插入

@H_696_163@2.基本思想

  直接插入排序是一种简单的插入排序法࿰c;其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中࿰c;直到所有的记录插入完为止࿰c;得到一个新的有序序列 。

实际中我们玩扑克牌时࿰c;就用了插入排序的思想

我们来说一下 直接插入排序的具体步骤：

1.定义一个 变量 i ࿰c;i 从这个数组中的第二个元素开始遍历

2.定义 一个变量 j ࿰c; j = i - 1 .如果 arr[ i ] 比 arr [ j] 小的话࿰c;每次都把 arr [ j+1 ] = arr [ j ]࿰c;相当于把 i 之前 比 arr [ i ] 大的数字全都向后移动一位࿰c;直到遇到 arr [ j ] < arr [ i ],此时 arr [j+1] = arr [ i ].

3.如果j向前遍历࿰c;直到 j<0 时 也没有满足 arr[ i ] < arr [ j], j 向前的遍历结束 ࿰c; arr [ j+1 ] = arr [ i ].

4.最后完成遍历࿰c;排序完成.

@H_696_163@3.代码展示

稳定性判断：

  根据上面的思路我们进行遍历࿰c;发现4 4 的位置并没有进行交换 ࿰c;所以 直接插入排序是稳定的.

还有一种判断稳定性的方法：

  在排序时࿰c;如果元素 没有发生跳跃式 变换࿰c;只是相邻元素交换的话࿰c;这个排序就是稳定的.

  还有通过这个代码我们发现࿰c;这个排序也可以变成不稳定的࿰c;

  在这样的情况下࿰c;相同的元素 在比较时就会发生交换࿰c;排序变成不稳定的了.

我们可以得到一个结论：

一个稳定的排序࿰c;可以实现为不稳定的排序

但是一个本身就不稳定的排序࿰c;就不可能实现为稳定的排序

@H_696_163@4.性能分析

时间复杂度

最好情况下：

  我们给定一个有序的数组进行直接插入排序࿰c;这就是最好情况࿰c;此时 时间复杂度为 O (N )

最坏情况下：

  我们给定一个完全无序的数组进行直接插入排序࿰c;这就是最坏情况࿰c;此时时间复杂度为 O（N^2）.

我们同样得到一个结论：

当一组数据࿰c;数据量不大且 趋近于有序࿰c;此时用插入排序时间更快 . 越有序越快！！

空间复杂度

这个排序算法 没用用到其他的辅助空间࿰c;所以 空间复杂度 为 O (1).

稳定性

这个排序由于没有发生跳跃式 变换࿰c;所以是 稳定的

二、希尔排序

算法演示：

希尔排序法又称缩小增量法。

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

1.插入排序在对几乎已经排好序的数据操作时࿰c;效率高࿰c;即可以达到线性排序的效率。

2.但插入排序一般来说是低效的࿰c;因为插入排序每次只能将数据移动一位。

@H_696_163@1.基本思想

1. 先选定一个小于N的整数gap作为第一增量࿰c;然后将所有距离为gap的元素分在同一组࿰c;并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量࿰c;重复上述操作…

2.当增量的大小减到1时࿰c;就相当于整个序列被分到一组࿰c;进行一次直接插入排序࿰c;排序完成。

为什么要让gap由大到小呢？

 gap越大࿰c;数据移动得越快；gap越小࿰c;数据移动得越慢。开始让gap较大࿰c;可以让数据更快得移动到自己对应的位置附近࿰c;减少移动次数.

@H_696_163@*注意点

1.希尔排序是对直接插入排序的优化。

2. 当gap > 1时都是预排序࿰c;目的是让数组更接近于有序。当gap == 1时࿰c;数组已经接近有序的了࿰c;这样就会很快。这样整体而言࿰c;可以达到优化的效果。我们实现后可以进行性能测试的对比。

我们来将整个排序的 思路走一遍：

下面是 我们要进行排序的数组

  将数组中的元素进行分组࿰c;每组中的元素 gap 间隔为3࿰c; 我用不同颜色进行分组.

gap ==3 ࿰c;分组完之后࿰c;我们将每一组中的数据进行排序

  将数组中的元素进行分组࿰c;每组中的元素 gap 间隔为2࿰c; 我用不同颜色进行分组.

gap == 2 ࿰c;分组完之后࿰c;我们将每一组中的数据进行排序

  将数组中的元素进行分组࿰c;每组中的元素 gap 间隔为1࿰c; 此时对整体进行排序.

整体排完序后࿰c;希尔排序完成.

每一组排序我们都用的是 直接插入排序.

@H_696_163@2.代码展示

@H_696_163@3.增量 gap 的选取

选自 《数据结构》清华大学出版

gap 的值 没有除 1 以外 的公因子࿰c;并且最后一个增量值 必须为 1 .

我们只能尽量 追求gap 没有公因子࿰c; 最后 要 +1.

我们可以这样取 gap ࿰c;使 gap 最后为 1.

   gap = arr@H_450_425@.length@H_450_425@;
   while@H_450_425@(gap>1@H_450_425@)@H_450_425@{
       gap = gap/3+1@H_450_425@;  //  加 1  保证最后一个序列为1 ࿰c;除几都行
   @H_450_425@}

@H_696_163@4.性能分析

时间复杂度

最坏、最好情况下

  由于 gap 每次取值都不同࿰c;所以算起来十分复杂࿰c;但是我们仍然能够得到一些数据…

所以我们就这样认为

最好情况下时间复杂度 O（n^ 1.3）

最坏情况下时间复杂度 O（n^ 1.5）

空间复杂度

没有借助其他的辅助空间࿰c;所以空间复杂度 为 O（1）

稳定性

在这个排序中 发生了跳跃式的交换࿰c;所以这个排序不是稳定的.

三、选择排序

算法演示：

@H_696_163@1.基本思想

 数组从头开始遍历 ࿰c; i= 0开始࿰c;i 后面的每一个元素 arr [ j ] 都与 arr[i] 进行比较࿰c;如果 arr [ i ]> arr [ j ] ,那么就进行交换.

我们根据思路来 走一下排序的过程.

我们要对 这个数据进行排序

开始进行排序

@H_696_163@2.代码展示

@H_696_163@3.性能分析

时间复杂度

最坏情况下： O（n^2）

最好情况下： O（n^2）

空间复杂度

没有借助辅助空间࿰c;所以空间复杂度为 O ( 1 )

稳定性

因为在排序的过程中发生了跳跃式交换࿰c;所以这种排序不是稳定的.

四、堆排序

算法演示：

@H_696_163@1.基本思想

从小到大排序 —— 升序 建立大堆

从大到小排序 —— 降序 建立小堆

思路： 以升序 为 例

0.先将数组 调整为一个 大堆 ࿰c;建立一个大堆

1. 交换 数组 首尾 的元素࿰c;这样最大的堆顶元素 被放在数组的最后一个࿰c;此时 最后一个元素 已经定好序了.

2. 此时从第一个到 倒数第二个再次调整࿰c;调整完后将堆顶元素 与倒数第二个元素交换࿰c;按照这样的逻辑规律࿰c;循环直到 有序.

我们以实际 例子说明…

下面以数组 [5, 7, 9 , 3, 1, 8࿰c;6,2] 为例进行从小到大排序的演示：

0.调整为大堆

1.首尾交换

2.向下调整

重复此操作直到全部有序

最后我们排完序了

如何将一个数组转换成一个堆呢？

@H_696_163@2.建堆操作

  下面我们给出一个数组࿰c;这个数组逻辑上可以看做一颗完全二叉树࿰c;但是还不是一个堆࿰c;现在我们通过算法࿰c;把它构建成一个堆。

  根节点左右子树不是堆࿰c;我们怎么调整呢？这里我们从倒数的第一个非叶子节点的子树开始调整࿰c;一直调整到根节点的树࿰c;就可以调整成堆。

将一个二叉树 调整为一个 大根堆

这棵二叉树调整为 大根堆 必须将 每颗子树都调整为大根堆.

@H_696_163@3.向下调整

思想 步骤：

parent —> 根节点下标

child —> 孩子节点下标

1.从最后一棵子树进行调整.

2. 每颗子树从根节点向下调整࿰c;如果左右孩子节点的最大值比这个根节点大࿰c;那么值互换࿰c;然后 parent 指向 child ,child = 2* parent + 1࿰c; 继续向下调整࿰c;直到 下标child 超出二叉树 范围.

3.重复第二步的操作࿰c;遍历每一颗子树࿰c;直到所有子树全部遍历完成.

代码实现：

这就是 向下调整的完整过程.

我们来看整体堆排序的代码展示：

@H_696_163@4.代码展示

@H_696_163@5.性能分析

时间复杂度

最好最坏情况下࿰c;都是 O（n* logn）

空间复杂度

没有借助外部空间࿰c;空间复杂度为O（1）

稳定性

发生了跳跃式的交换࿰c;所以是不稳定的.

五、冒泡排序

算法演示：

@H_696_163@1.基本思想

两两相邻元素进行比较࿰c;数值大的元素排到后面。

比较相邻的元素。如果第一个比第二个大࿰c;就交换他们两个。

对每一对相邻元素作同样的工作࿰c;从开始第一对到结尾的最后一对。

针对所有的元素重复以上的步骤࿰c;除了最后一个。   我们也可以找到规律：

这个数组一共有 10个数字

第 1 个数字比较了 9次࿰c; 第 2 个数字比较了 8 次…

第 i 个数字 比较 10 - i 次

  持续每次对越来越少的元素重复上面的步骤࿰c;直到没有任何一对数字需要比较。

我们来 走一遍 冒泡排序的思路：

  之后对每一个数字都从头开始比较相邻元素…直到全部排序完成.

@H_696_163@2.代码展示

@H_696_163@3.性能分析

时间复杂度

最好、最坏情况下都是 O（n^2）,在优化下࿰c;最好情况是O（n）.

空间复杂度

没有借助辅助空间࿰c;所以空间复杂度为O（1）

稳定性

都是相邻元素之间进行排序࿰c;所以这个排序是稳定的.

六、快速排序

1.原理

1.从待排序区间选择一个数࿰c;作为基准值(pivot)；通常为最左边的数字.

2.Partition: 遍历整个待排序区间࿰c;将比基准值小的（可以包含相等的）放到基准值的左边࿰c;将比基准值大的（可以包含相等的）放到基准值的右边；

3. 采用分治思想࿰c;对左右两个小区间按照同样的方式处理࿰c;直到小区间的长度 == 1࿰c;代表已经有序࿰c;或者小区间的长度 == 0࿰c;代表没有数据。

@H_696_163@1. Hoare 法

  左边第一个数字下标定义为 start 右边第一个数字下标定义为 end࿰c;key 为第一个数字

 end 先向前走࿰c;找到 比 key 小的位置࿰c;end 找到小于 key 的位置࿰c;保持不动࿰c;

start 在向后走࿰c;找到比 key 大的位置

找到之后࿰c;交换 start 和 end 的位置࿰c;key 的位置一直保持不动

重复此过程…

直到 start 和 end 相遇࿰c; 将该位置的值 与 key 交换.

@H_696_163@2.挖坑法

左边第一个数字下标定义为 start 右边第一个数字下标定义为 end

先将第一个数据放到 临时变量 tmp 中࿰c;形成一个坑位

 end 开始向前走࿰c;找到比 tmp 小的位置࿰c;找到后 ࿰c;将该值放入坑位中࿰c;该位置形成新的坑位

 start 开始向后移动࿰c;找到比 tmp 大的位置࿰c;找到后࿰c;将该值放入坑位中࿰c;再形成新的坑位

重复上面的两个过程…

最后 start 和 end 相互遇见࿰c;将 tmp 的值 放入最后一个 相遇的坑位.

我们来走一遍 挖坑法 的具体思路：

2.代码展示

@H_696_163@1.递归思路

@H_696_163@2.基准值的选择

1. 选择边上（左或者右）
2. 随机选择
3. 几数取中（例如三数取中）：arraY[left], arraY[R_340_11845@id], arraY[right] 大小是中间的为基准值

快速排序的优化

1.选择基准值很重要࿰c;通常使用几数取中法

  我们如果选取的 在基准的数值正好是 这组数据的中位数࿰c;每次都是平均 分࿰c;那么此时 时间复杂度最小࿰c;但是实际情况中通常没有那么巧合࿰c;所以我们为了追求尽可能小的 时间复杂度࿰c;取 这组数据 头 、尾 、 中间三个数字中的中间值作为 基准.

我们在实现 paitition 函数时࿰c;要满足这个条件：

arr [ mid] <= arr [ start ] <= arr [ end ]

2.partition 过程中把和基准值相等的数也选择出来

3.待排序区间小于一个阈值时（例如 48）࿰c;使用直接插入排序

  随着递归的进行,数据的区间在缩小,区间的数据也在慢慢趋近于有序…

@H_696_163@3.非递归思路

1.调用 partition 之后࿰c;找到了 pivot

2.把当前 pivot 的左边区间 和右边区间 的下标放入栈中

3.判断栈是否为 空࿰c;不为空࿰c;弹出栈顶2个元素࿰c;注意： 放的顺序 决定了 取出的顺序中第一个元素是给的 high 还是 low.

4.再进行 partion

什么时候 入栈?

当这个区间 最起码有 2个元素的时候

代码展示：

3.性能分析

时间复杂度

最好的情况下࿰c;选完基准之后都均分࿰c;此时时间复杂度为O（n*logn） 最坏的情况下࿰c; 数组为一个有序的数组࿰c;我们要逆序࿰c;此时时间复杂度为 O（n^2）.

空间复杂度

最好情况下是每次都二分࿰c;所以空间复杂度为O（logn）,最坏情况下为 O（n）,所以 空间复杂度为 O（logn）~ O（n）.

稳定性

排序时发生了跳跃式交换࿰c;所以是不稳定的

七、归并排序

归并算法演示

@H_696_163@1.原理总览

 归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并࿰c;得到完全有序的序列；即先使每个子序列有序࿰c;再使子序列段间有序。若将两个有序表合并成一个有序表࿰c;称为二路归并。

根据思路我们来将 归并排序走一遍：

1.整组元素对半拆分࿰c;拆分之后再次进行拆分࿰c;直到拆分成单个的元素.

2.按其拆分的方式࿰c;对其对应的两个元素进行排序并合并成一组.

3.对合并过的组࿰c;每两组再次进行合并

在这个思路中 最重要的 就只有两步：

1.分解࿰c;我们可以折半分解࿰c;直到 每个元素都分开

2.合并 ࿰c;将各个元素有序合并.

@H_696_163@2.合并两个有序数组

我们可以根据 start、mid、end 得到两个数组的区间

[ start , mid ] ---- [ mid+1 , end ]

构建一个 辅助的数组空间.

我们在排序时࿰c;有以下几种情况

 两个数组都未遍历完࿰c; s1<= e1 && s2<=e2 , 两个同时遍历࿰c;谁小往辅助数组放元素.放完之后 ࿰c;辅助元素的下标 ++ ࿰c;放到数组元素也 ++.

有一个数组遍历完了࿰c;直接在 已经排好序的数组之后接上 未遍历完的.

合并数组的代码展示：

@H_696_163@3.代码展示

归并排序的完整代码展示：

@H_874_1101@

@H_696_163@4.性能分析

时间复杂度

因为要进行二分拆解࿰c;所以最好、最坏情况下都是 O（n* logn）

空间复杂度

由于在合并有序数组是借助了 辅助空间࿰c;所以 空间复杂度为 O（n）.

稳定性

每次排序都是相邻的元素之间比较࿰c;所以是稳定的.

八、内部排序

  我们学习了这几种基于比较的排序算法࿰c;下面我们来进行总结一下.

  我们学的排序都是内部排序࿰c;什么是内部排序呢？ 就是把数据放在内存中 进行排序 .

内排序：数据量相对少一些࿰c;可以放到内存中进行排序。

外排序：数据量较大࿰c;内存中放不下࿰c;数据只能放到磁盘文件中࿰c;需要排序。

上面介绍的排序算法均是在内存中进行的࿰c;对于数据量庞大的序列࿰c;上面介绍的排序算法都束手无策࿰c;而归并排序却能胜任这种海量数据的排序。

九、海量数据的排序问题

外部排序：排序过程需要在磁盘等外部存储进行的排序

前提：内存只有 1G࿰c;需要排序的数据有 100G

   因为内存中因为无法把所有数据全部放下࿰c;所以需要外部排序࿰c;而归并排序是最常用的外部排序

1.先把文件切分成 200 份࿰c;每个 512 M

2.分别对 512 M 排序࿰c;因为内存已经可以放的下࿰c;所以任意排序方式都可以

3.进行 200 路归并࿰c;同时对 200 份有序文件做归并过程࿰c;最终结果就有序了

  好了今天的知识就分享到这里࿰c;希望大家多多练习࿰c;熟练掌握࿰c;感谢大家的欣赏与关注！！

谢谢欣赏！！

未完待续…