12、数据结构与算法 - 实战：希尔排序、快速排序（递归、好理解）、归并排序（递归、难理解）
前言
- 上节的三个排序算法：冒泡、选择、插入，较为简单，好理解，使用比较、交换的思想。但也都是基础。
- 这节的三个排序算法：希尔、快速【看注释比较容易理解思路】、归并，难理解，使用递归的思想。
- 这三个是难点，但也是重点。加油
一、希尔排序
1.1 简单插入排序存在的问题
我们看简单的插入排序可能存在的问题.
数组arr = {2,3,4,5,6,1} 这时需要插入的数 1(最小), 这样的过程是：
{2,3,4,5,6,6}
{2,3,4,5,5,6}
{2,3,4,4,5,6}
{2,3,3,4,5,6}
{2,2,3,4,5,6}
{1,2,3,4,5,6}
结论: 当需要插入的数是较小的数时，后移的次数明显增多，对效率有影响.
1.2 基本介绍
希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是 简单插入排序 经过改进之后的一个更高效的版本，也称为 缩小增量排序。
1.3 思路分析
1.3.1希尔排序法基本思想
希尔排序是**把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止**
1.3.2希尔排序法示意图
1.4 代码实现
有一群小牛, 考试成绩分别是 {8,9,1,7,2,3,5,4,6,0} 请从小到大排序. 请分别使用
1、 希尔排序时，对有序序列在插入时采用**交换法,并测试排序速度,相对较慢（容易理解）；
2、 希尔排序时，对有序序列在插入时采用移动法**,并测试排序速度,相对较快（不易理解）；
package com.feng.ch09_sort;
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
/*
* 希尔排序：
* 对插入排序的 进一步优化
* 使用到了 分组，并且缩小增量的 思想。
* 第一次分组，gap(分组的次数)=【数组大小】/2,
* 第二次分组，gap = （第一次分组次数）/2,
* 第三次分组，gap = （上一次分组次数）/2,
*
* 有两种方式：
* 第一种：交换式
* 里面使用了冒泡排序的 交换思想
* 效率低，容易理解 80000数据排序使用 14-19 S
*
* 第二种：移位式
* 里面使用了 简单插入排序的 插入移位思想
* 效率高，不易理解 8万数据： 1S ， 80万数据： 1S， 800万数据：4S
* */
public class S4_ShellSort {
public static void main(String[] args) {
int[] array = {
8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
System.out.println("初始数组：");
System.out.println(Arrays.toString(array));
System.out.println();
System.out.println("排序后");
// deductionShellSortBychange(array);
int[] ints = shellSortByChange(array); // 交换式
System.out.println(Arrays.toString(ints));
// 测试 80000 个数据排序 所用的时间
System.out.println();
System.out.println("测试 80000 个数据 采用希尔排序（交换式） 所用的时间:");
testTime(); // 交互式：19S, 移位式：1S
}
/*
* 测试一下 希尔排序的速度O(n^2), 给 80000 个数据，测试一下
* */
public static void testTime() {
// 创建一个 80000个的随机的数组
int array2[] = new int[80000];
for (int i = 0; i < 80000; i++) {
array2[i] = (int) (Math.random() * 8000000); // 生成一个[ 0, 8000000] 数
}
// System.out.println(Arrays.toString(array2)); // 不在打印，耗费时间太长
long start = System.currentTimeMillis(); //返回以毫秒为单位的当前时间
System.out.println("long start:" + start);
Date date = new Date(start); // 上面的也可以不要，但是我想测试
System.out.println("date:" + date);
SimpleDateFormat format = new SimpleDateFormat("yyyy-mm-dd HH:mm:ss");
System.out.println("排序前的时间是=" + format.format(date));
shellSortByChange(array2); // 交互式
// shellSortByMove(array2); // 移位式
System.out.println();
long end = System.currentTimeMillis();
Date date2 = new Date(end); // 上面的也可以不要，但是我想测试
System.out.println("排序后的时间是=" + format.format(date2));
System.out.println("共耗时" + (end - start) + "毫秒");
System.out.println("毫秒转成秒为：" + ((end - start) / 1000) + "秒");
}
/*
* 对交换式的希尔排序进行优化 -》》移位法
* */
public static int[] shellSortByMove(int[] array) {
// 增量gap, 并逐步的缩小增量
for (int gap = array.length / 2; gap > 0; gap /= 2) {
// 共分 3 组
// 从第 gap 个元素，逐个对其所在的组进行直接插入排序
for (int i = gap; i < array.length; i++) {
// 这里使用了 前面学习的 直接插入排序
int j = i;
int temp = array[j];
if (array[j] < array[j - gap]) {
while ((j - gap) >= 0 && temp < array[j - gap]) {
//移动
array[j] = array[j - gap];
j -= gap;
}
//当退出while后，就给temp找到插入的位置
array[j] = temp;
}
}
}
return array;
}
/*
* 交换式排序 整合
* */
public static int[] shellSortByChange(int[] array) {
int temporary = 0;
int count = 0;
for (int gap = array.length / 2; gap > 0; gap /= 2) {
// 三次分组。
for (int i = gap; i < array.length; i++) {
// 有几组，循环遍历几次，也就比较几次。
// 遍历各组中所有的元素（共 gap 组，每组有 个元素），步长为 gap
// 这里使用了交换：也就是前面学习的 冒泡排序的思想
for (int j = i - gap; j >= 0; j -= gap) {
if (array[j] > array[j + gap]) {
temporary = array[j];
array[j] = array[j + gap];
array[j + gap] = temporary;
}
}
}
// System.out.println("希尔排序第" + (++count) + "轮=" + Arrays.toString(array));
}
return array;
}
/*
* 希尔排序：采用交换式
* 使用逐步推导的方式
* */
public static int[] deductionShellSortBychange(int[] array) {
// 临时变量，存放交换的数据
int temporary = 0;
/*
* 希尔排序的第 1 轮排序
* */
System.out.println("第 1 轮排序");
// 因为第 1 轮排序，是将 10 个数据分成了5组 ，所以要比较 5 次， i 从 5 开始
for (int i = 5; i < array.length; i++) {
// 共遍历 5 次，即 比较 5 次
// 遍历各组中所有的元素（共 5 组，每组有2个元素），步长为 5
for (int j = i - 5; j >= 0; j -= 5) {
// 仅比较一次，走一次逻辑，就知道啦
if (array[j] > array[j + 5]) {
temporary = array[j];
array[j] = array[j + 5];
array[j + 5] = temporary;
}
}
}
System.out.println(Arrays.toString(array));
/*
* 希尔排序的第 2 轮排序
* */
System.out.println("第 2 轮排序");
// 因为第 1 轮排序，是将 10 个数据分成了 5/2 = 2组
for (int i = 2; i < array.length; i++) {
// 遍历各组中所有的元素（共 5 组，每组有2个元素），步长为 5
for (int j = i - 2; j >= 0; j -= 2) {
if (array[j] > array[j + 2]) {
temporary = array[j];
array[j] = array[j + 2];
array[j + 2] = temporary;
}
}
}
System.out.println(Arrays.toString(array));
/*
* 希尔排序的第 3 轮排序
* */
System.out.println("第 3 轮排序");
// 因为第 3 轮排序，是将 10 个数据分成了 2/2 = 1组
for (int i = 1; i < array.length; i++) {
// 遍历各组中所有的元素（共 5 组，每组有2个元素），步长为 5
for (int j = i - 1; j >= 0; j -= 1) {
if (array[j] > array[j + 1]) {
temporary = array[j];
array[j] = array[j + 1];
array[j + 1] = temporary;
}
}
}
System.out.println(Arrays.toString(array));
return array;
}
}
1.5 测试结果
二、快速排序
2.1 基本介绍
快速排序（Quicksort）是对冒泡排序的一种改进。
基本思想是 ：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再 按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行 ，以此达到整个数据变成有序序列
2.2 思路分析
1、 先把数组中的一个数当做基准数，一般会把数组中最左边的数当做基准数；
2、 然后从两边进行检索，先从右边往左检索比基准数小的，再从左边往右检索比基准数大的；
3、 如果检索到了，就停下，交换这两个元素然后继续检索；
4、 如果这两个索引指针相遇了，就退出循环；
5、 将基准数与这两个索引遇到的数字进行对换；
6、 基准数在这里就归位了，左边的数字都比基准数小，右边的数字都比基准数大；
7、 然后使用递归进行排序；
2.3 代码实现
package com.feng.ch09_sort;
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
/*
* 快速排序：
* 对冒泡排序的优化
*
* 时间复杂度：O(nlog2n)
* 速度测试 ： 8万数据： 1S不到， 80万数据： 1S 不到， 800万数据：1S不到 ，速度超级快
* */
public class S5_QuickSort {
public static void main(String[] args) {
int[] array = {
-9, 78, 0, 23, -567, 70, -1, 900, 4561};
System.out.println("初始数组：");
System.out.println(Arrays.toString(array));
System.out.println();
System.out.println("排序后：");
quickSort(array, 0, array.length - 1);
System.out.println(Arrays.toString(array));
// 测试 80000 个数据排序 所用的时间
System.out.println();
System.out.println("测试 80000 个数据 采用快速排序（交换式） 所用的时间:");
testTime(); // 8万数据： 1S不到， 80万数据： 1S 不到， 800万数据：2-3
}
/*
* 测试一下 快速排序的速度, 给 80000 个数据，测试一下
* */
public static void testTime() {
// 创建一个 80000个的随机的数组
int array2[] = new int[8000000];
for (int i = 0; i < 8000000; i++) {
array2[i] = (int) (Math.random() * 8000000); // 生成一个[ 0, 8000000] 数
}
// System.out.println(Arrays.toString(array2)); // 不在打印，耗费时间太长
long start = System.currentTimeMillis(); //返回以毫秒为单位的当前时间
System.out.println("long start:" + start);
Date date = new Date(start); // 上面的也可以不要，但是我想测试
System.out.println("date:" + date);
SimpleDateFormat format = new SimpleDateFormat("yyyy-mm-dd HH:mm:ss");
System.out.println("排序前的时间是=" + format.format(date));
quickSort(array2, 0, array2.length - 1); // 移位式
System.out.println();
long end = System.currentTimeMillis();
Date date2 = new Date(end); // 上面的也可以不要，但是我想测试
System.out.println("排序后的时间是=" + format.format(date2));
System.out.println("共耗时" + (end - start) + "毫秒");
System.out.println("毫秒转成秒为：" + ((end - start) / 1000) + "秒");
}
/*
* 快速排序方法：通俗异同，直接看注释即可
*
* @param array 需要排序的数组
* @param left 最左边的下标，也是索引
* @param right 最右边的下标，也是索引
* */
public static void quickSort(int[] array, int left, int right) {
// 进行判断，如果左边索引比右边索引要大，是不合法的，直接使用return 结束这个方法
if (right < left) {
return;
}
// 定义变量保存基准数，这里的基准数用最左边的数来代替。
int base = array[left];
// 定义变量 i ，指向最左边
int i = left;
// 定义变量 j, 指向最右边
int j = right;
// 当 i 和 j 不相遇的时候，就在循环中进行检索。
while (i != j) {
// 先 由j 从右往左检索比基准数小的，如果检索到比基准数小的就停下
// 如果检索比基准数大的或者相等的，就继续检索
while (array[j] >= base && i<j) {
j--; // j 从右往左移动
}
// i 从左往右检索。找比基准数 大的，
while (array[i] <= base && i<j) {
i++;// i 从左往右移动
}
// 如果代码走到这儿，i 和 j 都停下了，。然后交换 i 和 j 位置的元素
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
/*
* 如果上面的 while 循环条件不成立了，会跳出这个循环，往下执行。
* 如果这个条件不成立 说明 i 和 j 相遇了，也就是相等
* 如果 i 和 j 相遇了，就交换基准数这个元素 和相遇位置的元素。
* 把 相遇位置的元素 赋值 给基准数这个位置的元素
* */
array[left] = array[i];
// 把基准数赋值给相遇位置的元素
array[i] = base;
// 基准数在这里就归位了，左边的数字都比基准数小，右边的数字都比基准数大。
// 对基准数的 左边进行排序
quickSort(array, left, i-1);
// 排右边
quickSort(array, j+1, right);
}
}
2.4 测试结果
三、归并排序
3.1 基本介绍
归并排序（MERGE-SORT）是利用 归并 的思想实现的排序方法，该算法采用经典的**分治**（divide-and-conquer）策略（分治法将问题 分 (divide)成一些小的问题然后递归求解，而 治 (conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
3.2 思路分析
说明:
可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程。
3.3 代码实现
package com.feng.ch09_sort;
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
/*
* 归并排序
*
* 速度测试： 8万数据： 117Ms， 80万数据： 395Ms， 800万数据：2-3S
* */
public class S6_MergetSort {
public static void main(String[] args) {
int[] array = {
8, 4, 5, 7, 1, 3, 6, 2}; // 8-> merge 7次， 80000-> merge 80000-1=7999次
int[] temp = new int[array.length];
System.out.println("原始数组：");
System.out.println(Arrays.toString(array));
System.out.println();
System.out.println("排序后：");
mergetSort(array,0, array.length-1, temp);
System.out.println(Arrays.toString(array));
// 测试 80000 个数据排序 所用的时间
System.out.println();
System.out.println("测试 80000 个数据 采用归并排序（交换式） 所用的时间:");
testTime(); // 8万数据： 1S不到， 80万数据： 1S 不到， 800万数据：2-3
}
/*
* 测试一下 归并排序的速度, 给 80000 个数据，测试一下
* */
public static void testTime() {
// 创建一个 80000个的随机的数组
int array2[] = new int[8000000];
for (int i = 0; i < 8000000; i++) {
array2[i] = (int) (Math.random() * 8000000); // 生成一个[ 0, 8000000] 数
}
// System.out.println(Arrays.toString(array2)); // 不在打印，耗费时间太长
long start = System.currentTimeMillis(); //返回以毫秒为单位的当前时间
System.out.println("long start:" + start);
Date date = new Date(start); // 上面的也可以不要，但是我想测试
System.out.println("date:" + date);
SimpleDateFormat format = new SimpleDateFormat("yyyy-mm-dd HH:mm:ss");
System.out.println("排序前的时间是=" + format.format(date));
int[] temp = new int[array2.length];
mergetSort(array2,0, array2.length-1, temp); // 移位式
System.out.println();
long end = System.currentTimeMillis();
Date date2 = new Date(end); // 上面的也可以不要，但是我想测试
System.out.println("排序后的时间是=" + format.format(date2));
System.out.println("共耗时" + (end - start) + "毫秒");
System.out.println("毫秒转成秒为：" + ((end - start) / 1000) + "秒");
}
/*
* 分 + 合的方法
* */
public static void mergetSort(int[] array, int left, int right, int[] temp) {
if (left < right) {
// 数据校验
int mid = (left + right) / 2; // 中间索引
// 向左递归 分解
mergetSort(array, left, mid, temp);
// 向右递归 分解
mergetSort(array, mid + 1, right, temp);
// 以上为分解
// 以下这一句为合并
merge(array, left, mid, right, temp);
}
}
/*
* 合并的方法
*
* @param array 排序的原始数组
* @param left 左边有序序列的初始索引
* @param mid 中间索引
* @param right 右边索引
* @param temp 做中转的数组
* */
public static void merge(int[] array, int left, int mid, int right, int[] temp) {
// System.out.println("XXXX");
int i = left; // 初始化 i, 左边有序序列的初始索引
int j = mid + 1; // 初始化j, 右边有序序列的初始索引
int t = 0; // 指向 temp 数组的 当前索引。
// (一)
// 先把左右两边（有序）的数据按照规则填充到 temp数组
// 直到 左右两边的有序序列，有一边处理完毕为止
while (i <= mid && j <= right) {
/*
* 如果 左边的有序序列 的当前元素，小于等于右边有序序列的 当前元素
* 既然左边的当前元素，填充到 temp 数组
* 然后 t++, i++
* */
if (array[i] <= array[j]) {
temp[t] = array[i];
t += 1;
i += 1;
} else {
// 如果 右边的有序序列的当前元素 小于 左边有序序列的当前元素，则将右边的当前元素填充到 temp数组，然后 t++, j++
temp[t] = array[j];
t += 1;
j += 1;
}
}
/*
* (二)
* 当代码走到这里，说明 左边 或者 右边 ，已经有一方 有剩余的。
* 把有 剩余数据 的一边的数据 依次全部填充到 temp
* */
// 左边 有序序列还有剩余的元素，就全部填充到 temp
while (i <= mid) {
temp[t] = array[i];
t++;
i++;
}
// 右边 有序序列还有剩余的元素，就全部填充到 temp
while (j <= right) {
temp[t] = array[j];
t++;
j++;
}
/*
* (三)
* 将 temp 数组的元素拷贝到 array
* 注意，并不是每次都拷贝所有
* */
t = 0;
int tempLeft = left;//
// 第一次 合并： tempLeft = 0, right = 1, // tempLeft = 2, right = 3 // tempLeft = 0, right = 3
// 最后一次，tempLeft = 0 right = 7
// System.out.println("tempLeft=" + tempLeft + ",right=" + right);
while (tempLeft <= right) {
array[tempLeft] = temp[t];
t++;
tempLeft++;
}
}
}
3.4 测试结果
