11、数据结构与算法 - 实战：冒泡排序、选择排序、插入排序
前言
一、冒泡排序
1.1 基本介绍
冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始）, 依次比较相邻元素的值，若发现逆序则交换 ，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒。
因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序 ，因此要在排序过程中设置一个标志flag判断元素是否进行过交换。从而减少不必要的比较。(这里说的优化，可以在冒泡排序写好后，在进行)
1.2 演示冒泡过程的例子(图解)
小节下面的冒泡排序的图解过程：
1、 一共进行**【数组的大小-1】次大的循环**；
2、 每一趟排序的次数在逐渐的减少；
3、 如果我们发现在某趟排序中，没有发生一次交换，可以提前结束冒泡排序这个就是优化；
1.3 代码实现
- 时间复杂度：O(n^2)
- 实现对一位数组{3, 9, -1, 10, -2}的排序
- 代码实现是分为三部分学习的
1、 对每一步的循环进行分析、推导，其方法为deductionBubbleSort(int[]array)；
2、 对第一步的推导找出规律，合成两个for循环其方法为bubbleSort(int[]array)；
3、 测试80000个数据排序所需要的时间其方法为testTime()方法，26S左右；
package com.feng.ch09_sort;
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
/*
* 冒泡排序
* 时间复杂度为 O(n^2)
* 分为三步：
* 1、每一步进行推导。 deductionBubbleSort(int[] array)方法
* 2、找到规律，合成两个for循环。 bubbleSort(int[] array)方法，并进行优化：比较后没有交换的不进行循环一趟
* 3、测试 80000 个数据排序所需要的时间。 testTime()方法 26S 左右
* */
public class S1_BubbleSort {
public static void main(String[] args) {
int[] array = {
3, 9, -1, 10, -2};
System.out.println("排序前：");
System.out.println(Arrays.toString(array));
System.out.println();
System.out.println("排序后：");
// deductionBubbleSort(array); // 推导的方法。
int[] ints = bubbleSort(array); // 推导后的方法
System.out.println(Arrays.toString(ints));
// 测试 80000 个数据排序 所用的时间
System.out.println();
System.out.println("测试 80000 个数据 采用冒泡排序 所用的时间:");
testTime();
}
/*
* 测试一下 冒泡排序的速度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));
bubbleSort(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[] bubbleSort(int[] array) {
int temporary = 0; // 临时变量
boolean flag = false;
for (int i = 0; i < array.length - 1; i++) {
// 总共为 4 趟 大遍历。
for (int j = 0; j < array.length - 1 - i; j++) {
// 如果前面的数比后面的数大，则交换
if (array[j] > array[j + 1]) {
flag = true;
temporary = array[j];
array[j] = array[j + 1];
array[j + 1] = temporary;
}
}
// System.out.println("第" + (i + 1) + "躺排序后的数组");
// System.out.println(Arrays.toString(array));
if (!flag) {
// 在一趟排序中，一次交换都没有发生过
break;
} else {
flag = false; // 重置flag!!!, 进行下次判断
}
}
return array;
}
/*
* 推导的方法
* */
public static int[] deductionBubbleSort(int[] array) {
/*
* 为了容易理解，把冒泡排序的演变过程展示一下：
* */
//1、第一趟排序，就是将最大的数排在最后
int temporary = 0; // 临时变量
for (int i = 0; i < array.length - 1 - 0; i++) {
// 总共为 4次 大循环遍历
// 如果前面的数比后面的数大，则交换
if (array[i] > array[i + 1]) {
temporary = array[i];
array[i] = array[i + 1];
array[i + 1] = temporary;
}
}
System.out.println("每步演练的过程：：");
System.out.println("第一趟排序后的数组：");
System.out.println(Arrays.toString(array));
// 第二趟排序，就在将第二大的数排在倒数第二位
for (int i = 0; i < array.length - 1 - 1; i++) {
// 总共为 4次 大循环遍历
// 如果前面的数比后面的数大，则交换
if (array[i] > array[i + 1]) {
temporary = array[i];
array[i] = array[i + 1];
array[i + 1] = temporary;
}
}
System.out.println("第二趟排序后的数组：");
System.out.println(Arrays.toString(array));
// 第三趟排序，就在将第二大的数排在倒数第三位
for (int i = 0; i < array.length - 1 - 2; i++) {
// 总共为 4次 大循环遍历
// 如果前面的数比后面的数大，则交换
if (array[i] > array[i + 1]) {
temporary = array[i];
array[i] = array[i + 1];
array[i + 1] = temporary;
}
}
System.out.println("第三趟排序后的数组：");
System.out.println(Arrays.toString(array));
// 第四趟排序，就在将第二大的数排在倒数第四位
for (int i = 0; i < array.length - 1 - 3; i++) {
// 总共为 4次 大循环遍历
// 如果前面的数比后面的数大，则交换
if (array[i] > array[i + 1]) {
temporary = array[i];
array[i] = array[i + 1];
array[i + 1] = temporary;
}
}
System.out.println("第四趟排序后的数组：");
System.out.println(Arrays.toString(array));
return array;
}
}
1.4 测试结果
二、选择排序
2.1 基本介绍
选择式排序也属于 内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，再依规定交换位置后达到排序的目的。
2.2 思路分析
2.2.1 选择排序思想
选择排序（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次，得到一个按排序码从小到大排列的有序序列。
2.2.2 思路分析图
对一个数组的选择排序再进行讲解
对图解的说明：
说明：
1、 选择排序一共有**【数组大小-1】轮排序；
2、 每1轮排序，又是一个循环,循环的规则(代码)；
2、 1先假定**当前这个数是最小数；
2、 2然后和后面的每个数进行比较，如果发现有比当前数更小的数，就重新确定最小数，并得到下标；
2、 3当遍历到数组的最后时，就得到本轮最小数和下标；
2、 4交换[代码中再继续说]；
2.3 代码实现
- 时间复杂度：O(n^2)
- 实现对一位数组{101, 34, 119, 1}的排序
- 代码实现是分为三部分学习的
1、 对每一步的循环进行分析、推导，其方法为deductionSelectSort(int[]array)；
2、 1首先定义两个变量，minIndex、min，分别表示最小值下标、最小值；
2、 2假定第一个数据为最小值，然后拿着这个数据和其他数据比较（使用遍历）；
2、 3找到最小值后，将其与数组的第一个值进行互换（默认排序是从小到大）；
2、 对第一步的推导找出规律，合成两个for循环其方法为selectSort(int[]array)；
3、 测试80000个数据排序所需要的时间其方法为testTime()方法，5S左右，比冒泡快；
package com.feng.ch09_sort;
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
/*
* 选择排序
* 时间复杂度： O(n^2)
* 分为三步：
* 1、每一步进行推导。 deductionSelectSort(int[] array)方法
* 1.1 首先定义两个变量，minIndex、 min，分别表示 最小值下标、最小值
* 2.1 假定第一个数据为最小值，然后拿着这个数据和其他数据比较（使用遍历）
* 1.2 找到最小值后，将其与数组的第一个值进行互换（默认排序是从小到大）
* 2、找到规律，合成两个for循环。 selectSort(int[] array)方法，并进行优化：
* 3、测试 80000 个数据排序所需要的时间。 testTime()方法 5S 左右， 比冒泡快
* */
public class S2_SelectSort {
public static void main(String[] args) {
int array[] = new int[]{
101, 34, 119, 1};
System.out.println("排序前：");
System.out.println(Arrays.toString(array));
System.out.println();
System.out.println("排序后：");
// deductionSelectSort(array); // 推导 的过程
int[] ints = selectSort(array); // 推导后的方法
System.out.println(Arrays.toString(ints));
// 测试 80000 个数据排序 所用的时间
System.out.println();
System.out.println("测试 80000 个数据 采用选择排序 所用的时间:");
testTime();
}
/*
* 测试一下 冒泡排序的速度O(n^2), 给 80000 个数据，测试一下
* */
public static void testTime() {
// 创建一个 80000个的随机的数组
System.out.println();
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));
selectSort(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[] selectSort(int[] array) {
/*
* 在 deductionSelectSort()方法 推导的过程，发现了规律，因此，可以使用for循环解决。
* 4个数据， 每次循环比较，找到最小值，放到最前面。共需要 3 次。 而每次找的时候 需要比较循环 3 次。正好为 【数据的大小-1】
* */
for (int i = 0; i < array.length - 1; i++) {
int minIndex = i;
int min = array[i];
for (int j = i + 1; j < array.length; j++) {
if (min > array[j]) {
// 说明假定的最小值，并不是最小
minIndex = j; // 重置 min
min = array[j]; // 重置 minIndex
}
}
// 将最小值，放在 array[i], 即交换: 交换时 做一个判断，如果 比较后，不需要赋值，那么下面两行不在执行，否则就重复了
if (minIndex != i) {
array[minIndex] = array[i];
array[i] = min;
}
// System.out.println("第一轮后：");
// System.out.println(Arrays.toString(array));
}
return array;
}
/*
* 推导的方法
* */
public static void deductionSelectSort(int[] array) {
/*
* 使用逐步推导的方式来，讲解选择排序
* 第1轮
* 原始的数组；101, 34, 119, 1
* 第一轮排序：[1, 34, 119, 101]
* 算法 先简单--》做复杂，就是可以把一个复杂的算法，拆分成简单的问题-》逐步解决
* */
// 第一轮排序后：
int minIndex = 0;
int min = array[0];
for (int i = 1; i < array.length; i++) {
if (min > array[i]) {
// 说明假定的最小值，并不是最小
minIndex = i; // 重置 min
min = array[i]; // 重置 minIndex
}
}
// 将最小值，放在 array[0], 即交换: 交换时 做一个判断，如果 比较后，不需要赋值，那么下面两行不在执行，否则就重复了
if (minIndex != 0) {
array[minIndex] = array[0];
array[0] = min;
}
System.out.println("第一轮后：");
System.out.println(Arrays.toString(array));
// 第二轮排序后：
minIndex = 1;
min = array[1];
for (int i = 1 + 1; i < array.length; i++) {
if (min > array[i]) {
// 说明假定的最小值，并不是最小
minIndex = i; // 重置 min
min = array[i]; // 重置 minIndex
}
}
// 将最小值，放在 array[0], 即交换: 交换时 做一个判断，如果 比较后，不需要赋值，那么下面两行不在执行，否则就重复了
if (minIndex != 1) {
array[minIndex] = array[1];
array[1] = min;
}
System.out.println("第二轮后：");
System.out.println(Arrays.toString(array));
// 第三轮排序后：
minIndex = 2;
min = array[2];
for (int i = 2 + 1; i < array.length; i++) {
if (min > array[i]) {
// 说明假定的最小值，并不是最小
minIndex = i; // 重置 min
min = array[i]; // 重置 minIndex
}
}
// 将最小值，放在 array[0], 即交换: 交换时 做一个判断，如果 比较后，不需要赋值，那么下面两行不在执行，否则就重复了
array[minIndex] = array[2];
array[2] = min;
System.out.println("第三轮后：");
System.out.println(Arrays.toString(array));
}
}
2.4 测试结果
三、插入排序
3.1 基本介绍
插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。
3.2 思路分析
3.2.1 插入排序思想
插入排序（Insertion Sorting）的基本思想是：
把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。
3.2.2 插入排序思路图
3.3 代码实现
- 时间复杂度：O(n^2)
- 实现对一位数组{101, 34, 20, 1}的排序
- 代码实现是分为三部分学习的
1、 对每一步的循环进行分析、推导，其方法为deductionSelectSort(int[]array)；
2、 1先定义两个变量：insertValue、insertIndex，分别代表待插入的值（从数组第二个值开始）、待插入的下标；
2、 2先保存数组第二个值，进行循环，每次循环判断第二值（当前值）与第一个值（前一个值）的大小，若小则将第一个值（前一个值）后移，；
2、 3进行循环，循环一次，便将保存的当前值插入到所应该在的前面的位置；
2、 对第一步的推导找出规律，合成两个for循环其方法为selectSort(int[]array)；
3、 测试80000个数据排序所需要的时间其方法为testTime()方法，5S左右，比冒泡快；
package com.feng.ch09_sort;
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
/*
* 插入排序
* 时间复杂度： O(n^2)
* 分为三步：
* 1、每一步进行推导。 deductionInsertSort(int[] array)方法
* 1.1 先定义两个变量：insertValue、insertIndex，分别代表 待插入的值（从数组第二个值开始）、待插入的下标
* 1.2 先保存数组第二个值，进行循环，每次循环判断第二值（当前值）与第一个值（前一个值）的大小，若小则将第一个值（前一个值）后移，
* 1.3 进行循环，循环一次，便将 保存的当前值插入到所应该在的前面的位置。
* 2、找到规律，合成两个for循环。 insertSort(int[] array)方法，并进行优化，优化 重点，二行代码
* 3、测试 80000 个数据排序所需要的时间。 testTime()方法 1S 左右， 比选择、冒泡快
* */
public class S3_InsertSort {
public static void main(String[] args) {
int[] array = {
101, 34, 20, 1};
System.out.println("原始数组：");
System.out.println(Arrays.toString(array));
System.out.println();
deductionInsertSort(array);
// int[] ints = insertSort(array);
System.out.println("排序后：");
// System.out.println(Arrays.toString(ints));
// 测试 80000 个数据排序 所用的时间
System.out.println();
System.out.println("测试 80000 个数据 采用插入排序 所用的时间:");
//testTime();
}
/*
* 测试一下 冒泡排序的速度O(n^2), 给 80000 个数据，测试一下
* */
public static void testTime() {
// 创建一个 80000个的随机的数组
System.out.println();
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));
insertSort(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[] insertSort(int[] array) {
int insertValue = 0;
int insertIndex = 0;
for (int i = 1; i < array.length; i++) {
// 定义 待插入 的数
insertValue = array[i]; // 保存 第二个数
insertIndex = i - 1; // 保存要插入的位置
/*
* 给 insertValue 找到插入的位置
* 说明
* 1、insertIndex >= 0 保证再给 insertValue 找插入位置，不越界
* 2、insertValue < array[insertIndex] 待插入的数，还没有找到插入位置
* 3、就需要 array[insertIndex] 后移
* */
while (insertIndex >= 0 && insertValue < array[insertIndex]) {
array[insertIndex + 1] = array[insertIndex];
insertIndex--;
}
// 当退出 while 循环时，说明插入的位置找到，insertIndex +1；
// 举例：理解不了，debug 可以帮助理解
// 这里我们判断是否需要赋值
if (insertIndex + 1 != i) {
// insertIndex+1 == i ，就不需要进行赋值了，因为这时是正好的排序
array[insertIndex + 1] = insertValue;
}
}
return array;
}
/*
* 推导插入排序
* */
public static int[] deductionInsertSort(int[] array) {
// 使用逐步推导的方式来讲解，便于理解
// 第一轮{101, 34, 119, 1} =》 {34, 101 119, 1}
// 定义 待插入 的数、插入的位置
int insertValue = array[1]; // 保存 第二个数
int insertIndex = 1 - 1; // 保存要插入的位置
/*
* 给 insertValue 找到插入的位置
* 说明
* 1、insertIndex >= 0 保证再给 insertValue 找插入位置，不越界
* 2、insertValue < array[insertIndex] 待插入的数，还没有找到插入位置
* 3、就需要 array[insertIndex] 后移
* */
while (insertIndex >= 0 && insertValue < array[insertIndex]) {
array[insertIndex + 1] = array[insertIndex];
insertIndex--;
}
// 当退出 while 循环时，说明插入的位置找到，insertIndex +1；
// 举例：理解不了，debug 可以帮助理解
array[insertIndex + 1] = insertValue;
System.out.println("第一轮插入");
System.out.println(Arrays.toString(array));
// 第 2 轮
insertValue = array[2];
insertIndex = 2 - 1;
while (insertIndex >= 0 && insertValue < array[insertIndex]) {
array[insertIndex + 1] = array[insertIndex];
insertIndex--;
}
array[insertIndex + 1] = insertValue;
System.out.println("第二轮插入");
System.out.println(Arrays.toString(array));
// 第 3 轮
insertValue = array[3];
insertIndex = 3 - 1;
while (insertIndex >= 0 && insertValue < array[insertIndex]) {
array[insertIndex + 1] = array[insertIndex];
insertIndex--;
}
array[insertIndex + 1] = insertValue;
System.out.println("第三轮插入");
System.out.println(Arrays.toString(array));
return array;
}
}
3.4 测试结果
