排序算法及优化详解

目录

• 1. 开场白
• 2. 排序的基本概念与分类
• • 2.1 排序稳定性
  • 2.2 内排序与外排序
  • 2.3 分类
• 3.排序算法实现
• • 3.1. 冒泡排序
  • 3.2.选择排序
  • 3.3. 插入排序
  • 3.4. 希尔排序
  • • 3.4.1 希尔排序原理
    • 3.4.2 希尔排序算法实现
    • 3.4.3 希尔排序复杂度分析
  • 3.5. 堆排序
  • • 3.5.1 堆排序原理
    • 3.5.2 堆排序算法实现
    • 3.5.2 堆排序复杂度分析
  • 3.6. 归并排序
  • • 3.5.1 递归实现归并排序
    • 3.5. 非递归实现归并排序
    • 3.5. 归并排序复杂度分析
  • 3.7. 快速排序
  • • 3.7.1 快速排序算法基本思想
    • 3.7.2 快速排序递归算法实现及优化步骤
    • 3.7.4 快速排序非递归实现

1. 开场白

假如我想买一台IPhone13ProMax的手机, 于是去搜索百度.

搜到了很多相关物品, 我想花钱便宜一点购买但又怕遇到骗子该怎么办呢?
这时候就使用到了排序, 我们可以按照信用排序, 按照价格排序, 将最符合我们预期的商品列在前面, 最终找到我我愿意购买的商家

2. 排序的基本概念与分类

排序是我们生活中经常会面对的问题. 同学们做操时会按照从矮到高排列;老师查看上课出勤情况时, 会按学生学号顺序点名; 高考录取时，会按成绩总分降序依次录取等.
假设含有n个记录的序列,为{r1, r2, r3, …, rn}，其相应的关键字分别为{k1, k2, k3, …, kn}, 需确定1, 2, …, n的一种排列p1, p2, p3, …, pn使其相应的关键字满足kp1≤kp2, …, kpn (非递减或非递增)关系，即使得序列成为一个按关键字有序的序列{rp1, rp2, rp3, …, rpn}这样的操作就称为排序说人话就是按照给定的关键字按照递增或递减顺序排序整个数据

比如选拔优秀学生成绩遇到总分相等的那该怎么办呢?

mysql> select student.name, course.name,score.score from student, course, score where student.id = score.student_id and score.course_id = course.id;

+-----------------+--------------------+-------+
| name            | name               | score |
+-----------------+--------------------+-------+
| 黑旋风李逵      | Java               |  70.5 |
| 黑旋风李逵      | 计算机原理         |  98.5 |
| 黑旋风李逵      | 高阶数学           |  33.0 |
| 黑旋风李逵      | 英文               |  98.0 |
| 菩提老祖        | Java               |  60.0 |
| 菩提老祖        | 高阶数学           |  59.5 |
| 白素贞          | Java               |  33.0 |
| 白素贞          | 计算机原理         |  68.0 |
| 白素贞          | 高阶数学           |  99.0 |
| 许仙            | Java               |  67.0 |
| 许仙            | 计算机原理         |  23.0 |
| 许仙            | 高阶数学           |  56.0 |
| 许仙            | 英文               |  72.0 |
| 不想毕业        | Java               |  81.0 |
| 不想毕业        | 高阶数学           |  37.0 |
| 好好说话        | 中国传统文化       |  56.0 |
| 好好说话        | 语文               |  43.0 |
| 好好说话        | 英文               |  79.0 |
| tellme          | 中国传统文化       |  80.0 |
| tellme          | 英文               |  92.0 |
+-----------------+--------------------+-------+

总分排完再按照次关键字排序即可

2.1 排序稳定性

也正是由于排序不仅是针对主关键字, 多个关键字的排序最终都可以转换为单个关键字的排序, 我们主要讨论耽搁关键字的排序.
但带排序的记录序列中可能存在两个或两个以上的关键字相等的记录, 排序结果可能会存在不唯一的情况.

假设ki=kj(1<=i<=n, 1<=j<=n), 且在排序前的序列中 ri 领先于 rj(即i ri 仍然领先于 rj, 则是稳定排序
反之 rj 领先于 ri 就不是稳定的

2.2 内排序与外排序

根据排序中带排序的记录是否全部放置在内存中, 排序悲愤为内排序和外排序

内排序: 在排序整个过程中, 待排序的所有记录全部放置在内存中
外排序: 由于排序的记录个数太多, 不能同时放在内存, 整个排序过程需要在内外存之间多次交换数据才能进行.

排序算法性能影响主要有3个方面：

1. 时间性能: 内排中主要是比较和移动.因此减少比较次数和移动次数即可
2. 辅助空间: 除了存放带排序所占用的存储空间之外, 执行算法所需要的其它存储空间
3. 算法的复杂性: 指的是算法本身的复杂度而非是算法的时间复杂度

2.3 分类

简单算法: 冒泡, 选择, 插排
改进算法: 希尔, 堆排, 快排, 归并

3.排序算法实现

所有排序都是升序

3.1. 冒泡排序

冒泡排序(Bubble Sort) 一种交换排序，它的基本思想是: 两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。

class bubbleSort {
    void bubbleSort(int[] arr) {
        long before = System.currentTimeMillis();
      	// 针对所有的元素重复比较交换【两个数需要比较1次, 因此需要比较 元素个数-1 次】
        for (int i = 0; i < arr.length - 1; ++i) {
          	// 立一个 flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。但这种改进对于提升性能来说并没有什么太大作用
            boolean flag = true;
          	// 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，数组中最大的书就会 "冒泡" 到数组的末尾
            for (int j = 0; j < arr.length - i - 1; ++j) {
              	// 比较相邻的元素。如果第一个比第二个大，就交换他们两个
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    flag = false;
                }
            }
            if (flag) {
                break;
            }
        }
        long after = System.currentTimeMillis();
        System.out.println("BubbleSort time: " + (after - before));
    }
}

