1、排序算法汇总-选择、冒泡、插入
发布于 2022年 02月 13日 08:00
1、选择排序
时间的复杂度:O(N²)
- 在数组中找出最小的元素,和数组的首位进行交换
- 从剩余的元素中找出最小的元素,放到已排序元素的后面
- 依次循环第二步
/**
* @Author Sam
* @Description 选择排序 按照从小到大的方式进行排序
* @Date 2020/12/25
**/
public static void selectionSort(int[] array) {
if (array == null || array.length < 2) {
return;
}
//1、拿到数组角标为0的数据,依次跟后面的数据比较 0-----N-1
//2、找出最小的值,放到数组的起始位置,
int length = array.length;
for (int i = 0; i < length - 1; i++) {
//假设数组角标为0的第一个数据为最小值
int minIndex = i;
//根据拿到的值,依次向后比较,找出后面元素最小的角标
for (int j = i + 1; j < length; j++) {
if (array[minIndex] > array[j]) {
minIndex = j;
}
}
//经过第二个for循环,minIndex是整个数组中最小元素的角标,所以将最小的元素和前面的元素替换一下
swap(array, i, minIndex);
}
}
/**
* @Description 数组内两个元素的交换
* @Date 2020/12/25
* @Param array 数据
* @Param i 角标
* @Param j 角标
**/
public static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
2、冒泡排序
时间的复杂度:O(N²)
- 比较相邻的两个的元素的大小,如果左边的比右边的大,那么交换,这样比较一次下来,最右边的为最大值
2、循环一次往复
/**
* @Author Sam
* @Description 冒泡排序 从小到大
* @Date 2020/12/25
**/
public static void bubblingSort(int[] array) {
if (array == null || array.length < 2) {
return;
}
int length = array.length;
//外层循环控制整个数组的比较的位置
for (int i = length - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if (array[j] > array[j + 1]) {
swap(array, j, j + 1);
}
}
}
}
/**
* @Description 数组内两个元素的交换
* @Date 2020/12/25
* @Param array 数据
* @Param i 角标
* @Param j 角标
**/
public static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
3、插入排序
时间的复杂度:O(N²)
- 遍历元素,每个元素都比较它左边的元素,如果比左边的元素小,那么就位置交换
- 位置交换后的元素,如果左边有元素,那么继续比较,如果比左边的元素小,那么就位置交换
- 循环往复
/**
* @Author Sam
* @Description 插入排序,从小到大
* @Date 2020/12/28
**/
public static void insertSort(int[] array) {
if (array == null || array.length < 2) {
return;
}
for (int i = 1; i < array.length; i++) {
//如果左边的比右边的元素大,那么位置交换。
for (int j = i - 1; j >= 0 && array[j] > array[j + 1]; j--) {
swap(array, j, j + 1);
}
}
}
/**
* @Description 数组内两个元素的交换
* @Date 2020/12/25
* @Param array 数据
* @Param i 角标
* @Param j 角标
**/
public static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}