数据结构-八大排序之冒泡、选择、插入、希尔
一、冒泡排序
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;
}else
break;
}
}
}
}
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;
}else
break;
}
}
}
}
}4.3 内存图
原文地址：https://blog.csdn.net/m0_75163045/article/details/142760348
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！