单一步骤示意图:

加了个flag优化后的示意图:

3.2.选择排序

冒泡排序就像爱炒股票短线的人总在不断的买进卖出赚差价, 但操作频繁即使失误不多但由于操作的手续费和印花税过高而获利很少; 选择排序就像很少出手, 观察等待时机, 果断买进卖出交易次数少而最终收益丰富.所以用到它的时候, 数据规模越小越好. 唯一的好处可能就是不占用额外的内存空间.

class selectSort {
    void selectSort(int[] arr) {
        long before = System.currentTimeMillis();
      	// 总共要经历 N-1 次比较
        for (int i = 0; i < arr.length - 1; ++i) {
          	// 每轮需要比较 N-i 次并找最小值的下标
            int minIndex = i;
            for (int j = i + 1; j < arr.length; ++j) {
                if (arr[minIndex] > arr[j]) {
                    minIndex = j;
                }
            }
          	// 找到最小值就进行交换: 让小值在前大值在后就是升序
            if (minIndex != i) {
                int tmp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = tmp;
            }
        }
        long after = System.currentTimeMillis();
        System.out.println("SelectSort time: " + (after - before));
    }
}

单一步骤交换图:

3.3. 插入排序

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴, 但它的原理应该是最容易理解的了, 因为只要打过扑克牌的人都应该能够秒懂. 插入排序是一种最简单直观的排序算法, 它的工作原理是通过构建有序序列, 对于未排序数据, 在已排序序列中从后向前扫描, 找到相应位置并插入.

应该说，哪怕你是第一次玩扑克牌，只要认识这些数字，理牌的方法都是不用教的。将3和4移动到5的左侧，再将2移动到最左侧，顺序就算是理好了。这里，我们的理牌方法，就是直接插入排序法。

插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入

class insertSort {
    void insertSort(int[] arr) {
        long before = System.currentTimeMillis();
      	// 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列
        for (int i = 1; i < arr.length; ++i) {
          	// 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置【如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面】
            int tmp = arr[i];
            int j = i - 1;
            for (j = i - 1; j >= 0 && arr[j] > tmp; --j) {
                arr[j + 1] = arr[j];
            }
            arr[j + 1] = tmp;
        }
        long after = System.currentTimeMillis();
        System.out.println("InsertSOrt time:" + (after - before));
    }
}

单一步骤示意图:

1. i=1, tmp=3, arr[0]=5, arr[0]>tmp;
2. 此时把arr[0]赋值给arr[1]
3. 再把tmp 赋值给 arr[0]
4. 5放在3位置, 3放在5位置
   

进入下一次循环

1. i=2, tmp=4, arr[1]=5, arr[1]>tmp;
2. 此时把arr[1]赋值给arr[2]
3. 再把tmp 赋值给 arr[1]
4. 5放在4位置, 4放在5位置

进入下一次循环

1. i=3, tmp=6, arr中没有比6大的元素, 所以不移动
   
   进入下一次循环
2. i=4, 数组中所有元素都比 tmp=2 大, 因此arr[j+1]=arr[j];就会让他们集体后移一个单位
3. arr[j+1] = tmp 把 2填充到最后的种植的开始移动的下标的前一个位置也就是 3 的前方
   

3.4. 希尔排序

希尔排序, 也称递减增量排序算法, 是插入排序的一种更高效的改进版本. 但希尔排序是非稳定排序算法.

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

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

希尔排序的基本思想是: 先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序, 待整个序列中的记录 “基本有序” 时, 再对全体记录进行依次直接插入排序.

3.4.1 希尔排序原理

上面的简介知识大致说明了希尔排序的特征, 下面详细说明这些原理特点.

之前的插入排序, 虽然时间复杂度准确来说是 n^2/4, 但在某些时候效率很高: 当数据本身基本有序的时候只需要少量的插入操作就可以达到整个数据的排序还有就是当记录次数少的时候直接插入的优势也特别明显. 于是希尔排序就是将记录和移动逐步减少后进行的一趟插入排序

如何让记录次数减少呢?
很容易想到的就是把大量的数据进行分组. 有点类似于网络中报文的分组转发, 一次发送不完分多次发送最后合并在一起组成完整数据.

