[数据结构与算法]Java实现七大排序算法

基本概念

1.排序

排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
平时的上下文中，如果提到排序，通常指的是排升序（非降序）。
通常意义上的排序，都是指的原地排序而且这里的七种排序全是基于比较的排序

2.稳定性

如何判单一个排序算法是否稳定？

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

一个排序是否发生跳跃式的交换也是判断是否稳定的一个技巧。

• 一个稳定的排序算法可以变成一个不稳定的排序算法
• 一个本身就不稳定的排序算法是不可以变成一个稳定的排序算法的
  

一、直接插入排序

1.原理

整个排序区间被分为

1. 有序区间
2. 无序区间

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

直接插入排序的基本操作就是从下标1开始记录，插入到前面已经排好的有序区间里生成一个新的有序区间，直到记录完数组的最后一个元素。
其实这就类似与我们斗地主，摸一张牌就插入到对应的位置。

2.排序过程

定义两个变量 i 和 j ,i从1开始，j = i-1.再定义一个tmp存放i下标的元素。
j从 i-1 往回走，当 j 位置的元素大于tmp就把它往后移一个位置，如果 j 位置的元素小于 tmp 就把tmp的元素给 j+1位置同时结束循环。
然后i往后走同时tmp记录i下标的元素，j 再等于 i-1。直到 i 大于数组长度。

第一轮：从第二位置的 6 开始比较，比前面 7 小，交换位置。

第二轮：第三位置的 9 比前一位置的 7 大，无需交换位置。

第三轮：第四位置的 3 比前一位置的 9 小交换位置，依次往前比较。

第四轮：第五位置的 1 比前一位置的 9 小，交换位置，再依次往前比较。

…
就这样，直到最后一个元素比较完。

3.代码实现

4.性能分析

时间复杂度

最好情况：O(n) （当数据已经是有序的时候)

最坏情况：O(n²)（当数据是逆序的时候)

空间复杂度

没有使用额外的空间： O(1)

稳定性：稳定的排序

直接插入排序，初始数据越接近有序，时间效率越高。

开头说过判断稳定性就是一组数据里有相同的元素，如果排序前和排序后，这两个相同的元素的前后关系没有发生变化那么这个排序就是稳定的。

来看下面这组数据经过直接插入排序后红色的6还是在黑色的6前面，所以这个排序是稳定的。

前面我们也说到过一个稳定的排序可以变成一个不稳定的排序，这里只需要在判断 j 下标的元素和标记位置的元素比较大小的地方取 >= 就能变成一个不稳定的排序。因为这样相同的元素也会发生交换。

二、希尔排序

我们知道到直接插入排序的时间复杂度是O(n²)，那么当排序数据非常大的时候，就比较慢了。
假设而我们要排1万个无序的数据，那么他的时间复杂度就是 10000²= 1亿，如果采用一种分组的的思想，把1万个数据分为100组每组100个，每组分别采用直接插入排序，那它的时间复杂度就会大大降低。

1.原理

希尔排序又称缩小增量排序，因 DL.Shell 于 1959 年提出而得名。
希尔排序(Shell Sort)是插入排序的一种，它是针对直接插入排序算法的改进。。

希尔排序法的基本思想是：先选定一个整数gap，把待排序元素中所有记录分成个组，所有距离为gap的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到gap=1时，所有记录在统一组内排好序

2.直接插入排序过程

1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果

假设我们要排序一组元素

1.将初始增量定位 gap = 5，相同的颜色为一组。分别进行直接插入排序

2.第二次我们把 gap = 3，再进行分组排序，排序完成后。发现较大的数字已经跑到了后面，这就已经慢慢趋近与有序了，这不是直接插入排序最喜欢的吗？

3.最后再把 gap = 1进行直接插入排序，数据就变成有序的了

3.关于 gap 的取值

清华大学出版社的数据结构书上说到：
希尔排序的分析是一个复杂的问题，因为他的时间是所取“增量”序列的函数，这涉及一些数学上尚未解决的难题，所以，到现在为止还没有人取得一种最好的增量序列，所以增量序列可以有各种取法，但必须要保证 gap 最后要等于1，因为希尔排序本来就是直接插入排序的一种优化.才能保证有序。

4.代码实现

5.性能分析

时间复杂度
希尔排序的时间复杂度刚刚说了，不太好算。

它的时间复杂度是：O(n^1.3~1.5)

空间复杂度

没有使用任何额外空间： O(1)

