一、冒泡排序
1.1 基础知识
思想：
前后两两进行比较，大的数据往后走，小的数据往前走。
一轮结束之后最大的数据到达正确的位置。
时间复杂度：
第一轮： 计算了 x-1
第二轮： 计算了 x-2
第三轮： 计算了 x-3
...
第x-1轮： 计算了 1
y=(x-1+1)*(x-1)/2
y=x^2 O(n^2)
1.2 代码
public class BubbleSort {public static void main(String[] args) {int[] arr= {5,7,4,2,0,3,1,6};sort(arr);System.out.println(Arrays.toString(arr));System.out.print("[");for(int i=0;i<arr.length;i++) {if(i==arr.length-1) {System.out.print(arr[i]);}else System.out.print(arr[i]+", ");}System.out.println("]");}public static void sort(int[] arr) {for(int j=0;j<arr.length;j++) {for(int i=0;i<arr.length-1-j;i++) {if(arr[i]>arr[i+1]) {//进行交换int temp=arr[i];arr[i]=arr[i+1];arr[i+1]=temp;}}}}
}1.3 内存图
二、选择排序
2.1 基础知识
原理：
默认待排序数组当中的第一个为最小值，找待排序数组当中真正的最小值和待排序数组中的第一个进行交换，最小值到达正确位置。
每一轮都让最小值到达正确位置。
时间复杂度：
第一轮： 查找 x次
第二轮： 查找 x-1次
第三轮： 查找 x-2次
...
第x-1轮： 查找 2 次
y=2+3+4+...+x=(x+2)*(x-1)/2
O(n^2)
2.2 代码
public class SelectSort {public static void main(String[] args) {int[] arr= {5,7,4,2,0,3,1,6};sort(arr);System.out.println(Arrays.toString(arr));}public static void sort(int[] arr) {for(int j=0;j<arr.length;j++) {int min=arr[j];int minindex=j;//记录最小值的下标//找真正的最小值for(int i=j;i<arr.length;i++) {if(arr[i]<min) {min=arr[i];minindex=i;}}//真正的最小值和待排序数组中第一个进行交换arr[minindex]=arr[j];arr[j]=min;}}
}
2.3 内存图
三、插入排序
3.1 基础知识
原理：
认为数组当中第一个数值是已经排好的数值，定义游标从第二个数据开始不断地向后进行遍历。
游标指向的数据指向已经排好序的数组当中。
如何实现插入？
定义 j 游标指向 i 的前一个数据 j , j和 j+1 进行比较
如果 j+1 指向的数值大，则数据到达正确位置
如果 j+1 指向的数据小，j 和 j+1 进行交换 j--
继续进行交换，直到 j+1 的值大或者越界。
越小的数据在后边交换的次数越多。
时间复杂度:
第一轮： 比较 1次
第二轮： 比较 2次
第三轮： 比较 3次
第四轮： 比较 4次
...
第x-1轮： 比较 x-1次
y=(1+x-1)*(x-1)/2
O(n^2)
3.2 代码
public class InsertSort {public static void main(String[] args) {int[] arr= {5,7,4,2,0,3,1,6};sort(arr);System.out.println(Arrays.toString(arr));}public static void sort(int[] arr) {for(int i=1;i<arr.length;i++) {//用j和j+1进行比较交换for(int j=i-1;j>=0;j--) {if(arr[j]>arr[j+1]) {//进行交换int temp=arr[j];arr[j]=arr[j+1];arr[j+1]=temp;}elsebreak;}}}
}
3.3 内存图
四、希尔排序（缩小增量排序）
4.1 基础知识
原理：
step1：
将数组按照数组长度的一半为间隔进行分组，组内进行插入排序
小的数值在前边，大的数值在后边
4
step2：
将数组按照数组长度的一半为间隔进行分组，组内进行插入排序
小的数值在前边，大的数值在后边
2
step3：
将数组按照数组长度的一半为间隔进行分组，组内进行插入排序
小的数值在前边，大的数值在后边
1
....
直到无法继续分组（步长为1时），整个数组视为一组，组内进行插入排序，只需要微调就可以。
时间复杂度：
第一轮： 计算次数 x 间隔 x/2 x/2^1
第二轮： 计算次数 x 间隔 x/2/2 x/2^2
间隔 x/2/2/2 x/2^3
...
第k轮 ： 计算次数 x 间隔 x/2^k 1
k=log2x
xlog2x---->O(nlogn)
4.2 代码
public class ShellSort {public static void main(String[] args) {int[] arr= {5,7,4,2,0,3,1,6};sort(arr);System.out.println(Arrays.toString(arr));}public static void sort(int[] arr) {for(int len=arr.length/2;len>=1;len=len/2) {for(int i=len;i<arr.length;i++) {//arr[j]和arr[j+len]进行比较for(int j=i-len;j>=0;j=j-len) {if(arr[j]>arr[j+len]) {int temp=arr[j];arr[j]=arr[j+len];arr[j+len]=temp;}elsebreak;}}}}
}4.3 内存图