希尔排序就是把数据分割成若干子序列, 此时每个记录的排序数据量比较就少了, 然后对每个子序列内分别进行插入排序, 当整个序列基本有序最后对所有分割的数据整合在一起进行一趟直接插入排序.

注意:
{9,1,8,3,7,4,6,2}. 现在分成三组{9,1,5}, {8,3,7}, {4,6,2}哪怕将它们排好序{1,5,9},{3,7,8},{2,4,6}在合并{1,5,9,3,7,8,2,4,6}此时它们也是乱序, 根本谈不上基本有序【9在前面, 2在后面】, 所谓的基本有序就是: 小的关键字基本在前面, 大的关键字基本在后面, 不大不小的在中间. 像{2,1,3,6,4,7,5,8,9}这样可以称为基本有序了

3.4.2 希尔排序算法实现

class shellSort {
    void shellSort(int[] arr) {
        long before = System.currentTimeMillis();
        // 选择一个增量序列 gap t1，t2，……，tk，其中 ti > tj, tk = 1
        int increment = arr.length;
        do {
            increment = increment / 3 + 1;
            for (int i = increment; i < arr.length; ++i) {
                int tmp = arr[i];
                int j = i - increment;
                for (; j >= 0 && arr[j] > tmp; j -= increment) {
                    arr[j + increment] = arr[j];
                }
                arr[j + increment] = tmp;
            }
        } while (increment > 1);
        long after = System.currentTimeMillis();
        System.out.println("ShellSOrt time:" + (after - before));
    }
}

假设 shellSort(arr) 中传入了一个{9,1,5,8,3,7,4,6,2}的数组

增量因子 初始值设为带排序的记录数也就是: arr.length/3+1

1. 第一次循环

下标	0	1	2	3	4	5	6	7	8
元素	9	1	5	8	3	7	4	6	2

increment值: 4
i值: 4
tmp值: 3
j值: 0

arr[j]的值与 tmp 进行比较后进行移动, arr[0]>tmp刚好在第一个元素就移动所以
比较1次, 移动1次
之后再把 tmp 填充到 arr[j+increment] 中

下标	0	1	2	3	4	5	6	7	8
元素	3	1	5	8	9	7	4	6	2

2. 第二次循环

下标	0	1	2	3	4	5	6	7	8
元素	3	1	5	8	9	7	4	6	2

increment值: 4
i值: 5
tmp值: 7
j值: 1
arr[j]的值与 tmp 进行比较后进行移动在素组下标1, 0之前但没有比 tmp 值大的元素所以循环不执行
比较2次, 移动0次
由于 j=i-increment
所以 arr[j+increment] = tmp 也就是 arr[1+4] = 7

下标	0	1	2	3	4	5	6	7	8
元素	3	1	5	8	9	7	4	6	2

3. 第三次循环

下标	0	1	2	3	4	5	6	7	8
元素	3	1	5	8	9	7	4	6	2

increment值: 4
i值: 6
tmp值: 4
j值: 2
arr[j]的值与 tmp 进行比较后进行移动, arr[2]>tmp, 所以
比较1次, 移动1次
再然后把 tmp 赋值给 arr[j+increment]进行填充

下标	0	1	2	3	4	5	6	7	8
元素	3	1	4	8	9	7	5	6	2

4. 第四次循环

下标	0	1	2	3	4	5	6	7	8
元素	3	1	4	6	9	7	5	8	2

increment值: 4
i值:7
tmp值: 6
j值: 3
arr[3]>tmp, 所以
比较1次, 移动1次
再然后复位填充arr[j+increment]

5. 第五次循环

下标	0	1	2	3	4	5	6	7	8
元素	3	1	4	8	9	7	5	6	2

increment值: 4
i值: 8
tmp值: 2
j值: 4, 0
由于j==4, j终止条件是j>=0 && arr[j]>tmp; 调整部分是 j-=increment;
所以会将 arr[j] 之前任何比 tmp 大的值调整到后边去, 比较2次, 移动2次最后把 arr[j+increment] 用 tmp的值进行填充

下标	0	1	2	3	4	5	6	7	8
元素	2	1	4	8	3	7	5	6	9

6. 第六次循环

下标	0	1	2	3	4	5	6	7	8
元素	2	1	4	8	3	7	5	6	9

increment值: 4/3+1 = 2;
i值: 2
tmp值: 4
j值: 0
arr[0] 所以比较1次, 移动0次
最后arr[j+increment]=tmp也就是arr[0+2]=4
后续的循环步骤省略, 由此我们发现实现基本有序靠的是 增量因子, 它将数组中的元素划分为若干子序列, 对每个子序列进行插入排序, 将内部所有元素实现基本有序之后也就是 增量因子 为1的时候, 全体数据最后进行一趟 直接插入排序

3.4.3 希尔排序复杂度分析

