7.5 冒泡排序
7.5.1基本介绍
冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始）,依次比较
相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒。
优化：
因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志flag 判断元素是否进行过交换。从而减少不必要的比较。(这里说的优化，可以在冒泡排
序写好后，在进行)
7.5.2演示冒泡过程的例子(图解)
小结上面的图解过程:
(1) 一共进行数组的大小-1 次大的循环
(2)每一趟排序的次数在逐渐的减少
(3) 如果我们发现在某趟排序中，没有发生一次交换， 可以提前结束冒泡排序。这个就是优化
7.5.3冒泡排序应用实例
我们举一个具体的案例来说明冒泡法。我们将五个无序的数：3, 9, -1, 10, -2 使用冒泡排序法将其排成一个从小
到大的有序数列。
1.代码实现:
package sort;import java.text.SimpleDateFormat;import java.util.Arrays;import java.util.Date;public class BubbleSort {public static void main(String[] args) {int arr[] = {3, 9, -1, 10, 20};//System.out.println("排序前");System.out.println(Arrays.toString(arr));// //为了容量理解，我们把冒泡排序的演变过程，给大家展示// //测试一下冒泡排序的速度O(n^2), 给80000 个数据，测试// //创建要给80000 个的随机的数组// int[] arr = new int[80000];// for (int i = 0; i < 80000; i++) {// arr[i] = (int) (Math.random() * 8000000); //生成一个[0, 8000000) 数// }// Date data1 = new Date();// SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");// String date1Str = simpleDateFormat.format(data1);// System.out.println("排序前的时间是=" + date1Str);//测试冒泡排序bubbleSort(arr);// Date data2 = new Date();// String date2Str = simpleDateFormat.format(data2);// System.out.println("排序后的时间是=" + date2Str);System.out.println("排序后");System.out.println(Arrays.toString(arr));/*//演示过程// 第二趟排序，就是将第二大的数排在倒数第二位int temp ;for (int j = 0; j < arr.length - 1 - 1; j++) {// 如果前面的数比后面的数大，则交换if (arr[j] > arr[j + 1]) {temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}System.out.println("第二趟排序后的数组");System.out.println(Arrays.toString(arr));// 第三趟排序，就是将第三大的数排在倒数第三位for (int j = 0; j < arr.length - 1 - 2; j++) {// 如果前面的数比后面的数大，则交换if (arr[j] > arr[j + 1]) {temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}System.out.println("第三趟排序后的数组");System.out.println(Arrays.toString(arr));// 第四趟排序，就是将第4 大的数排在倒数第4 位for (int j = 0; j < arr.length - 1 - 3; j++) {// 如果前面的数比后面的数大，则交换if (arr[j] > arr[j + 1]) {temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}System.out.println("第四趟排序后的数组");System.out.println(Arrays.toString(arr));*/}// 将前面额冒泡排序算法，封装成一个方法public static void bubbleSort(int[] arr) {// 冒泡排序的时间复杂度O(n^2), 自己写出int temp = 0; // 临时变量boolean flag = false; // 标识变量，表示是否进行过交换for (int i = 0; i < arr.length - 1; i++) {for (int j = 0; j < arr.length - 1 - i; j++) {// 如果前面的数比后面的数大，则交换if (arr[j] > arr[j + 1]) {flag = true;temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}//System.out.println("第" + (i + 1) + "趟排序后的数组");//System.out.println(Arrays.toString(arr));if (!flag) { // 在一趟排序中，一次交换都没有发生过break;} else {flag = false; // 重置flag!!!, 进行下次判断}}}}
2.结果演示
//包装方法前（演示过程）第二趟排序后的数组[3, -1, 9, 10, 20]第三趟排序后的数组[-1, 3, 9, 10, 20]第四趟排序后的数组[-1, 3, 9, 10, 20]Process finished with exit code 0//包装方法后排序前[3, 9, -1, 10, 20]排序后[-1, 3, 9, 10, 20]Process finished with exit code 0
3.测试8w数据排序耗时（11s）
排序前的时间是=2021-04-11 10:18:16排序后的时间是=2021-04-11 10:18:27Process finished with exit code 0
7.6 选择排序
7.6.1基本介绍
选择式排序也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，再依规定交换位置后达到
排序的目的。
7.6.2选择排序思想:
选择排序（select sorting）也是一种简单的排序方法。它的基本思想是：第一次从arr[0]~arr[n-1]中选取最小值，与arr[0]交换，第二次从arr[1]~arr[n-1]中选取最小值，与arr[1]交换，第三次从arr[2]~arr[n-1]中选取最小值，与arr[2]交换，…，第i 次从arr[i-1]~arr[n-1]中选取最小值，与arr[i-1]交换，…, 第n-1 次从arr[n-2]~arr[n-1]中选取最小值，与arr[n-2]交换，总共通过n-1 次，得到一个按排序码从小到大排列的有序序列。
7.6.3选择排序思路分析图:
对一个数组的选择排序再进行讲解
1. 选择排序一共有 数组大小 - 1 轮排序
2. 每1轮排序，又是一个循环, 循环的规则(代码)
2.1先假定当前这个数是最小数
2.2 然后和后面的每个数进行比较，如果发现有比当前数更小的数，就重新确定最小数，并得到下标
2.3 当遍历到数组的最后时，就得到本轮最小数和下标
2.4 交换 [代码中再继续说 ]
7.6.4选择排序应用实例:
有一群牛, 颜值分别是101, 34, 119, 1 请使用选择排序从低到高进行排序[101, 34, 119, 1]
说明: 测试效率的数据 80000，看耗时
1.代码实现
package sort;import java.text.SimpleDateFormat;import java.util.Arrays;import java.util.Date;//选择排序public class SelectSort {public static void main(String[] args) {// int [] arr = {101, 34, 119, 1, -1, 90, 123};//创建要给80000 个的随机的数组， 在我的机器是2-3 秒，比冒泡快.int[] arr = new int[80000];for (int i = 0; i < 80000; i++) {arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数}// System.out.println("排序前");// System.out.println(Arrays.toString(arr));Date data1 = new Date();SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");String date1Str = simpleDateFormat.format(data1);System.out.println("排序前的时间是=" + date1Str);selectSort(arr);Date data2 = new Date();String date2Str = simpleDateFormat.format(data2);System.out.println("排序后的时间是=" + date2Str);// System.out.println("排序后");// System.out.println(Arrays.toString(arr));}//选择排序public static void selectSort(int[] arr) {//在推导的过程，我们发现了规律，因此，可以使用for 来解决//选择排序时间复杂度是O(n^2)for (int i = 0; i < arr.length - 1; i++) {int minIndex = i;int min = arr[i];for (int j = i + 1; j < arr.length; j++) {if (min > arr[j]) { // 说明假定的最小值，并不是最小min = arr[j]; // 重置minminIndex = j; // 重置minIndex}}// 将最小值，放在arr[0], 即交换if (minIndex != i) {arr[minIndex] = arr[i];arr[i] = min;}// System.out.println("第"+(i+1)+"轮后~~");// System.out.println(Arrays.toString(arr));// 1, 34, 119, 101}/*//使用逐步推导的方式来，讲解选择排序//第1 轮//原始的数组： 101, 34, 119, 1//第一轮排序: 1, 34, 119, 101//算法先简单--》做复杂， 就是可以把一个复杂的算法，拆分成简单的问题-》逐步解决//第1 轮int minIndex = 0;int min = arr[0];for (int j = 0 + 1; j < arr.length; j++) {if (min > arr[j]) { //说明假定的最小值，并不是最小min = arr[j]; //重置minminIndex = j; //重置minIndex}}//将最小值，放在arr[0], 即交换if (minIndex != 0) {arr[minIndex] = arr[0];arr[0] = min;}System.out.println("第1 轮后~~");System.out.println(Arrays.toString(arr));// 1, 34, 119, 101//第2 轮minIndex = 1;min = arr[1];for (int j = 1 + 1; j < arr.length; j++) {if (min > arr[j]) { // 说明假定的最小值，并不是最小min = arr[j]; // 重置minminIndex = j; // 重置minIndex}}// 将最小值，放在arr[0], 即交换if (minIndex != 1) {arr[minIndex] = arr[1];arr[1] = min;}System.out.println("第2 轮后~~");System.out.println(Arrays.toString(arr));// 1, 34, 119, 101//第3 轮minIndex = 2;min = arr[2];for (int j = 2 + 1; j < arr.length; j++) {if (min > arr[j]) { // 说明假定的最小值，并不是最小min = arr[j]; // 重置minminIndex = j; // 重置minIndex}}// 将最小值，放在arr[0], 即交换if (minIndex != 2) {arr[minIndex] = arr[2];arr[2] = min;}System.out.println("第3 轮后~~");System.out.println(Arrays.toString(arr));// 1, 34, 101, 119 */}}
2.结果演示
//未用方法前（演示）
排序前
[101, 34, 119, 1, -1, 90, 123]
第1 轮后~~
[-1, 34, 119, 1, 101, 90, 123]
第2 轮后~~
[-1, 1, 119, 34, 101, 90, 123]
第3 轮后~~
[-1, 1, 34, 119, 101, 90, 123]
排序后
[-1, 1, 34, 119, 101, 90, 123]
Process finished with exit code 0
3.耗时测试（2s）
排序前的时间是=2021-04-11 10:57:15
排序后的时间是=2021-04-11 10:57:18
Process finished with exit code 0
7.7 插入排序
7.7.1插入排序法介绍:
插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。
7.7.2插入排序法思想:
插入排序（Insertion Sorting）的基本思想是：把n 个待排序的元素看成为一个有序表和一个无序表，开始时有
序表中只包含一个元素，无序表中包含有n-1 个元素，排序过程中每次从无序表中取出第一个元素，把它的排
序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。
7.7.3插入排序思路图:
7.7.4插入排序法应用实例:
有一群小牛, 考试成绩分别是101, 34, 119, 1 请从小到大排序
1.代码实现：
package sort;
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
public class InsertSort {
public static void main(String[] args) {
// int[] arr = {101, 34, 119, 1, -1, 89};
//创建要给80000 个的随机的数组
int[] arr = new int[80000];
for (int i = 0; i < 80000; i++) {
arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
}
// System.out.println("排序前");
Date data1 = new Date();
SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String date1Str = simpleDateFormat.format(data1);
System.out.println("排序前的时间是=" + date1Str);
insertSort(arr); //调用插入排序算法
Date data2 = new Date();
String date2Str = simpleDateFormat.format(data2);
System.out.println("排序前的时间是=" + date2Str);
// System.out.println(Arrays.toString(arr));
}
//插入排序
public static void insertSort(int[] arr) {
int insertVal = 0;
int insertIndex = 0;
//使用for 循环来把代码简化
for (int i = 1; i < arr.length; i++) {
//定义待插入的数
insertVal = arr[i];
insertIndex = i - 1; // 即arr[1]的前面这个数的下标
// 给insertVal 找到插入的位置
// 说明
// 1. insertIndex >= 0 保证在给insertVal 找插入位置，不越界
// 2. insertVal < arr[insertIndex] 待插入的数，还没有找到插入位置
// 3. 就需要将arr[insertIndex] 后移
while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
arr[insertIndex + 1] = arr[insertIndex];// arr[insertIndex]
insertIndex--;
}
// 当退出while 循环时，说明插入的位置找到, insertIndex + 1
// 举例：理解不了，我们一会debug
//这里我们判断是否需要赋值
if(insertIndex + 1 != i) {
arr[insertIndex + 1] = insertVal;
}
// System.out.println("第"+i+"轮插入");
// System.out.println(Arrays.toString(arr));
}
/*
//使用逐步推导的方式来讲解，便利理解
//第1 轮{101, 34, 119, 1}; => {34, 101, 119, 1}
//{101, 34, 119, 1}; => {101,101,119,1}
//定义待插入的数
int insertVal = arr[1];
int insertIndex = 1 - 1; //即arr[1]的前面这个数的下标
//给insertVal 找到插入的位置
//说明
//1. insertIndex >= 0 保证在给insertVal 找插入位置，不越界
//2. insertVal < arr[insertIndex] 待插入的数，还没有找到插入位置
//3. 就需要将arr[insertIndex] 后移
while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
arr[insertIndex + 1] = arr[insertIndex];// arr[insertIndex]
insertIndex--;
}
//当退出while 循环时，说明插入的位置找到, insertIndex + 1
//举例：理解不了，我们一会debug
arr[insertIndex + 1] = insertVal;
System.out.println("第1 轮插入");
System.out.println(Arrays.toString(arr));
//第2 轮
insertVal = arr[2];
insertIndex = 2 - 1;
while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
arr[insertIndex + 1] = arr[insertIndex];// arr[insertIndex]
insertIndex--;
}
arr[insertIndex + 1] = insertVal;
System.out.println("第2 轮插入");
System.out.println(Arrays.toString(arr));
//第3 轮
insertVal = arr[3];
insertIndex = 3 - 1;
while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
arr[insertIndex + 1] = arr[insertIndex];// arr[insertIndex]
insertIndex--;
}
arr[insertIndex + 1] = insertVal;
System.out.println("第3 轮插入");
System.out.println(Arrays.toString(arr));*/
}
}
2.运行结果
第1 轮插入
[34, 101, 119, 1, -1, 89]
第2 轮插入
[34, 101, 119, 1, -1, 89]
第3 轮插入
[1, 34, 101, 119, -1, 89]
Process finished with exit code 0
3.耗时测试（1s）
排序前的时间是=2021-04-11 11:47:11
排序前的时间是=2021-04-11 11:47:12
Process finished with exit code 0
7.8 希尔排序
7.8.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}
结论: 当需要插入的数是较小的数时，后移的次数明显增多，对效率有影响.
7.8.2希尔排序法介绍
希尔排序是希尔（Donald Shell）于1959 年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入
排序经过改进之后的一个更高效的版本，也称为缩小增量排序。
7.8.3希尔排序法基本思想
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含
的关键词越来越多，当增量减至1 时，整个文件恰被分成一组，算法便终止
7.8.4希尔排序法的示意图
7.8.5希尔排序法应用实例:
有一群小牛, 考试成绩分别是{8,9,1,7,2,3,5,4,6,0} 请从小到大排序. 请分别使用
1) 希尔排序时， 对有序序列在插入时采用交换法, 并测试排序速度.
2) 希尔排序时， 对有序序列在插入时采用移动法, 并测试排序速度
3) 代码实现
package sort;
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
public class ShellSort {
public static void main(String[] args) {
// int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
// shellSort(arr);
// 创建要给80000 个的随机的数组
int[] arr = new int[80000];
for (int i = 0; i < 80000; i++) {
arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
}
System.out.println("排序前");
Date data1 = new Date();
SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String date1Str = simpleDateFormat.format(data1);
System.out.println("排序前的时间是=" + date1Str);
// shellSort(arr); //交换式
shellSort2(arr);//移位方式
Date data2 = new Date();
String date2Str = simpleDateFormat.format(data2);
System.out.println("排序前的时间是=" + date2Str);
//System.out.println(Arrays.toString(arr));
}
// 使用逐步推导的方式来编写希尔排序
// 希尔排序时， 对有序序列在插入时采用交换法,
// 思路(算法) ===> 代码
public static void shellSort(int[] arr) {
int temp = 0;
int count = 0;
// 根据前面的逐步分析，使用循环处理
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
for (int i = gap; i < arr.length; i++) {
// 遍历各组中所有的元素(共gap 组，每组有个元素), 步长gap
for (int j = i - gap; j >= 0; j -= gap) {
// 如果当前元素大于加上步长后的那个元素，说明交换
if (arr[j] > arr[j + gap]) {
temp = arr[j];
arr[j] = arr[j + gap];
arr[j + gap] = temp;
}
}
}
// System.out.println("希尔排序第" + (++count) + "轮=" + Arrays.toString(arr));
}
/*
// 希尔排序的第1 轮排序
// 因为第1 轮排序，是将10 个数据分成了5 组
for(
int i = 5;
i<arr.length;i++)
{
// 遍历各组中所有的元素(共5 组，每组有2 个元素), 步长5
for (int j = i - 5; j >= 0; j -= 5) {
// 如果当前元素大于加上步长后的那个元素，说明交换
if (arr[j] > arr[j + 5]) {
temp = arr[j];
arr[j] = arr[j + 5];
arr[j + 5] = temp;
}
}
}
System.out.println("希尔排序1 轮后="+Arrays.toString(arr));//
// 希尔排序的第2 轮排序
// 因为第2 轮排序，是将10 个数据分成了5/2 = 2 组
for (
int i = 2;
i < arr.length; i++) {
// 遍历各组中所有的元素(共5 组，每组有2 个元素), 步长5
for (int j = i - 2; j >= 0; j -= 2) {
// 如果当前元素大于加上步长后的那个元素，说明交换
if (arr[j] > arr[j + 2]) {
temp = arr[j];
arr[j] = arr[j + 2];
arr[j + 2] = temp;
}
}
}
System.out.println("希尔排序2 轮后=" + Arrays.toString(arr));//
// 希尔排序的第3 轮排序
// 因为第3 轮排序，是将10 个数据分成了2/2 = 1 组
for (
int i = 1;
i < arr.length; i++) {
// 遍历各组中所有的元素(共5 组，每组有2 个元素), 步长5
for (int j = i - 1; j >= 0; j -= 1) {
// 如果当前元素大于加上步长后的那个元素，说明交换
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
System.out.println("希尔排序3 轮后=" + Arrays.toString(arr));//
*/
}
//对交换式的希尔排序进行优化->移位法
public static void shellSort2(int[] arr) {
// 增量gap, 并逐步的缩小增量
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
// 从第gap 个元素，逐个对其所在的组进行直接插入排序
for (int i = gap; i < arr.length; i++) {
int j = i;
int temp = arr[j];
if (arr[j] < arr[j - gap]) {
while (j - gap >= 0 && temp < arr[j - gap]) {
//移动
arr[j] = arr[j-gap];
j -= gap;
}
//当退出while 后，就给temp 找到插入的位置
arr[j] = temp;
}
}
}
}
}
4) 结果演示
希尔排序1 轮后=[3, 5, 1, 6, 0, 8, 9, 4, 7, 2]
希尔排序2 轮后=[0, 2, 1, 4, 3, 5, 7, 6, 9, 8]
希尔排序3 轮后=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Process finished with exit code 0
5) 耗时测试（<1s）
//希尔交换排序效率：27s
排序前的时间是=2021-04-11 13:29:25
排序前的时间是=2021-04-11 13:29:32
Process finished with exit code 0
//希尔位移排序效率：<1s
排序前的时间是=2021-04-11 13:35:58
排序前的时间是=2021-04-11 13:35:58
Process finished with exit code 0
7.9 快速排序
7.9.1快速排序法介绍:
快速排序（Quicksort）是对冒泡排序的一种改进。基本思想是：通过一趟排序将要排序的数据分割成独立的两
部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排
序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
7.9.2快速排序法示意图:
7.9.3快速排序法应用实例:
要求: 对[-9,78,0,23,-567,70] 进行从小到大的排序，要求使用快速排序法。
说明[验证分析]:
1) 如果取消左右递归，结果是-9 -567 0 23 78 70
2) 如果取消右递归,结果是-567 -9 0 23 78 70
3) 如果取消左递归,结果是-9 -567 0 23 70 78
4) 代码实现
package sort;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Date;
public class QuickSort {
public static void main(String[] args) {
//int[] arr = {-9,78,0,23,-567,70, -1,900, 4561};
//测试快排的执行速度
// 创建要给80000 个的随机的数组
int[] arr = new int[8000000];
for (int i = 0; i < 8000000; i++) {
arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
}
System.out.println("排序前");
Date data1 = new Date();
SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String date1Str = simpleDateFormat.format(data1);
System.out.println("排序前的时间是=" + date1Str);
quickSort(arr, 0, arr.length-1);
Date data2 = new Date();
String date2Str = simpleDateFormat.format(data2);
System.out.println("排序前的时间是=" + date2Str);
//System.out.println("arr=" + Arrays.toString(arr));
}
public static void quickSort(int[] arr,int left, int right) {
int l = left; //左下标
int r = right; //右下标
//pivot 中轴值
int pivot = arr[(left + right) / 2];
int temp = 0; //临时变量，作为交换时使用
//while 循环的目的是让比pivot 值小放到左边
//比pivot 值大放到右边
while( l < r) {
//在pivot 的左边一直找,找到大于等于pivot 值,才退出
while( arr[l] < pivot) {
l += 1;
}
//在pivot 的右边一直找,找到小于等于pivot 值,才退出
while(arr[r] > pivot) {
r -= 1;
}
//如果l >= r 说明pivot 的左右两的值，已经按照左边全部是
//小于等于pivot 值，右边全部是大于等于pivot 值
if( l >= r) {
break;
}
//交换
temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
//如果交换完后，发现这个arr[l] == pivot 值相等r--， 前移
if(arr[l] == pivot) {
r -= 1;
}
//如果交换完后，发现这个arr[r] == pivot 值相等l++， 后移
if(arr[r] == pivot) {
l += 1;
}
}
// 如果l == r, 必须l++, r--, 否则为出现栈溢出
if (l == r) {
l += 1;
r -= 1;
}
//向左递归
if(left < r) {
quickSort(arr, left, r);
}
//向右递归
if(right > l) {
quickSort(arr, l, right);
}
}
}
arr=[-9, 78, 0, 23, -567, 70, -1, 900, 4561]
Process finished with exit code 0
5) 测试80w（1s）
排序前的时间是=2021-04-11 23:04:12
排序前的时间是=2021-04-11 23:04:13
Process finished with exit code 0
7.10 归并排序
7.10.1 归并排序介绍:
归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之)。
7.10.2 归并排序思想示意图1-基本思想:
7.10.3 归并排序思想示意图2-合并相邻有序子序列:
再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将
[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤
7.10.4 归并排序的应用实例:
给你一个数组, val arr = Array(8, 4, 5, 7, 1, 3, 6, 2 ), 请使用归并排序完成排序。
1.代码演示
package sort;
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
public class MergetSort {
public static void main(String[] args) {
//int arr[] = { 8, 4, 5, 7, 1, 3, 6, 2 }; //
//测试快排的执行速度
// 创建要给80000 个的随机的数组
int[] arr = new int[8000000];
for (int i = 0; i < 8000000; i++) {
arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
}
System.out.println("排序前");
Date data1 = new Date();
SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String date1Str = simpleDateFormat.format(data1);
System.out.println("排序前的时间是=" + date1Str);
int temp[] = new int[arr.length]; //归并排序需要一个额外空间
mergeSort(arr, 0, arr.length - 1, temp);
Date data2 = new Date();
String date2Str = simpleDateFormat.format(data2);
System.out.println("排序前的时间是=" + date2Str);
//System.out.println("归并排序后=" + Arrays.toString(arr));
}
//分+合方法
public static void mergeSort(int[] arr, int left, int right, int[] temp) {
if(left < right) {
int mid = (left + right) / 2; //中间索引
//向左递归进行分解
mergeSort(arr, left, mid, temp);
//向右递归进行分解
mergeSort(arr, mid + 1, right, temp);
//合并
merge(arr, left, mid, right, temp);
}
}
//合并的方法
/**
*
尚硅谷Java 数据结构和算法
更多Java –大数据–前端–python 人工智能-区块链资料下载，可访问百度：尚硅谷官网第156页
* @param arr 排序的原始数组
* @param left 左边有序序列的初始索引
* @param mid 中间索引
* @param right 右边索引
* @param temp 做中转的数组
*/
public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
int i = left; // 初始化i, 左边有序序列的初始索引
int j = mid + 1; //初始化j, 右边有序序列的初始索引
int t = 0; // 指向temp 数组的当前索引
//(一)
//先把左右两边(有序)的数据按照规则填充到temp 数组
//直到左右两边的有序序列，有一边处理完毕为止
while (i <= mid && j <= right) {//继续
//如果左边的有序序列的当前元素，小于等于右边有序序列的当前元素
//即将左边的当前元素，填充到temp 数组
//然后t++, i++
if(arr[i] <= arr[j]) {
temp[t] = arr[i];
t += 1;
i += 1;
} else { //反之,将右边有序序列的当前元素，填充到temp 数组
temp[t] = arr[j];
t += 1;
j += 1;
}
}
//(二)
//把有剩余数据的一边的数据依次全部填充到temp
while( i <= mid) { //左边的有序序列还有剩余的元素，就全部填充到temp
temp[t] = arr[i];
t += 1;
i += 1;
}
while( j <= right) { //右边的有序序列还有剩余的元素，就全部填充到temp
temp[t] = arr[j];
t += 1;
j += 1;
}
//(三)
//将temp 数组的元素拷贝到arr
//注意，并不是每次都拷贝所有
t = 0;
int tempLeft = left; //
//第一次合并tempLeft = 0 , right = 1 // tempLeft = 2 right = 3 // tL=0 ri=3
//最后一次tempLeft = 0 right = 7
while(tempLeft <= right) {
arr[tempLeft] = temp[t];
t += 1;
tempLeft += 1;
}
}
}
2.运行结果
归并排序后={1，2，3，4，5，6，7，8}
3.效率测试（800w 1s）
排序前的时间是=2021-04-12 16:00:36
排序前的时间是=2021-04-12 16:00:37
Process finished with exit code 0
7.11 基数排序
7.11.1 基数排序(桶排序)介绍:
1) 基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾
名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用
2) 基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法
3) 基数排序(Radix Sort)是桶排序的扩展
4) 基数排序是1887 年赫尔曼·何乐礼发明的。它是这样实现的：将整数按位数切割成不同的数字，然后按每个
位数分别比较。
7.11.2 基数排序基本思想
1) 将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。
这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
2) 这样说明，比较难理解，下面我们看一个图文解释，理解基数排序的步骤
7.11.3 基数排序图文说明
将数组{53, 3, 542, 748, 14, 214} 使用基数排序, 进行升序排序
7.11.4 基数排序代码实现
要求：将数组{53, 3, 542, 748, 14, 214} 使用基数排序, 进行升序排序
1) 思路分析：
2) 代码实现：
第0轮的结果[542, 53, 3, 14, 214, 748]
第1轮的结果[3, 14, 214, 542, 748, 53]
第2轮的结果[3, 14, 53, 214, 542, 748]
第3轮的结果[3, 14, 53, 214, 542, 748]
Process finished with exit code 0
3）效率测试（800w <1s）
排序前的时间是=2021-04-12 22:05:29
排序前的时间是=2021-04-12 22:05:29
Process finished with exit code 0
但8000w数据需要占3.3.G内存，会报错。
7.12 常用排序算法总结和对比
7.12.1 一张排序算法的比较图
7.12.2 相关术语解释：
1) 稳定：如果a 原本在b 前面，而a=b，排序之后a 仍然在b 的前面；
2) 不稳定：如果a 原本在b 的前面，而a=b，排序之后a 可能会出现在b 的后面；
3) 内排序：所有排序操作都在内存中完成；
4) 外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
5) 时间复杂度： 一个算法执行所耗费的时间。
6) 空间复杂度：运行完一个程序所需内存的大小。
7) n: 数据规模
8) k: “桶”的个数
9) In-place: 不占用额外内存
10) Out-place: 占用额外内存
7.12.3 各排序算法简记
1.冒泡排序
在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一轮比较中：首先比较第1个和第2个数，将小数放前，大数放后；然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。重复第一轮的步骤，直至全部排序完成。
2.选择排序
在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。
3.插入排序 InsertSort
插入排序（Insertion Sorting）的基本思想是：把n 个待排序的元素看成为一个有序表和一个无序表，开始时有
序表中只包含一个元素，无序表中包含有n-1 个元素，排序过程中每次从无序表中取出第一个元素，把它的排
序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。
4.希尔排序 ShellSort
希尔排序又叫“缩小增量排序”，先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序，然后取第二个增量d2。其是插入排序改良的算法，希尔排序步长从大到小调整，第一次循环后面元素逐个和前面元素按间隔步长进行比较并交换，直至步长为1，步长选择是关键。
5.归并排序
归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。归并排序中第二步，对两个有序数组排序法则非常简单，同时对两个数组的第一个位置比较大小，将小的放入一个空数组，然后被放入空数组的那个位置的指针往后移一个，然后继续和另一个数组的上一个位置进行比较，以此类推。直到最后任何一个数组先出栈完，就将另外一个数组里的所有元素追加到新数组后面。
归并排序和快速排序有那么点异曲同工之妙，快速排序：是先把数组粗略的排序成两个子数组，然后递归再粗略分两个子数组，直到子数组里面只有一个元素，那么就自然排好序了，可以总结为先排序再递归；归并排序：先什么都不管，把数组分为两个子数组，一直递归把数组划分为两个子数组，直到数组里只有一个元素，这时候才开始排序，让两个数组间排好序，依次按照递归的返回来把两个数组进行排好序，到最后就可以把整个数组排好序。
6.快速排序
选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一轮扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分，直到各区间只有一个数。
7.基数排序
- 时间复杂度：给定n个d位数(即d个关键码，关键码的取值范围为r)，基数排序需要比较元素的每一位，则复杂度为O(d(n+r))，其中一轮循环分配时间复杂度为O(n)，一轮循环收集时间复杂度为O(r)，共需要d次循环来进行分配收集，即时间复杂度为O(d(n+r))
- 基本思想：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。
简单分类：
1.插入排序：直接插入排序、二分插入排序、希尔排序
2.选择排序：直接选择排序、推排序
3.交换排序：冒泡排序、快速排序
4.归并排序
5.基数排序
若有收获，就点个赞吧
0 人点赞
