前言
一、冒泡排序
1.1 基本介绍
冒泡排序(Bubble Sorting)的基本思想是:通过对待排序序列从前向后(从下标较小的元素开始), 依次比较相邻元素的值,若发现逆序则交换
,使值较大的元素逐渐从前移向后部,就象水底下的气泡一样逐渐向上冒。
因为排序的过程中,各元素不断接近自己的位置,如果一趟比较下来没有进行过交换,就说明序列有序
,因此要在排序过程中设置一个标志flag判断元素是否进行过交换。从而减少不必要的比较。(这里说的优化,可以在冒泡排序写好后,在进行)
1.2 演示冒泡过程的例子(图解)
小节下面的冒泡排序的图解过程:
- 一共进行
【数组的大小-1 】
次 大的循环 - 每一趟排序的次数在逐渐的减少
- 如果我们发现在某趟排序中,没有发生一次交换, 可以提前结束冒泡排序。这个就是优化
1.3 代码实现
时间复杂度:O(n^2)
实现对一位数组{3, 9, -1, 10, -2}的排序
代码实现是分为三部分学习的
- 对每一步的循环进行分析、推导,其方法为
deductionBubbleSort(int[] array)
- 对第一步的推导找出规律,合成两个 for 循环。其方法为
bubbleSort(int[] array)
- 测试 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.2 然后和后面的每个数进行比较,如果发现有比当前数更小的数,就重新确定最小数,并得到下标
2.3 当遍历到数组的最后时,就得到本轮最小数和下标
2.4 交换 [代码中再继续说 ]
2.3 代码实现
时间复杂度:O(n^2)
实现对一位数组{101, 34, 119, 1}的排序
代码实现是分为三部分学习的
- 对每一步的循环进行分析、推导,其方法为
deductionSelectSort(int[] array)
2.1 首先定义两个变量,minIndex、 min,分别表示 最小值下标、最小值
2.2 假定第一个数据为最小值,然后拿着这个数据和其他数据比较(使用遍历)
2.3 找到最小值后,将其与数组的第一个值进行互换(默认排序是从小到大) - 对第一步的推导找出规律,合成两个 for 循环。其方法为
selectSort(int[] array)
- 测试 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}的排序
代码实现是分为三部分学习的
- 对每一步的循环进行分析、推导,其方法为
deductionSelectSort(int[] array)
2.1 先定义两个变量:insertValue、insertIndex,分别代表 待插入的值(从数组第二个值开始)、待插入的下标
2.2 先保存数组第二个值,进行循环,每次循环判断第二值(当前值)与第一个值(前一个值)的大小,若小则将第一个值(前一个值)后移,
2.3 进行循环,循环一次,便将 保存的当前值插入到所应该在的前面的位置。 - 对第一步的推导找出规律,合成两个 for 循环。其方法为
selectSort(int[] array)
- 测试 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;
}
}