通过这段代码的剖析, 相信大家都明白, 希尔排序并不是随便分组后各自排序而是将相隔某个 “增量” 的记录组层一个子序列, 实现跳跃式的移动, 使得排序效率提高.
这里的增量选取就很关键, 本文中时 increment/3+1, 可究竟该选取什么样的增量才是最好目前还是一个数学难题, 迄今为止还没有找到一个好的增量序列. 不过大量的研究表明, 当增增量序列为 dlta=2^(t-k+1)-1[0<=k<=t<=log(n+1)] 时可以获取不错的效率, 其时间复杂度为O(N^(3/2)), 需要注意的是增量序列的最后一个增量值必须是1才行, 另外由于希尔排序是一个跳跃式的交换, 所以不是稳定的排序

3.5. 堆排序 3.5.1 堆排序原理

前面说到的简单选择排序, 它在待排序的 n 个记录中选择一个最小的记录需要比较 n-1 次
可惜的是这样的操作, 并没有把每一趟的比较结果进行保存, 在后一趟的比较中, 有许多比较在之前已经做过了, 但由于前一趟比较时未保存结果, 所以后续的比较又重复这些操作, 因为记录的次数比较多
如果可以做到每次选择到最小记录的同时还能保存比较结果还能对这些结果做出相应的调整, 那样总体效率就很高了, 而堆排就是对选择排序的一种改进

那什么是堆排序呢?

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序.
分为两种方法:

1. 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
2. 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列

堆调整前后示意图

大小顶堆示意图

3.5.2 堆排序算法实现

class heapSort {
    void heapSort(int[] arr) {
        long before = System.currentTimeMillis();
        // 1.升序就调整为大根堆
        createBigHeap(arr);
        int end = arr.length - 1;
      	// 2.堆顶(最大值)和堆尾交换
        while (end > 0) {
            int tmp = arr[0];
            arr[0] = arr[end];
            arr[end] = tmp;
          	// 3.每次都调整堆把新的堆顶元素调整到相应位置
            shiftDown(arr, 0, end--);
        }
        long after = System.currentTimeMillis();
        System.out.println("HeapSort time: " + (after - before));
    }

    private void createBigHeap(int[] arr) {
      	// 1.arr.length-1选取数组最后一个元素, 再-1是为了求得父节点下标
        for (int parent = (arr.length - 2) >> 1; parent >= 0; --parent) {
          	// 2.对每一个父节点进行调整
            shiftDown(arr, parent, arr.length);
        }
    }

    private void shiftDown(int[] arr, int parent, int sz) {
      	// 1.根据父节点求的其子节点
        int child = (parent << 1) + 1;
      	// 2.
        while (child < sz) {
          	// 3.判定右子节点不越界且保证左子树的值小于右子树
            if (child + 1 < sz && arr[child] < arr[child + 1]) {
            //if (child + 1 < sz && arr[child] > arr[child + 1]) {//符号改变后就是小顶堆: 降序
                ++child;
            }
          	// 4.遇到左子树比右子树还大, 那么就把左子树和父节点进行交换
            if (arr[child] > arr[parent]) {
            //if (arr[child] < arr[parent]) {// 符号改变后就是小顶堆: 降序
                int tmp = arr[child];
                arr[child] = arr[parent];
                arr[parent] = tmp;
                // 5.更新父节点, 使其带动子节点下沉
                parent = child;
                child = (parent << 1) + 1;
            } else {
              	// 6.如果左子树值小于父节点, 无需调整
                break;
            }
        }
    }
}

详细步骤分析

图1⃣️是一个大顶堆, 90为最大值, 将 90 与 20(末尾元素)呼唤, 如图2⃣️所示, 此时 90 就成了整个堆序列的最后一个元素, 将 20 经过调整, 使得除 90 以外的节点继续满足大顶堆定义.见图3⃣️

在考虑 30 和 80 互换…

看到这儿, 相信大家已经明白堆排序的基本思想了, 不过要实现它还需要解决两个问题

1. 如何由一个无须序列构建成一个堆
2. 如何在输出堆顶元素后, 调整剩余元素成为一个新的堆

要解释清楚它们, 我们来详解一下代码
这是一个大的思路框架

// 1.升序就调整为大根堆
createBigHeap(arr);
int end = arr.length - 1;
// 2.堆顶(最大值)和堆尾交换
while (end > 0) {
    int tmp = arr[0];
    arr[0] = arr[end];
    arr[end] = tmp;
  	// 3.每次都调整堆把新的堆顶元素与堆尾元素进行调整
    shiftDown(arr, 0, end--);
}

假设我们要排序的序列式{50,10,90,30,70,40,80,60,20}. 那么 end = 8 while循环每次交换堆顶元素和"堆尾"元素, 交换完之后再重新调整堆的大小.
再看 createBigHeap 函数

private void createBigHeap(int[] arr) {
 	// 1.arr.length-1选取数组最后一个元素, 再-1是为了求得父节点下标
   for (int parent = (arr.length - 2) >> 1; parent >= 0; --parent) {
     	// 2.对每一个父节点进行调整
       shiftDown(arr, parent, arr.length);
   }
}

