冒泡排序、简单选择排序和插入排序

1. 冒泡排序

1.1 算法步骤

(一)比较相邻的元素。如果第一个比第二个大,就交换他们两个

(二)对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。

(三)针对所有的元素重复以上的步骤,除了最后一个。

(四)持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

1.2 算法分析

平均时间复杂度: T(n) = O(n²)
最坏时间复杂度:T(n) = O(n²):当输入的数据是反序时,(此种情况下,可以for循环反序输出)
最好时间复杂度:T(n) = O(n):当输入的数据已经有序时,只需遍历一遍用于确认数据已有序。
空间复杂度:O(1)

1.3 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class BubbleSort implements IArraySort {

@Override
public int[] sort(int[] sourceArray) throws Exception {
// 对 arr 进行拷贝,不改变参数内容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
// boolean flag = true不放在这里,因为放在这里优化的是初始数组就有序,放在下面则可以表示某次循环有序
for (int i = 1; i < arr.length; i++) {
// 设定一个标记,若为true,则表示此次循环没有进行交换,也就是待排序列已经有序,排序已经完成。
boolean flag = true;

for (int j = 0; j < arr.length - i; j++) {
if (arr[j] > arr[j + 1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;

flag = false;
}
}
if (flag) {
break;
}
}
return arr;
}
}

此种优化只对有序数组起到作用,而如果是无序数组,这种优化还会增加负担,具体由代码第10行、18行、21行引起。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.Arrays;

/**
* @author by 慕容琴羽
* @Date 2022/4/29 13:56
*/
public class suanfa {
public Integer[] bubbleSort(Integer[] array) {
for (int end = array.length-1; end >0 ; end--) {
// sortIndex在数组完全有序的时候,完全有序时会将1赋值给end,end--后程序为0会退出
int sortIndex=1;
for (int begin = 0; begin <end; begin++) {
if (array[begin]>array[begin+1]){
Integer temp=array[begin+1];
array[begin+1]=array[begin];
array[begin]=temp;
sortIndex=begin;//记录每次交换的顺序,如果后面的数组有序,则这是最后一次交换的位置
}
}
end=sortIndex;//将最后一次的交换位置赋值给end,则再扫描的时候不需要再对后面有序数组扫描
}
return array;
}

public static void main(String[] args) {
Integer[] array = {1,2,3};
System.out.println(Arrays.toString(new suanfa().bubbleSort(array)));
}
}

2. 简单选择排序

2.1 算法步骤

(一)首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置。

(二)再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。

(三)重复第二步,直到所有元素均排序完毕。

1.2 复杂度分析

选择排序是时间复杂度表现最稳定的排序算法之一,无论什么数据进去都是O(n²) 的时间复杂度…..所以用到它的时候,数据规模越小越好。

平均时间复杂度: T(n) = O(n²)
最坏时间复杂度: T(n) = O(n²)
最好时间复杂度: T(n) = O(n²)
空间复杂度: O(1)

1.3 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class SelectionSort implements IArraySort {

@Override
public int[] sort(int[] sourceArray) throws Exception {
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

// 总共要经过 N-1 轮比较,剩最后一个的时候不用再比啦
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;

// 每轮需要比较的次数 N-i
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
// 记录目前能找到的最小值元素的下标
minIndex = j;
}
}

// 将找到的最小值和i位置所在的值进行交换
if (i != minIndex) {
int tmp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = tmp;
}

}
return arr;
}
}

3. 插入排序

插入排序的原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

3.1 算法步骤

(一)将第一待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。

(二)从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面。)

3.2 算法复杂度

平均时间复杂度: T(n) = O(n²)
**最坏时间复杂度: T(n) = O(n²)**:输入数组按降序排列(完全逆序)
**最好时间复杂度: T(n) = O(n)**:输入数组按升序排列(基本有序)
空间复杂度: O(1)

3.3 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class InsertSort implements IArraySort {

@Override
public int[] sort(int[] sourceArray) throws Exception {
// 对 arr 进行拷贝,不改变参数内容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

// 从下标为1的元素开始选择合适的位置插入,因为下标为0的只有一个元素,默认是有序的
for (int i = 1; i < arr.length; i++) {
// 记录要插入的数据
int tmp = arr[i];
// 从已经排序的序列最右边的开始比较,找到比其小的数
int j = i;
while (j > 0 && tmp < arr[j - 1]) {
arr[j] = arr[j - 1];
j--;
}
// 存在比其小的数,插入
if (j != i) {
arr[j] = tmp;
}
}
return arr;
}
}