B站学习传送门–>尚硅谷Java数据结构与java算法（Java数据结构与算法）

---

写在前面
数组结构可视化在线网站地址 ===>数据结构可视化在线

排序算法: 把一组数据，依指定顺序进行排列的过程.

1.时间复杂度概述

时间频度

时间频度(T(n)) 算法中语句的执行次数

案例
时间频度为 (n+1);
这里的n就是100;
加1是因为最后在循环时还要再判断一次;

public class Demo01 {public static void main(String[] args) {int total = 0;int end = 100;for (int i = 1; i <= end; i++) {total +=i;}System.out.println(total);//5050}
}

但是若直接简化写为;
时间频度就变成 1 ;因为仅执行一次

public class Demo01 {public static void main(String[] args) {int total = 0;int end = 100;total =(end +1 )* end/2;System.out.println(total);//5050}
}

实际上,常数项可以忽略

低阶的次数项也可以忽略

在同等次方的条件下,和次方项前面的系数有关系;去掉系数后;这个就接近了

时间复杂度

在计算机科学中，时间复杂性，又称时间复杂度，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。
一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f (n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

时间频度不同,时间复杂度可能相同
例: T(n) = n² + 6n+2 与 T(n) = 2n² + 5n+2
时间复杂度都可写为 O(n²)

Ο(1)＜Ο(log₂n)＜Ο(n)＜Ο(nlog₂n)＜Ο(n²)＜Ο(n³)＜ Ο(n^k) ＜Ο(2ⁿ)
时间复杂度增大,效率变低

常数阶 Ο(1):
只要里面没有循环之类的复杂运算,代码再多也都是O(1)常数阶;
不会因为某个变量的增加而增加消耗的时间

对数阶: Ο(log₂n)
案例:比如说要计算下面这个循环次数;
在while循环内;每次都给 i *2 ;条件是i<1024;
1024 = 2^10; 即 n = 2^10; 那么对应的就是 log₂n = 10; 执行的次数为10次;
即时间复杂度为对数阶O(log₂n);
当然,这个根据实际情况会发生改变; 若 在循环中变为 i = i * 5 ;那么时间复杂度也就是O(log5n)

public class Demo02 {public static void main(String[] args) {int i = 1;int n =1024;//num:用来计数int num = 0;while (i<n){i = i * 2 ;num++;}System.out.println("执行次数->"+num); //执行次数->10}
}

线性阶:O(n)
单层循环的话,按照循环的规模来决定; 时间复杂度就是O(n)
案例;它的执行次数为 T(n) = n +1 ;
忽略掉常数项 ; 时间复杂度其实就是O(n);
在本案例中循环的规模n=10;那么它时间复杂度为O(10);
当n变为20时,它也就是O(20);总的来说,时间复杂度就是线性阶的O(n)

public class Demo03 {public static void main(String[] args) {int w =0;int num = 0;int n =10;for (int i = 0; i <= n ; i++) {w = num;num ++;}System.out.println(w);  // 10 System.out.println("执行次数->"+num);//执行次数->11}
}

线性对数阶Ο(nlog₂n)
实际上就是让时间复杂度为O(log₂n)的再循环n次
案例;这里执行次数就是 T(n) = (n+1) * (log₂n)

public class Demo04 {public static void main(String[] args) {int n =1024;int i ;//num:用来计数int num = 0;for (int m = 0; m <= n; m++) {i =1;while (i<n){i = i * 2 ;num++;}}System.out.println("执行次数->"+num); //执行次数->10250  (1024+1) * 10}
}

平方阶Ο(n²)
实际就是把时间复杂度为O(n)的再嵌套一层循环;即双层循环;也可写作O( m* n)
案例

public class Demo05 {public static void main(String[] args) {int w =0;int num = 0;int m =10;int n =10;for (int i = 1; i <= m ; i++) {for (int j = 1; j <= n; j++) {w = num;num ++;}}System.out.println(w);  // 99System.out.println("执行次数->"+num);//执行次数->100}
}

平均&最差时间复杂度

2.冒泡排序

按照提前设定的规则 (由小到大 / 由大到小) ;比较前后两个相邻元素的大小;若逆序了,就发生交换;

例如需要完成由小到大冒泡排序:29,10,14,37,14,3
图示:–>

初始的理解过程

总共经过数组的(长度-1)次大的交换过程;即 5 次;
其实每次大的排序结束后就有一个最大的值固定下来了;所以循环次数会比上一次的少一次
(1)
10 -> 29 -> 14 -> 37 -> 14 -> 3
10 -> 14 -> 29 -> 37 -> 14 -> 3
10 -> 14 -> 29 -> 37 -> 14 -> 3
10 -> 14 -> 29 -> 14 -> 37 -> 3
10 -> 14 -> 29 -> 14 -> 3 -> 37
(2)
10 -> 14 -> 29 -> 14 -> 3 -> 37
10 -> 14 -> 29 -> 14 -> 3 -> 37
10 -> 14 -> 14 -> 29 -> 3 -> 37
10 -> 14 -> 14 -> 3 -> 29 -> 37
(3)
10 -> 14 -> 14 -> 3 -> 29 -> 37
10 -> 14 -> 14 -> 3 -> 29 -> 37
10 -> 14 -> 3 -> 14 -> 29 -> 37
(4)
10 -> 14 -> 3 -> 14 -> 29 -> 37
10 -> 3 -> 14 -> 14 -> 29 -> 37
(5)
3 -> 10 -> 14 -> 14 -> 29 -> 37

分步骤写法;

这里分步骤展示排序过程

public class BubbleSortTest2 {public static void main(String[] args) {//需要排序的数组int[] array = {29,10,14,37,14,3};//临时变量,用于前后交换时临时存储;int temp = 0;//1.第一次排序;for (int i = 0; i < array.length - 1; i++) {if(array[i] > array[i+1]){temp = array[i];array[i] = array[i+1];array[i+1] =temp;}}System.out.println("第一次排序后-->"+ Arrays.toString(array));//第一次排序后-->[10, 14, 29, 14, 3, 37]//2.第二次排序;for (int i = 0; i < array.length - 1 - 1; i++) {if(array[i] > array[i+1]){temp = array[i];array[i] = array[i+1];array[i+1] =temp;}}System.out.println("第二次排序后-->"+ Arrays.toString(array));//第二次排序后-->[10, 14, 14, 3, 29, 37]//3.第三次排序for (int i = 0; i < array.length - 1 - 1 - 1; i++) {if(array[i] > array[i+1]){temp = array[i];array[i] = array[i+1];array[i+1] =temp;}}System.out.println("第三次排序后-->"+ Arrays.toString(array));//第三次排序后-->[10, 14, 3, 14, 29, 37]//4.第四次排序;for (int i = 0; i < array.length - 1 - 1 -1; i++) {if(array[i] > array[i+1]){temp = array[i];array[i] = array[i+1];array[i+1] =temp;}}System.out.println("第四次排序后-->"+ Arrays.toString(array));//第四次排序后-->[10, 3, 14, 14, 29, 37]//5.第五次排序;for (int i = 0; i < array.length - 1 - 1 -1; i++) {if(array[i] > array[i+1]){temp = array[i];array[i] = array[i+1];array[i+1] =temp;}}System.out.println("第五次排序后-->"+ Arrays.toString(array));//第五次排序后-->[3, 10, 14, 14, 29, 37]}
}

综合写法

public class BubbleSortTest {public static void main(String[] args) {//需要排序的数组int[] array = {29,10,14,37,14,3};//调用方法; 完成由大到小排序int[] sortArray = BubbleSort(array);System.out.println("冒泡排序结果-->"+Arrays.toString(sortArray));//冒泡排序结果-->[3, 10, 14, 14, 29, 37]}public static int[] BubbleSort(int[] array){for (int i = 0; i <array.length -1; i++) {for (int j = 0; j < array.length - i - 1; j++) {//后一个和之前的交换;if(array[j] > array[j+1]){int temp = array[j];array[j] = array[j+1];array[j+1] = temp;}}System.out.println("第"+(i+1)+"次排序后-->"+Arrays.toString(array));}return array;}
}

运行结果

第1次排序后-->[10, 14, 29, 14, 3, 37]
第2次排序后-->[10, 14, 14, 3, 29, 37]
第3次排序后-->[10, 14, 3, 14, 29, 37]
第4次排序后-->[10, 3, 14, 14, 29, 37]
第5次排序后-->[3, 10, 14, 14, 29, 37]
冒泡排序结果-->[3, 10, 14, 14, 29, 37]

稍微优化一下

如果说,我这个数组比较特殊;
例如:3,2,14,37,14,3
看看它的执行步骤;会发现其实第三次它就排序完成了;但还进行了后面的无意义排序;

第1次排序后-->[2, 3, 14, 14, 3, 37]
第2次排序后-->[2, 3, 14, 3, 14, 37]
第3次排序后-->[2, 3, 3, 14, 14, 37]
第4次排序后-->[2, 3, 3, 14, 14, 37]
第5次排序后-->[2, 3, 3, 14, 14, 37]
冒泡排序结果-->[2, 3, 3, 14, 14, 37]

那么,就对之前的冒泡排序优化一下;
在执行时加入标志位的判断;

public class BubbleSortTest3 {public static void main(String[] args) {//需要排序的数组int[] array = {3,2,14,37,14,3};//调用方法; 完成由大到小排序int[] sortArray = BubbleSort(array);System.out.println("冒泡排序结果-->"+Arrays.toString(sortArray));}public static int[] BubbleSort(int[] array){//定义标志位;boolean flag =false;for (int i = 0; i <array.length -1; i++) {for (int j = 0; j < array.length - i - 1; j++) {//后一个和之前的交换;if(array[j] > array[j+1]){flag = true;int temp = array[j];array[j] = array[j+1];array[j+1] = temp;}}//对标志位判断后再决定是否继续循环;if(flag){//重置标志位;flag = false;}else {//表示没发生交换;跳过本次循环;break;}System.out.println("第"+(i+1)+"次排序后-->"+Arrays.toString(array));}return array;}
}

看看执行过程

第1次排序后-->[2, 3, 14, 14, 3, 37]
第2次排序后-->[2, 3, 14, 3, 14, 37]
第3次排序后-->[2, 3, 3, 14, 14, 37]
冒泡排序结果-->[2, 3, 3, 14, 14, 37]

3.简单选择排序

比如说要定义由小到大的排序;
首先假设数组的第一个数是最小的数;去依次和后面的数进行比较,直到找到一个比它小的,然后将那个数标记为最小的数,接着继续依次比较;直到数组遍历结束;将带有标记的最小数字和第一个数交换;
这时,第一个数的位置就定下来了;接着开始假设第二个数为最小的数,重复之前的步骤…直到完成排序;

就用案例
8 -> 3 -> 2 -> 1 -> 7 -> 4 -> 6 -> 5来看了

图示过程–>

这七次排序的分解过程;

初始 =====>8 -> 3 -> 2 -> 1 -> 7 -> 4 -> 6 -> 5
(1)
1 -> 3 -> 2 -> 8 -> 7 -> 4 -> 6 -> 5
(2)
1 -> 2 -> 3 -> 8 -> 7 -> 4 -> 6 -> 5
(3)
1 -> 2 -> 3 -> 8 -> 7 -> 4 -> 6 -> 5
(4)
1 -> 2 -> 3 -> 4 -> 7 -> 8 -> 6 -> 5
(5)
1 -> 2 -> 3 -> 4 -> 5 -> 8 -> 6 -> 7
(6)
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 8 -> 7
(7)
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8

首先是分步骤实现的方式

public class SelectSortTest {public static void main(String[] args) {//需要排序的数组;int[] array = {8, 3, 2, 1, 7, 4, 6, 5};System.out.println("选择排序之前-->   "+Arrays.toString(array));//--------------------- ( 1 )----------------------------------------//定义最小值的索引,以及最小值;int minIndex = 0;int minVal = array[0];//1.第一次排序;for (int i = 0+1; i < array.length ; i++) {//若比较,找到比这个最小值还小的数;就把那个数标记为最小值;if(minVal > array[i]){minIndex = i;minVal =array[i];}}//结束后,再交换;array[minIndex] = array[0];array[0] = minVal;System.out.println("第一次排序结束后-->"+Arrays.toString(array));//-----------------------( 2 )--------------------------------------//最小值以及索引重置;minIndex = 1;minVal = array[1];//2.第二次排序;for (int i = 1+1; i < array.length ; i++) {//若比较,找到比这个最小值还小的数;就把那个数标记为最小值;if(minVal > array[i]){minIndex = i;minVal =array[i];}}//结束后,再交换;array[minIndex] = array[1];array[1] = minVal;System.out.println("第二次排序结束后-->"+Arrays.toString(array));//------------------------( 3 )-------------------------------------//最小值以及索引重置;minIndex = 2;minVal = array[2];//3.第三次排序;for (int i = 1+1+1; i < array.length ; i++) {//若比较,找到比这个最小值还小的数;就把那个数标记为最小值;if(minVal > array[i]){minIndex = i;minVal =array[i];}}//结束后,再交换;array[minIndex] = array[2];array[2] = minVal;System.out.println("第三次排序结束后-->"+Arrays.toString(array));//------------------------( 4 )-------------------------------------//最小值以及索引重置;minIndex = 3;minVal = array[3];//4.第四次排序;for (int i = 1+1+1+1; i < array.length ; i++) {//若比较,找到比这个最小值还小的数;就把那个数标记为最小值;if(minVal > array[i]){minIndex = i;minVal =array[i];}}//结束后,再交换;array[minIndex] = array[3];array[3] = minVal;System.out.println("第四次排序结束后-->"+Arrays.toString(array));//-------------------------( 5 )------------------------------------//最小值以及索引重置;minIndex = 4;minVal = array[4];//5.第五次排序;for (int i = 1+1+1+1+1; i < array.length ; i++) {//若比较,找到比这个最小值还小的数;就把那个数标记为最小值;if(minVal > array[i]){minIndex = i;minVal =array[i];}}//结束后,再交换;array[minIndex] = array[4];array[4] = minVal;System.out.println("第五次排序结束后-->"+Arrays.toString(array));//--------------------------( 6 )-----------------------------------//最小值以及索引重置;minIndex = 5;minVal = array[5];//6.第六次排序;for (int i = 1+1+1+1+1+1; i < array.length ; i++) {//若比较,找到比这个最小值还小的数;就把那个数标记为最小值;if(minVal > array[i]){minIndex = i;minVal =array[i];}}//结束后,再交换;array[minIndex] = array[5];array[5] = minVal;System.out.println("第六次排序结束后-->"+Arrays.toString(array));//---------------------------( 7 )----------------------------------//最小值以及索引重置;minIndex = 6;minVal = array[6];//7.第七次排序;for (int i = 1+1+1+1+1+1+1; i < array.length ; i++) {//若比较,找到比这个最小值还小的数;就把那个数标记为最小值;if(minVal > array[i]){minIndex = i;minVal =array[i];}}//结束后,再交换;array[minIndex] = array[6];array[6] = minVal;System.out.println("第七次排序结束后-->"+Arrays.toString(array));}
}

结果过程

选择排序之前-->   [8, 3, 2, 1, 7, 4, 6, 5]
第一次排序结束后-->[1, 3, 2, 8, 7, 4, 6, 5]
第二次排序结束后-->[1, 2, 3, 8, 7, 4, 6, 5]
第三次排序结束后-->[1, 2, 3, 8, 7, 4, 6, 5]
第四次排序结束后-->[1, 2, 3, 4, 7, 8, 6, 5]
第五次排序结束后-->[1, 2, 3, 4, 5, 8, 6, 7]
第六次排序结束后-->[1, 2, 3, 4, 5, 6, 8, 7]
第七次排序结束后-->[1, 2, 3, 4, 5, 6, 7, 8]

稍微优化一下

public class SelectSortTest01 {public static void main(String[] args) {//需要排序的数组;int[] array = {8, 3, 2, 1, 7, 4, 6, 5};int[] result = SelectSort(array);System.out.println("选择排序结束后的-->"+Arrays.toString(result));//选择排序结束后的-->[1, 2, 3, 4, 5, 6, 7, 8]}//选择排序的方法;public static int[] SelectSort(int[] array) {for (int i = 0; i < array.length - 1; i++) {//定义最小值的索引,最小值; 先假设当前的数为最小的;int minIndex = i;int minVal = array[i];for (int j = i + 1; j < array.length; j++) {//比较最小值和其他的数;if (minVal > array[j]) {//仅标记最小值,以及得到它的索引;minVal = array[j];minIndex = j;}}//若最小值不是假设的那个;if (minIndex != i) {//交换最小值;array[minIndex] = array[i];array[i] = minVal;}}return array;}
}

4.直接插入排序

首先假设第一个元素是已经排序好的有序表,后面的元素都是无序的;
然后从第二个元素开始; 和前面的第一个有序表元素比较,放入合适的位置;
然后这时前两个元素形成有序表,后面的是无序的;
然后这时把第三个元素获取到,和前面的有序表(已经有两个元素了)比较;放入合适的位置;
… 以此类推;直到将所有的元素排序完毕.

例如;要对16 - >3 -> 12 -> 1 -> 30 -> 6 进行插入排序
图解–>

• 首先明确,待插入的数是从第2个数开始的;也就是数组下标索引 为 1的数;
• 那么,先把待插入的数值存起来;然后他要插入,首先找的是前面有序表的最后一个;也就是这个待插入数值的下标的前一个;
• 若这个待插入的数值比前面的有序表最后一个数还大,那么直接把它放在有序表的最后一个位置;
• 然后,它如果比前面的有序表最后一个还小,就说明它要放入前面的表里面;那么首先让前面的挪一个位置出来,放到这个待插入的数的原来位置;
• 注意这个待插入数的值已经提前被取出来了,那么它在有序表中找位置,还是一样的,和前面的比较;…
• 直到找到最前面的一个,一定注意不能数组越界

首先还是分步骤的实现

package day06sorting.sort03_insertionsort;import java.util.Arrays;
/*** @author by CSDN@小智RE0* @date 2021-11-04 21:18* 插入排序,分步骤 写一下*/
public class InsertionSortTest {public static void main(String[] args) {//需要完成排序的数组;int[] array = {16,3,12,1,30,6};System.out.println("排序之前的数组-->"+ Arrays.toString(array));//---------------------( 1 )-------------------------------->//首先定义待插入的元素; 以及它的(前一个位置)待插入点;  注意第一步从第二个元素开始;int insertVal = array[1];int insertIndex = 1 - 1 ;//判断是否可插入前面 有序表 的条件;while (insertIndex >=0 && array[insertIndex] > insertVal){//将它的前一个数换到后面来;腾出位置;array[insertIndex +1 ] = array[insertIndex];//待插入点前移;insertIndex -- ;}//注意,上面可能会让 insertIndex 待插入点到达 -1 位置;//这里把这个确定的最小值放入插入点;array[insertIndex +1 ] = insertVal;System.out.println("第一次插入排序后-->"+Arrays.toString(array));//---------------------( 2 )-------------------------------->//改变待插入的元素 以及 待插入点insertVal = array[2];insertIndex = 2 - 1 ;//判断是否可插入前面 有序表 的条件;while (insertIndex >=0 && array[insertIndex] > insertVal){//将它的前一个数换到后面来;腾出位置;array[insertIndex +1 ] = array[insertIndex];//待插入点前移;insertIndex -- ;}//注意,上面可能会让 insertIndex 待插入点到达 -1 位置;//这里把这个确定的最小值放入插入点;array[insertIndex +1 ] = insertVal;System.out.println("第二次插入排序后-->"+Arrays.toString(array));//---------------------( 3 )-------------------------------->//改变待插入的元素 以及 待插入点insertVal = array[3];insertIndex = 3 - 1 ;//判断是否可插入前面 有序表 的条件;while (insertIndex >=0 && array[insertIndex] > insertVal){//将它的前一个数换到后面来;腾出位置;array[insertIndex +1 ] = array[insertIndex];//待插入点前移;insertIndex -- ;}//注意,上面可能会让 insertIndex 待插入点到达 -1 位置;//这里把这个确定的最小值放入插入点;array[insertIndex +1 ] = insertVal;System.out.println("第三次插入排序后-->"+Arrays.toString(array));//---------------------( 4 )-------------------------------->//改变待插入的元素 以及 待插入点insertVal = array[4];insertIndex = 4 - 1 ;//判断是否可插入前面 有序表 的条件;while (insertIndex >=0 && array[insertIndex] > insertVal){//将它的前一个数换到后面来;腾出位置;array[insertIndex +1 ] = array[insertIndex];//待插入点前移;insertIndex -- ;}//注意,上面可能会让 insertIndex 待插入点到达 -1 位置;//这里把这个确定的最小值放入插入点;array[insertIndex +1 ] = insertVal;System.out.println("第四次插入排序后-->"+Arrays.toString(array));//---------------------( 5 )-------------------------------->//改变待插入的元素 以及 待插入点insertVal = array[5];insertIndex = 5 - 1 ;//判断是否可插入前面 有序表 的条件;while (insertIndex >=0 && array[insertIndex] > insertVal){//将它的前一个数换到后面来;腾出位置;array[insertIndex +1 ] = array[insertIndex];//待插入点前移;insertIndex -- ;}//注意,上面可能会让 insertIndex 待插入点到达 -1 位置;//将待插入元素放到那个合适的位置; 注意上面的值由于在循环内要进行 -- 运算,然后才在条件判断;所以实际的待插入点在后一位;array[insertIndex +1 ] = insertVal;System.out.println("第五次插入排序后-->"+Arrays.toString(array));}
}

结果

排序之前的数组-->[16, 3, 12, 1, 30, 6]
第一次插入排序后-->[3, 16, 12, 1, 30, 6]
第二次插入排序后-->[3, 12, 16, 1, 30, 6]
第三次插入排序后-->[1, 3, 12, 16, 30, 6]
第四次插入排序后-->[1, 3, 12, 16, 30, 6]
第五次插入排序后-->[1, 3, 6, 12, 16, 30]

稍微优化一下

package day06sorting.sort03_insertionsort;import java.util.Arrays;/*** @author by CSDN@小智RE0* @date 2021-11-04 21:44* 插入排序*/
public class InsertionSortTest02 {public static void main(String[] args) {//定义要排序的数组;int[] array ={16,3,12,1,30,6};System.out.println("排序之前的数组-->"+ Arrays.toString(array));//进行插入排序;int[] sort = InsertionSort(array);System.out.println("排序结束后的数组-->"+Arrays.toString(array));}//插入排序方法;public static int[]  InsertionSort(int[] array){//首先明白,待插入的元素是从第二个元素开始的,所以它遍历的长度自然就是数组的长度了;for (int i = 1; i < array.length ; i++) {//待插入的元素,待插入的位置;int insertVal = array[i];int insertIndex = i -1;//遍历前面的有序表;找找合适的位置;while (insertIndex >= 0 && array[insertIndex] > insertVal){//前面的一个元素换到后面;array[insertIndex+1] = array[insertIndex];//待插入点前移;insertIndex -- ;}//将待插入元素放到那个合适的位置; 注意上面的值由于在循环内要进行 -- 运算,然后才在条件判断;所以实际的待插入点在后一位;array[insertIndex+1] =insertVal;System.out.println("第"+i+"次插入排序==>"+Arrays.toString(array));}return array;}
}

结果

排序之前的数组-->[16, 3, 12, 1, 30, 6]
第1次插入排序==>[3, 16, 12, 1, 30, 6]
第2次插入排序==>[3, 12, 16, 1, 30, 6]
第3次插入排序==>[1, 3, 12, 16, 30, 6]
第4次插入排序==>[1, 3, 12, 16, 30, 6]
第5次插入排序==>[1, 3, 6, 12, 16, 30]
排序结束后的数组-->[1, 3, 6, 12, 16, 30]

5. 希尔排序

在刚才的排序中,可以看到一个比较麻烦的状况;
如果说待插入的这个数啊,它就是比前面假设的有序表里面的元素都小,那么它想到达这有序表合适的位置,就得让这有序表的元素一个个地后移,这要是数据量大的话,也会浪费时间;

那么希尔排序就优化了插入排序的过程;缩小增量;对数组不断地分组,直到增量缩小到1;

图示

交换式 实现

分步骤实现

public class SheelSortTest {public static void main(String[] args) {int[] array ={8,9,1,7,2,3,5,4,6,0};//首先是分步骤实现;System.out.println("排序前的数组-->"+ Arrays.toString(array));//定义临时变量;int temp =0;//1.首先两两一组,分为5组; 步长为5;for (int i = 5; i < array.length; i++) {for (int j = i -5; j >=0 ; j-=5) {//交换;if(array[j]>array[j+5]){temp = array[j];array[j] = array[j+5];array[j+5] = temp;}}}System.out.println("第一次排序--->"+ Arrays.toString(array));//2.交换后,分为2组; 步长为2;for (int i = 2; i < array.length; i++) {for (int j = i -2; j >=0 ; j-=2) {//交换;if(array[j]>array[j+2]){temp = array[j];array[j] = array[j+2];array[j+2] = temp;}}}System.out.println("第二次排序--->"+ Arrays.toString(array));//3.分为1组; 步长为1;for (int i = 1; i < array.length; i++) {for (int j = i -1; j >=0 ; j-=1) {//交换;if(array[j]>array[j+1]){temp = array[j];array[j] = array[j+1];array[j+1] = temp;}}}System.out.println("第三次排序--->"+ Arrays.toString(array));}
}

排序前的数组-->[8, 9, 1, 7, 2, 3, 5, 4, 6, 0]
第一次排序--->[3, 5, 1, 6, 0, 8, 9, 4, 7, 2]
第二次排序--->[0, 2, 1, 4, 3, 5, 7, 6, 9, 8]
第三次排序--->[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

综合一下

public class SheelSortTest01 {public static void main(String[] args) {//需要排序的数组;int[] array ={15,25,1,6,8,2,99,27,36,0,55};System.out.println("排序前的数组->"+Arrays.toString(array));int[] sheelSortExchange = sheelSortExchange(array);System.out.println("排序后的数组->"+Arrays.toString(sheelSortExchange));}//交换式希尔排序public static  int[] sheelSortExchange(int[] array){//定义变量记录排序的次数;int num =0;//每次按一半进行分组;for (int group = array.length/2; group >0 ; group/=2) {//分组;for (int i = group; i < array.length; i++) {//组内交换;for (int j = i - group; j >=0 ; j-=group) {//由小到大交换;if(array[j]>array[j+group]){int temp = array[j];array[j] = array[j+group];array[j+group] = temp;}}}System.out.println("第"+(++num)+"次排序后-->"+ Arrays.toString(array));}return array;}
}

排序结果

排序前的数组->[15, 25, 1, 6, 8, 2, 99, 27, 36, 0, 55]
第1次排序后-->[2, 25, 1, 6, 0, 15, 99, 27, 36, 8, 55]
第2次排序后-->[0, 6, 1, 8, 2, 15, 36, 25, 55, 27, 99]
第3次排序后-->[0, 1, 2, 6, 8, 15, 25, 27, 36, 55, 99]
排序后的数组->[0, 1, 2, 6, 8, 15, 25, 27, 36, 55, 99]

移位方式 实现

public class SheelSortTest02 {public static void main(String[] args) {//需要排序的数组;int[] array ={18,99,0,6,25,36,15,4,2,1,15};System.out.println("排序前的数组-->"+Arrays.toString(array));int[] sortShift = sheelSortShift(array);System.out.println("排序后的数组-->"+Arrays.toString(sortShift));}//移位式希尔排序;public static int[] sheelSortShift(int[] array){//定义变量为排序计数;int num = 0 ;//先保障缩小增量;for (int group = array.length/2; group >0 ; group/=2) {//移动位置;for (int i = group; i < array.length ; i++) {//组内插入前先保存待插入的点位和数值;int insertIndex = i;int insertVal = array[i];//若这个待插入数比它同组的前面那个数还小,就考虑移动位置插入;if(array[insertIndex] < array[insertIndex - group]){//不断遍历,直至找到合适位置while (insertIndex -group >= 0 && insertVal < array[insertIndex -group]){//将组内前面的位置空出来;array[insertIndex] =  array[insertIndex - group];//移动要插入的位置;insertIndex -= group;}//将待插入点放到合适位置;array[insertIndex] = insertVal;}}System.out.println("第"+(++num)+"次排序后-->"+Arrays.toString(array));}return array;}
}

排序后结果

排序前的数组-->[18, 99, 0, 6, 25, 36, 15, 4, 2, 1, 15]
第1次排序后-->[15, 15, 0, 2, 1, 18, 99, 4, 6, 25, 36]
第2次排序后-->[0, 2, 1, 4, 6, 15, 15, 18, 36, 25, 99]
第3次排序后-->[0, 1, 2, 4, 6, 15, 15, 18, 25, 36, 99]
排序后的数组-->[0, 1, 2, 4, 6, 15, 15, 18, 25, 36, 99]

6.快速排序

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分
的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序

例如对数组40,2,22,25,14,1,3进行排序

图解案例1;

图解案例2对 [-9,78,0,23,-567,70] 进行从小到大的排序

实现完成

public class QuickSortTest {public static void main(String[] args) {//需要排序的数组;int[] array ={40,2,22,25,14,1,3};int[] quickSort = quickSort(array, 0, array.length - 1);System.out.println(Arrays.toString(quickSort));}/*** 快速排序* @param array 需要排序的数组* @param left  左指针* @param right 右指针* @return      排序后的数组*/public static int[] quickSort(int[] array,int left,int right){//先把左右指针提前存起来;int l = left;int r = right;//找到中心点;int bottom = array[(left +right)/2];System.out.println("当前中心轴值-->"+bottom);//左指针 和 右指针向中心移动;while (l < r){//左右指针移动;while (array[l] < bottom){l+=1;}while (array[r] > bottom){r-=1;}//跳出循环的条件;if(l>=r){break;}//先进行交换;int temp =array[l];array[l] = array[r];array[r] = temp;//考虑接近到达中心点的情况;if(array[l] == bottom){r-=1;}if(array[r] == bottom){l+=1;}}//还需考虑两指针相遇的情况;if(l == r){l+=1;r-=1;}//向左递归;if(left<r){quickSort(array,left,r);}//向右递归;if(right>l){quickSort(array,l,right);}return array;}
}

执行过程

当前中心轴值-->25
当前中心轴值-->22
当前中心轴值-->2
当前中心轴值-->14
[1, 2, 3, 14, 22, 25, 40]

7.归并排序

该算法使用到了分治(分而治之)算法的思想,将大的问题细分为小的问题进行处理

例如图解数组[ 8 , 4 , 5 , 7, 1, 3, 6, 2 ]过程

最后一个治理合并为有序数组的过程

图示对12,3,8,20,18,1,5进行排序

具体的实现过程

package day06sorting.sort06_mergesort;import java.util.Arrays;/*** @author by CSDN@小智RE0* @date 2021-11-06 13:48* 归并排序*/
public class MergeSortTest {public static void main(String[] args) {//需要排序的数组;int[] array= {12,3,8,20,18,1,5};//临时数组;int[] temp = new int[array.length];//归并排序;mergeSort(array,0, array.length - 1,temp );System.out.println(Arrays.toString(array));}/*** 分化数组* @param array 原数组* @param left  左索引* @param right 右索引* @param temp  临时数组*/public static void mergeSort(int[] array, int left, int right, int[] temp){if(left < right){//直接定义中心索引;int middle = (left + right) / 2;//左边递归分化;mergeSort(array,left,middle,temp);//右边递归分化;mergeSort(array,middle+1,right,temp);//合并数组;mergeArray(array,left,right,middle,temp);}}/*** 首先从合并处理开始写;* @param array 原数组* @param left  左边的数组索引* @param right 右边的数组索引* @param middle 中间的索引* @param tempArray 临时的数组*/private static void mergeArray(int[] array, int left, int right, int middle, int[] tempArray){//先确定i作为左边的索引;j作为右边列表的索引;int i = left;int j = middle + 1;//临时数组的索引;int tempIndex = 0;//首先根据需要,由小到大把一块数组先放入临时数组;while (i <= middle && j<=right){//左边的放入临时数组;if(array[i] <= array[j]){tempArray[tempIndex] = array[i];i+=1;tempIndex+=1;}else {//否则右边的放入临时数组;tempArray[tempIndex] = array[j];j+=1;tempIndex+=1;}}//可能一块的数组已经存完了,但是另一块还有剩余,那就全部存入临时数组;while (i<= middle){tempArray[tempIndex] = array[i];i+=1;tempIndex+=1;}while (j<=right){tempArray[tempIndex] = array[j];j+=1;tempIndex+=1;}//最终要把临时数组的放进原数组中去;//但是注意,由于要递归,这边的拷贝索引是动态的;//这里先初始化临时的索引;tempIndex = 0;//定义拷贝时的原数组左边动态索引;int originalLeftIndex = left;System.out.println("此时左索引originalLeftIndex==>"+originalLeftIndex +"此时右索引right==>"+right);while (originalLeftIndex<=right){array[originalLeftIndex] = tempArray[tempIndex];originalLeftIndex+=1;tempIndex+=1;}}}

执行结果

此时左索引originalLeftIndex==>0此时右索引right==>1
此时左索引originalLeftIndex==>2此时右索引right==>3
此时左索引originalLeftIndex==>0此时右索引right==>3
此时左索引originalLeftIndex==>4此时右索引right==>5
此时左索引originalLeftIndex==>4此时右索引right==>6
此时左索引originalLeftIndex==>0此时右索引right==>6
[1, 3, 5, 8, 12, 18, 20]

8.基数排序

将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。
以空间换时间;若数据量过大,会出现内存问题(OOM).

图示 数组[ 53, 3, 542, 748, 14, 214 ]的排序过程

图解过程

(1)

(2)

若这个元素没有十位数的话就补零,放在第一个桶里(即下标为0的那个数组),

(3)

同理,若没有百位数也在前面补零,放在第一个桶里

在实现时,用二维数组表示这10个桶数组;
每个桶的大小就设置为最大的,也就是需要排序的数组长度;
然后,还需要考虑每个桶实际存入的元素个数,以便于取出时可以明确地知道是否要遍历,遍历几次;

首先是分步骤完成

package day06sorting.sort07_basesort;import java.util.Arrays;/*** @author by CSDN@小智RE0* @date 2021-11-06 16:12* 基数排序*/
public class BaseSortTest {public static void main(String[] args) {//需要排序的数组;int[] array ={53,77,3,542,748,14,214};//分步骤完成过程;//定义二维数组方放10个桶;int[][] barrel = new int[10][array.length];//定义数组记录桶中元素的个数;int[] barrelCount =new int[10];//取出元素时,原数组的索引;int index = 0 ;System.out.println("第一次排序---->");//向桶里放入数据;for (int value : array) {//第一次是取个位数的;int numberOrders = value % 10;barrel[numberOrders][barrelCount[numberOrders]] = value;//注意要计数;barrelCount[numberOrders]++;}//把桶里的数又按顺序拿出来放进数组;for (int i = 0; i < barrelCount.length; i++) {//首先保证桶里有没有数据;if(barrelCount[i]!=0){for (int j = 0; j < barrelCount[i]; j++) {array[index++] = barrel[i][j];}}}System.out.println("第一次排序后-->"+ Arrays.toString(array));System.out.println("第二次排序---->");//需要重置计数的数组;barrelCount =new int[10];//向桶里放入数据;for (int k : array) {//第一次是取个位数的;int numberOrders = k / 10 % 10;barrel[numberOrders][barrelCount[numberOrders]] = k;//注意要计数;barrelCount[numberOrders]++;}//注意index要重置;index =0;//把桶里的数又按顺序拿出来放进数组;for (int i = 0; i < barrelCount.length; i++) {//首先保证桶里有没有数据;if(barrelCount[i]!=0){for (int j = 0; j < barrelCount[i]; j++) {array[index++] = barrel[i][j];}}}System.out.println("第二次排序后-->"+ Arrays.toString(array));System.out.println("第三次排序---->");//需要重置计数的数组;barrelCount =new int[10];//向桶里放入数据;for (int k : array) {//第一次是取个位数的;int numberOrders = k / 10 / 10 % 10;barrel[numberOrders][barrelCount[numberOrders]] = k;//注意要计数;barrelCount[numberOrders]++;}//注意index要重置;index =0;//把桶里的数又按顺序拿出来放进数组;for (int i = 0; i < barrelCount.length; i++) {//首先保证桶里有没有数据;if(barrelCount[i]!=0){for (int j = 0; j < barrelCount[i]; j++) {array[index++] = barrel[i][j];}}}System.out.println("第三次排序后-->"+ Arrays.toString(array));}
}

执行的过程

第一次排序---->
第一次排序后-->[542, 53, 3, 14, 214, 77, 748]
第二次排序---->
第二次排序后-->[3, 14, 214, 542, 748, 53, 77]
第三次排序---->
第三次排序后-->[3, 14, 53, 77, 214, 542, 748]

稍微优化一下

将这个分步的写法综合一下,因为实际计算时并不是说固定的排序几次;
首先就得找出最大值的长度;以便于确定要去排序几次;

//基数排序的方式;
public static void baseSort(int[] array) {int maxVal = array[0];//首先找最大值,for (int j : array) {if (j >= maxVal) {maxVal = j;}}//得到最大值的长度;int maxLength = (maxVal + "").length();//输出测试一下;System.out.println("当前要排序数组的最大元素为:" + maxVal + " 最大长度为:" + maxLength);//定义二维数组放置10个桶;int[][] barrel = new int[10][array.length];//定义一个数组来记录每个桶的元素数量;int[] barrelCount = new int[10];for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {for (int value : array) {//第一次取个位数;第二次取十位数;以此列推;int numberOrders = value / n % 10;//存入桶中;barrel[numberOrders][barrelCount[numberOrders]] = value;//计数递增;barrelCount[numberOrders]++;}//数组的索引;int index = 0;//取出桶的元素存向数组;for (int k = 0; k < barrelCount.length; k++) {//先判断桶里有没有元素;if (barrelCount[k] != 0) {for (int j = 0; j < barrelCount[k]; j++) {array[index++] = barrel[k][j];}}//重置记录桶的元素数量的数组;barrelCount[k] = 0;}}
}

---