第一次当把 9 传入函数中, 是从4开始到1结束【包含1, 这里的1其实就是数组下标0元素的位置, 为了好让大家解读暂且理解为1】
他们都是有孩子的父节点, 注意灰色节点的下标编号

4怎么来的呢?
还记得for (int parent = (arr.length - 2) >> 1; parent >= 0; --parent) 吗?
9-2=7, 7/2=3, 3+1=4
4就是左子树, 4+1=5就是右子树
那么 parent–>4,3,2,1的调整每个父节点的左右子树使其达成大顶堆.
知道了调整的是哪些节点, 我们在看关键的 shiftDown 函数如何实现的

private void shiftDown(int[] arr, int parent, int sz) {
      	// 1.根据父节点求的其子节点
        int child = (parent << 1) + 1;
      	// 2.
        while (child < sz) {
          	// 3.判定右子节点不越界且保证左子树的值小于右子树
            if (child + 1 < sz && arr[child] < arr[child + 1]) {
            //if (child + 1 < sz && arr[child] > arr[child + 1]) {//符号改变后就是小顶堆: 降序
                ++child;
            }
          	// 4.遇到左子树比右子树还大, 那么就把左子树和父节点进行交换
            if (arr[child] > arr[parent]) {
            //if (arr[child] < arr[parent]) {// 符号改变后就是小顶堆: 降序
                int tmp = arr[child];
                arr[child] = arr[parent];
                arr[parent] = tmp;
                // 5.更新父节点, 使其带动子节点下沉
                parent = child;
                child = (parent << 1) + 1;
            } else {
              	// 6.如果左子树值小于父节点, 无需调整
                break;
            }
        }
    }

1. 函数第一次被调用的时候传入的是
   arr={50,10,90,30,70,40,80,60,20}
   parent=3
   sz=9

child=parent2+1得7
while(7<9)成立
child+1 右子树没有越界, 但左子树7⃣️>右子树8⃣️所以child5⃣️不自增
child7⃣️ > child3⃣️, 交换parent3⃣️和child7⃣️的值
新的父节点就是parent7⃣️, 其最小的左子树已经越界while((27+1) < 9), 所以循环结束

调整完毕之后

2. 函数第二次被调用的时候传入的是
   arr={50,10,90,30,70,40,80,60,20}
   parent=2
   sz=9

child=2*2+1得5
while(5<9)成立
child+1右子树不越界且左子树child5⃣️<右子树child6⃣️, child5⃣️节点自增
右子树child6⃣️

3. 函数第三次被调用的时候传入的是
   arr={50,10,90,30,70,40,80,60,20}
   parent=1
   sz=9

child=12+1得3
while(3<9)成立
child+1右子树不越界且左子树child3⃣️>右子树4⃣️, child3⃣️节点不自增
child3⃣️ 新parent3⃣️, 新child7⃣️
while(7<9)
7+1不越界, child7⃣️>child8⃣️, 不自增
child7⃣️ 新parent7⃣️, 新child【27+1】已经越过9下标所以会推出循环

4. 函数第三次被调用的时候传入的是
arr={50,10,90,30,70,40,80,60,20}
parent=0
sz=9

child=20+1
while(1<9)成立
(1+1)<9且左子树child1⃣️>右子树child2⃣️, 所以child1⃣️不自增;
child1⃣️>parent0⃣️, 所以不交换
新parent2⃣️, 新child5⃣️
(5+1)<9且child5⃣️ child6⃣️ 新的parent6⃣️, 新child【26+1】已经越界推出循环

5. 由于 parent=在第四次循环完毕之后为-1, 所以结束第一次调整

发现, 此时已经是一个大顶堆

6. 在看

while (end > 0) {
            int tmp = arr[0];
            arr[0] = arr[end];
            arr[end] = tmp;
          	// 3.每次都调整堆把新的堆顶元素调整到相应位置
            shiftDown(arr, 0, end--);
        }

将堆顶元素与堆尾元素交换

再 shiftDown 函数继续调整尺寸-1之后的堆[也就是把90排除在外之后的堆大小]
…然后无限循环下去, 直到堆的尺寸为1之后说明调整完毕, 此时就是升序排列的数组

3.5.2 堆排序复杂度分析

上面的数学公式说明了堆的排序时间复杂度为何O(logN)

它的运行时间主要损耗在构建堆和重建堆上, 在建堆过程中, 因为我们是完全二叉树丛最下层最右边的非终端节点开始构建, 将它与其他孩子进行比较和若有比较的互换, 对于每个非终端节点来说, 其实最多进行两次比较和互换操作, 因此整个构建堆的时间复杂度为O(n)

在正式排序时, 重建堆时间复杂度为O(nlongN), 因为每个节点狗咬构造

所以堆排序的时间复杂度为O(nlogN), 由于排序对原始记录的排序状态并不敏感, 因此无论是最好, 最坏和平均时间复杂度均为O(nlogN), 这在性能上显然要远远好过冒泡, 简单选择, 直接插入的时间复杂度了

3.6. 归并排序

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

• 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
• 自下而上的迭代；