稳定性： 希尔排序发生了跳跃式的交换，那么肯定不是稳定的排序。

三、选择排序

1.原理

每一次从无序区间选出最大（或最小）的一个元素，存放在无序区间的最后（或最前），直到全部待排序的数据元素排完。这是一个非常简单的排序。

2.排序过程

3.代码实现

4.性能分析

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n2) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

时间复杂度

最好最坏都是：O(n²)

空间复杂度

没有任何额外空间 O(1)

**稳定性：**很明显这里也发生了跳跃式的交换，那么它肯定不是一个稳定的排序

四、堆排序

堆逻辑上是一棵完全二叉树
要想了解堆排序，就得先知道什么是堆。可以看看这篇博客.
——> 优先级队列 (堆PriorityQueue)

1.原理

基本原理也是选择排序，只是不在使用遍历的方式查找无序区间的最大的数，而是通过堆来选择无序区间的最大的数。

注意：从小到大排序是建大堆，从大到小排序是建小堆。

2.排序过程

要想进行堆排序，前提是这个堆一定是大(小)堆。

(1) 建大堆（向下调整）

我先来看一下建大堆过程：采用向下调整的方式，从最后一棵子树开始，保证左右孩子要小于父亲。遍历完所以子树，最后整个堆都变成一个大根堆。

建大堆代码：
如果想建小堆，只需要把 改一下大于小于号即可。

public static void adjustDown(int[] array,int root,int len) {
        int parent  = root;
        int child  = parent*2+1;
        while (child < len) {
            //找出左右孩子的最大值
            if(child+1 < len && array[child] < array[child+1]) {
                child++;
            }
            //拿左右孩子的最大值和父亲比较
            if(array[parent] < array[child]) {
                int tmp = array[parent];
                array[parent] = array[child];
                array[child] = tmp;
                parent = child;
                child = parent*2+1;
            }else{
                break;
            }
        }
    }
    //建大堆
    public static void creatMaxHeap(int[] array) {
        int parent = (array.length-1-1)/2;
        for (int i = parent; i >= 0; i--) {
            adjustDown(array,i,array.length);
        }
    }

(2) 堆排序过程

1.首先保证一个堆是一个大堆后，就可以进行堆排序了。把0下标的元素和数组最后一个元素交换，再把除去交换过的元素外，堆整体调整为大根堆

2.每进行一次交换，下次进行调整的元素就少了减少一个，因为大根堆的堆顶元素一定是这组元素中最大的。紫色代表已经有序不需要参加调整了。

3.代码实现

4.性能分析

时间复杂度

最好最坏都是 O(n*log${}_2$n)

空间复杂度

无任何额外空间所以是：O(1)

稳定性

同样这里发生了跳跃式的交换，所以是不稳定排序

五、冒泡排序

1.原理

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

这里的写的是优化过的冒泡排序，就是立了一个flg来判断是否已经有序。

2.排序过程

第一趟冒泡排序

第二趟冒泡排序过后数据已经有序了，再走完第三趟排序后发现没有任何元素进行交换，直接结束了整个排序。

3.代码实现

4.性能分析

时间复杂度

最好最坏都是O(n²) 但是：如果优化了 ，有序的时候就是O(n)

空间复杂度

没有使用任何额外空间：O(1)

稳定性

很明显这是一个稳定的排序，没有发生跳跃式交换且交换的都是相邻的元素

六、快速排序

1.原理

1.从数列中挑出一个元素，称为 “基准”（pivot）

2.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作

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

3.递归把小于基准值元素的子数列和大于基准值元素的子数列排序

(1) 挖坑法

挖坑法是一种找基准的方法，如上图所示。
定义一个 left 和 right 分别代表左边和右边的下标，key来存储基准的数字
挖坑法的思路：

1.先在 left 下标挖一个坑把里面的元素存到 key 里

2.从 right 位置从后往前找比 key 小的数字把刚刚挖的坑填上

3.从left位置从前往后找比 key 大的元素，填上 right 挖的坑

4.直到 left 和 right 相遇就把 key 的值放到它们相遇的位置

5.这样key里面的元素就是一个基准了，它的左边是比它小的值，右边是比它大的值

分别递归执行基准的左边和右边，直到有序。

(2) Hoare法

Hoare法也是一种找基准的方式，其实还有其它的找基准方式，比如随机找基准法。

Hoare法和挖坑法其实类似

1.同样是把左边的元素存到key里

2.先让 right 从后往后找比 key 小的元素

3.再让 left 从前往后找比 key 大的元素