为了更清晰说清楚这里的思想, {16,7,13,10,9,15,3,2,5,8,12,1,11,4,6,14}通过两两合并排序后再合并, 最终获得了一个有序数组. 注意观察它的形状, 像极了一棵倒置的完全二叉树, 通常涉及到完全二叉树结构的排序算法效率一般都不低.

3.5.1 递归实现归并排序

class mergeSort {
    void mergeSort(int[] arr) {
        long start = System.currentTimeMillis();
        _mergeSort(arr, 0, arr.length);
        long end = System.currentTimeMillis();
        System.out.println("mergeSort time:" + (end - start));
    }

    // 辅助递归
    private void _mergeSort(int[] arr, int left, int right) {
        if (right - left <= 1) {
            
            return;
        } else {
            int mid = (left + right) >> 1;
            
            _mergeSort(arr, left, mid);
            _mergeSort(arr, mid, right);
            merge(arr, left, mid, right);
        }
    }

    
    private void merge(int[] arr, int left, int mid, int right) {
        
        if (left >= right) {// 空区间
            return;
        } else {
            int[] tmp = new int[right - left];
            int tmpIndex = 0;// 表示当前元素该放到临时空间哪个位置上
            int cur1 = left;
            int cur2 = mid;
            while (cur1 < mid & cur2 < right) {// 保证区间有效
                if (arr[cur1] <= arr[cur2]) {// 为了保证稳定性
                    tmp[tmpIndex++] = arr[cur1++];// 把 cur1 对应的元素插入到临时空间中
                } else {
                    tmp[tmpIndex++] = arr[cur2++];
                }
            }
            // 循环结束之后, 需要把剩余的元素也都拷贝到最终结果里
            while (cur1 < mid) {
                tmp[tmpIndex++] = arr[cur1++];
            }
            while (cur2 < right) {
                tmp[tmpIndex++] = arr[cur2++];
            }
        
            for (int i = 0; i < tmp.length; i++) {
                arr[left + i] = tmp[i];
            }
        }
    }

    
    void mergeSortByLoop(int[] arr) {
        long start = System.currentTimeMillis();
        int gap = 1;// gap 用于限定分组, 每个待归并的数组长度
        for (; gap < arr.length; gap *= 2) {
            // 当前两个待归并的数组
            for (int i = 0; i < arr.length; i += 2 * gap) {
                
                int left = i;
                int mid = i + gap > arr.length ? arr.length : i + gap;
                int right = i + 2 * gap > arr.length ? arr.length : i + 2 * gap;
                merge(arr, left, mid, right);
            }
        }
        long end = System.currentTimeMillis();
        System.out.println("mergeSortByLoop time:" + (end - start));
    }
}

代码详细步骤解析:

void mergeSort(int[] arr) {
    long before = System.currentTimeMillis();
    mergeSortInternal(arr, 0, arr.length);
    long after = System.currentTimeMillis();
    System.out.println("MergeSort time: " + (after - before));
    }

函数调用入口, 输入一个左闭右开的区间[0, arr.length)

private void mergeSortInternal(int[] arr, int left, int right) {
    if (right - left <= 1) {
        return;
    } else {
        int mid = (left + right) >> 1;
        mergeSortInternal(arr, left, mid);
        mergeSortInternal(arr, mid, right);
        merge(arr, left, mid, right);
    }
}

进行区间划分左右递归
最后交给merge进行合并[left, mid), [mid, right)两个区间

private void merge(int[] arr, int left, int mid, int right) {
      int[] tmp = new int[right - left + 1];
      int tmpIndex = 0;
      int cur1 = left, cur2 = mid;
      while (cur1 < mid && cur2 < right) {
          if (arr[cur1] <= arr[cur2]) {// 为了保证稳定性
              tmp[tmpIndex++] = arr[cur1++];// 把 cur1 对应的元素插入到临时空间中
          } else {
              tmp[tmpIndex++] = arr[cur2++];
          }
      }
      	// 处理剩余数据
        while (cur1 < mid) {
            tmp[tmpIndex++] = arr[cur1++];
        }
        while (cur2 < right) {
            tmp[tmpIndex++] = arr[cur2++];
        }
      	// 数据返回原数组位置, 所以加上是arr[left+i]而不是arr[i]
        for (int i = 0; i < tmpIndex; i++) {
            arr[left + i] = tmp[i];
        }
    }

区间合并的具体算法实现

假设有 {50,10,90,30,70,40,80,60,20} 数据, 那么递归代码如何执行的呢?

传入的其实左区间值是0, 右区间值是9也就是[0, 9)
然后划分区间为[0,4), 左区间为[4, 9)
[0,2), [2, 4), [4,6), [6, 9)
由于递归的终止条件是right-left<=1 也就是有两个元素的时候就推出递归, 通过 merge 函数进行合并

3.5. 非递归实现归并排序

非递归代码

void mergeSortTraversalNo(int[] arr) {
        long before = System.currentTimeMillis();
      	// gap: 限定每个待归并数组的长度
        int gap = 1;
        for (; gap < arr.length; gap *= 2) {
          	// 当前两个待归并的数组
            for (int i = 0; i < arr.length; i += 2 * gap) {
                int left = i;
                int mid = i+gap> arr.length? arr.length : i+gap;
                int right = i+2*gap> arr.length? arr.length : i+2*gap;
                merge(arr, left, mid, right);
            }
        }
        long after = System.currentTimeMillis();
        System.out.println("MergeSortTraversalNo time: " + (after - before));
    }

变量 gap 和 I 记住即可,
左区间为i，中间间隔是i+gap，右区间为i+2*gap
其中左中右均要保持数组不越界

3.5. 归并排序复杂度分析

我们来分析一下归并 排序的时间复杂度，一趟归并需要将arr[1] ~ arr[n]中相邻的长度为h的有序序列进行两两归并。并将结果放到tmp[1]~TR1[n]中，这需要将待排序序列中的所有记录扫描一遍， 因此耗费0(n)时间，而由完全二叉树的深度可知，整个归并排序需要进行[log2n]次，因此，总的时间复杂度为0(nlogn), 而且这是归并排序算法中最好、最坏、平均的时间性能。

由于归并排序在归并过程中需要与原始记录序列同样数量的存储空间存放归并结果以及递归时深度为log2n的栈空间，因此空间复杂度为0(n+logn]。

另外，对代码进行仔细研究，发现merge函数中有if (arr[cur1]<=arr[cur2])语句， 这就说明它需要两两比较，不存在跳跃，因此归并排序是一种稳定的排序算法。

也就是说，归并排序是一-种比较占用内存，但却效率高且稳定的算法。

3.7. 快速排序

终于到我们的高手登场了, 如果将来工作后, 你的老板让你一写一个排序算法, 而你会的算法中竟然没有快速排序, 还是不要声张, 偷偷去把快速排序算法找来练习练习抱抱佛脚至少不被嘲笑

希尔排序相当于是直接插入排序的升级, 他们同属于插入排序类
堆排序相当于简单选择排序的升级, 他们同属于选择排序
而快速排序则认为是前面最慢的冒泡排序的升级版, 它们都属于交换排序类

快速排序也是通过不断比较和移动交换来实现排序的, 只不过它的实现增大了记录的比较和移动的距离, 将关键字较大的记录从前面直接移动到后面; 关键字较小的记录从后面直接移动到前面, 从而减少了总的比较次数和移动交换次数

3.7.1 快速排序算法基本思想

通过一趟排序将待排记录分割成独立的两部分, 其中一部分记录的关键字均比另一部分记录的关键字小, 则可分别对这两部分记录继续进行排序, 以达到整个序列有序的目的

3.7.2 快速排序递归算法实现及优化步骤

class quickSort {
    void quickSort(int[] arr) {
        long start = System.currentTimeMillis();
        quick(arr, 0, arr.length-1);
        long after = System.currentTimeMillis();
        System.out.println("quickSort`time:" + (after - start));
    }

    private void quick(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        } else {
            int pivot = partition(arr, left, right);
            quick(arr, left, pivot - 1);
            quick(arr, pivot + 1, right);
        }
    }

    private int partition(int[] arr, int left, int right) {
        int tmp = arr[left];
        while (left < right) {
            while (left < right && arr[right] >= tmp) {
                --right;
            }
            arr[left] = arr[right];
            while (left < right && arr[left] <= tmp) {
                ++left;
            }
            arr[right] = arr[left];
        }
        arr[left] = tmp;
        return left;
    }
}

代码分析

1. 首先执行quick(arr, 0, arr.length-1)
   传入[0, arr.length-1]的闭区间【注意与归并排序的区间传参区分】
2. 再执行

private void quick(int[] arr, int left, int right) {
    if (left >= right) {
        return;
    } else {
        int pivot = partition(arr, left, right);
        quick(arr, left, pivot - 1);
        quick(arr, pivot + 1, right);
    }
}

这个是递归进行分治

3. 再执行

private int partition(int[] arr, int left, int right) {
        int tmp = arr[left];
        while (left < right) {
            while (left < right && arr[right] >= tmp) {
                --right;
            }
            // 右边找到小的就直接移到左边
            arr[left] = arr[right];
            while (left < right && arr[left] <= tmp) {
                ++left;
            }
            // 左边找到大的就直接移到右边
            arr[right] = arr[left];
        }
        //然后给枢纽填充且返回枢纽值
        arr[left] = tmp;
        return left;
}

一个中枢, 直接移动两端元素然后返回枢纽值

刚才的快速排序还是有不少可以改进的地方
优化选取枢轴

如果我们选取的 pivot 处于整个序列的中间位置, 那么我们可以将整个序列分成小数集合和大数集合. 但注意, 这仅仅是如果, 如果运气倒霉, 选了个最小值或者最大值作为枢纽来分治整个数组, 那么这样的划分会导致效率下降
有人说应该随机选取left和right之间的数, 虽然性能上解决了基本有序的序列快速排序是性能瓶颈, 不过随机就很可能撞大运, 随机到了一个极值那不等于白给?
下边是加入了随机选取法