4.接着交换 right 和 left 位置的元素

5.直到 right 和 left 相遇后，把 key 和它们相遇位置的元素交换

递归执行，直到数据有序。
注意：一定是right先从后往前找比 key 大的元素

2.排序过程

这里演示的挖坑法的排序过程

3.代码实现

这里默认调用的是挖坑法

4.快速排序的优化

上面的代码如果数据过大则会出现栈被挤爆的情况，那么就需要优化一下代码。那么怎么优化呢？快速排序的关键点无非就是找基准值，那么就从基准值入手。
常见的取基准值的方法有：
1.固定位置选择
也就是我们刚刚写的挖坑法和Hoare里面的选择最左或者最右的元素作为基准值。
2.随机选取法
这是一个随缘优化，它的基本思路是从 left 和 right之间随机选取一个元素和 left 进行交换作为基准值，这不是就是在碰运气吗？但这个方法的确能起到作用。比如在待排序区间部分数据是有序的时候。
代码也很简单。

int pivot =  random.nextInt(right-left+1)+left;

3.三数取中法+直接插入
我们在划分区间的时候最希望的是什么，当然是能把区间分成等长的，也就是基准值取的刚好是这组数据的中位数，可是，这很难算出来并且会让算法更加慢。

那么到底怎么进行三数取中呢？

思路：其实很简单，只需把取间中，left 、right 和中间元素 mid，求出它们的中位数，再和 left 交换。

保证：mid <= left <= right

我们假设要排一组有序数列，如果基准取的它们的中位数。肯定是要比取最边上的效率高的。

1，2，3，4，5

我们知道在不断找基准的同时，数据也慢慢趋近于有序。而直接插入排序对于趋近有序的数据排序是非常快的。

当待排序区间小于一个阈值的时候使用直接插入排序，我们这里给50，当然这个值也不是死的，给40或者80都行。

优化后的代码：

5.非递归实现

思路：用一个栈存放 left 和 right 的下标

1.调用挖坑法找基准值

2.把当前基准值 pivot 的左边区间和右边区间的下标放到栈里面
注意：当区间至少有两个元素以上时才入栈

3.判断栈是否为空，不为空，弹出两个元素，left 和 right
注意：入栈和弹出的元素要对应，是 left 还是 right

代码实现

6.性能分析

时间复杂度

最好：O(n*log${}_2$n) 待排序区间均匀的分割下

最坏：待排序区间不均匀分割，或者是当数据是逆序的情况下情况数据是逆序 O(n²)

空间复杂度

最好：O(log${}_2$n)

最坏：O(n)

七、归并排序

1.原理

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

2.排序过程

归并排序是递归算法的一个实例，这个算法中基本的操作是合并两个已排序的数组，取两个输入数组 A 和 B，一个输出数组 C，以及三个计数器 i、j、k，它们初始位置置于对应数组的开始端。
A[i] 和 B[j] 中较小者拷贝到 C 中的下一个位置，相关计数器向前推进一步。
当两个输入数组有一个用完时候，则将另外一个数组中剩余部分拷贝到 C 中。

自顶向下的归并排序，递归分组图示：

对第三行两个一组的数据进行归并排序

对第二行四个一组的数据进行归并排序

整体进行归并排序

3.代码实现

4.非递归实现

思路：假设我们要排序8个数据

我们先把它们看作是一个一个有序，再看作两个两两个有序，再到四个四个有序，最后整体有序。
定义4个变量分别代表待排序的左边区间和右边区间。
要考虑数组越界，也就是只有一个区间的情况

5.性能分析

时间复杂度

每次都是对半进行拆分，最好最坏都是：O(N*log n)

空间复杂度

每次拆分都用了额外的数组所以是：O(n)

稳定性

没有发生跳跃式的交换，比较的是相邻的元素，所以是稳定的

八、汇总

这是7个基于比较的排序，也属于内部排序，也就是在内存中进行排序。

九、海量数据的排序问题

外部排序：排序过程需要在磁盘等外部存储进行的排序
前提：内存只有 1G，需要排序的数据有 100G
因为内存中因为无法把所有数据全部放下，所以需要外部排序，而归并排序是最常用的外部排序

1. 先把文件切分成 200 份，每个 512 M
2. 分别对 512 M 排序，因为内存已经可以放的下，所以任意排序方式都可以
3. 进行 200 路归并，同时对 200 份有序文件做归并过程，最终结果就有序了

完！
这么好的文章不收藏？