private void quick(int[] arr, int left, int right) {
    if (left >= right) {
        return;
    } else {
    	Random random = new Random();
    	int rand = random.nextInt(right - left) + left + 1;
    	int tmp = arr[left];
    	arr[left] = arr[rand];
    	arr[rand] = tmp;
        int pivot = partition(arr, left, right);
        quick(arr, left, pivot - 1);
        quick(arr, pivot + 1, right);
    }
}

再改进, 就出现了三数取中法

private void quick(int[] arr, int left, int right) {
    if (left >= right) {
        return;
    } else {
    	medianOfThree(arr, left, right);
        int pivot = partition(arr, left, right);
        quick(arr, left, pivot - 1);
        quick(arr, pivot + 1, right);
    }
}

private void medianOfThree(int[] arr, int left, int right) {
	 //arr[mid]
     int mid = (left + right) >> 1, tmp = 0;
     if (arr[mid] > arr[left]) {
         tmp = arr[mid];
         arr[mid] = arr[left];
         arr[left] = tmp;
     }
     if (arr[mid] > arr[right]) {
         tmp = arr[mid];
         arr[mid] = arr[right];
         arr[right] = tmp;
     }
     if (arr[left] > arr[right]) {
         tmp = arr[left];
         arr[left] = arr[right];
         arr[right] = tmp;
     }
}

选取三个关键字进行排序, 将中间数作为枢纽, 一般是取左端, 中间和右端三个数, 也可以随机选取. 这样至少这个中间数一定不会是最小或者最大数, 从概率上说, 去三个数均为最小或最大数的可能性微乎其微. 因此中间数位于较为中间的值的可能性就大大提高了.
由于整个序列是无序状态, 随机选取三个数和从左中右端取三个数其实是一回事, 而且随机数生成器本身还会带来时间上的开销, 因此随机生成不予考虑.

优化递归操作

private void quick(int[] arr, int left, int right) {
    if (left >= right) {
        return;
    } else {
    	medianOfThree(arr, left, right);
    	while(left < right){
    		int pivot = partition(arr, left, right);
    		quick(arr, left, pivot - 1);
    		left = pivor + 1;
		}
    }
}

优化小数组时的排序方案
当数组非常小的时候直接插入是简单排序中性能最好的, 其原因在于快速排序用到了递归操作, 在大量数据排序时, 这点性能影响相对于它的整体算法优势而言是忽略的, 但如果数组只有几个记录需要排序时, 这就成了一个杀鸡用牛刀的问题.

    private void quick(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        } else {
        	// 希尔排序快于插入排序就用希尔排序了, 数据量够小的话也可以用直接插入排序优化
            if (right - left <= 150) {
                int gap = arr.length - 1;
                while (gap > 0) {
                    for (int i = gap; i < arr.length; i++) {
                        int tmp = arr[i];
                        int j = i - gap;
                        for (j = i - gap; j >= 0 && arr[j] > tmp; j -= gap) {
                            arr[j + gap] = arr[j];
                        }
                        arr[j + gap] = tmp;
                    }
                    gap >>= 1;
                }
            } else {
                
//                Random random = new Random();
//                int rand = random.nextInt(right - left) + left + 1;
//                int tmp = arr[left];
//                arr[left] = arr[rand];
//                arr[rand] = tmp;

                
                int pivot = partition(arr, left, right);
                quick(arr, left, pivot - 1);
                quick(arr, pivot + 1, right);
            }
        }
    }

3.7.4 快速排序非递归实现

// 非递归实现快排
void quickSortTraversalNo(int[] arr) {
     long before = System.currentTimeMillis();
     Stack stack = new Stack<>();
     stack.push(0);
     stack.push(arr.length - 1);
     while (!stack.empty)) {
         // 注意存取顺序
         int right = stack.pop();
         int left = stack.pop();
         if (left >= right) {
             continue;
         } else {
             int pivot = partition(arr, left, right);
             // 左右区间谁先开始的顺序不影响
             stack.push(left);
             stack.push(pivot - 1);
             stack.push(pivot + 1);
             stack.push(right);
         }
     }
     long after = System.currentTimeMillis();
     System.out.println("QuickSortTraversalNo time: " + (after - before));
 }

排序算法	平均时间复杂度	最好情况	最坏情况	空间复杂度	稳定性
冒泡排序	O(N^2)	O(N)	O(N^2)	O(1)	稳定
选择排序	O(N^2)	O(N^2)	O(N^2)	O(1)	不稳定
插入排序	O(N^2)	O(N)	O(N^2)	O(1)	稳定
希尔排序	O(logN)	O(NlogN)	O(Nlog^2N)	O(1)	不稳定
堆排序	O(NlogN)	O(NlogN)	O(NlogN)	O(1)	不稳定
归并排序	O(NlogN)	O(NlogN)	O(NlogN)	O(N)	稳定
快速排序	O(NlogN)	O(NlogN)	O(NlogN^2)	O(N)	不稳定