n^2时间复杂度排序算法

目录
  1. 冒泡排序
  2. 插入排序
  3. 选择排序

之所以将这3个排序归为一类, 是因为它们的时间复杂度都是O(n^2)。由于这几个排序比较简单,主要就贴代码了。

1.冒泡排序

冒泡排序: 顾名思义,就是泡泡越往上越大,也就是相邻的两个数比较,如果前面的比后面的大,则交换位置

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
30
31
32
33
34
35
36
//下面打印数组的函数省略
public static void printArray(int [] array) {
System.out.println(Arrays.toString(array));
}

public static int [] sortWithFlag(int [] array) {
int length = array.length;
if (length <= 1) {
return array;
}
printArray(array);
//0 -> length-1
for (int i = 0; i < length; i ++) {
boolean flag = true;
for (int j = 0; j < length - i - 1; j++) {
//如果相邻的两个数前面的比后面的大,则交换位置
if (array[j] > array[j + 1]) {
int temp = array[j + 1];
array[j + 1] = array[j];
array[j] = temp;
// 一次循环内都没有进这个if则表示前一个数都比后一个数要小,也就是说
// 数据已经是从小到大排好序了
flag = false;
}
System.out.println("i:"+i+",j:"+j);

}
System.out.println("i:"+i);
printArray(array);
// 已经排好序则退出循环
if (flag) {
break;
}
}
return array;
}

中间过程输出结果:

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
[3, 9, 2, 1, 0, 8, 4, 7, 5, 6]
--------------------------------
i:0,j:0
i:0,j:1
i:0,j:2
i:0,j:3
i:0,j:4
i:0,j:5
i:0,j:6
i:0,j:7
i:0,j:8
i:0
[3, 2, 1, 0, 8, 4, 7, 5, 6, 9]
i:1,j:0
i:1,j:1
i:1,j:2
i:1,j:3
i:1,j:4
i:1,j:5
i:1,j:6
i:1,j:7
i:1
[2, 1, 0, 3, 4, 7, 5, 6, 8, 9]
i:2,j:0
i:2,j:1
i:2,j:2
i:2,j:3
i:2,j:4
i:2,j:5
i:2,j:6
i:2
[1, 0, 2, 3, 4, 5, 6, 7, 8, 9]
i:3,j:0
i:3,j:1
i:3,j:2
i:3,j:3
i:3,j:4
i:3,j:5
i:3
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
i:4,j:0
i:4,j:1
i:4,j:2
i:4,j:3
i:4,j:4
i:4 // 之后就是排好序的了
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

2.插入排序

插入排序: 就是将数组索引1遍历到数组尾,然后将每个元素与前面的所有元素比较,插入到大小合适的位置(此时满足 array[p-1] < array[q] < array[p])即可。
插入分3步:

  1. 插入之前,保存本次循环的初始值: tmp = array[q](q为当前用来插入的元素的索引)
  2. 后移: 插入点p到q之前的所有元素都后移一位[,,,p,,,,q,,]
  3. 赋值: array[p] = tmp
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    public static int[] insertSort(int [] array) {
    printArray(array);
    System.out.println("------------------------------");
    int len = array.length;
    // 索引0的值 作为基准值
    for (int i = 1; i < len; i++) {
    int temp = array[i];
    int j;
    // array[j] > array[i],表示前面的数比后面的数大,则将从不大于array[i]的后一位开始到i的这些元素全部后移1位
    for (j = i - 1; j >= 0 && array[j] > temp; j--) {
    //后移
    array[j + 1] = array[j];
    }
    //插入
    array[j + 1] = temp;

    System.out.println("i:"+i+",j:"+(j+1));
    printArray(array);
    }
    return array;
    }

中间过程输出结果:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
[3, 9, 2, 1, 0, 8, 4, 7, 5, 6]
------------------------------
i:1,j:1
[3, 9, 2, 1, 0, 8, 4, 7, 5, 6]
i:2,j:0
[2, 3, 9, 1, 0, 8, 4, 7, 5, 6]
i:3,j:0
[1, 2, 3, 9, 0, 8, 4, 7, 5, 6]
i:4,j:0
[0, 1, 2, 3, 9, 8, 4, 7, 5, 6]
i:5,j:4
[0, 1, 2, 3, 8, 9, 4, 7, 5, 6]
i:6,j:4
[0, 1, 2, 3, 4, 8, 9, 7, 5, 6]
i:7,j:5
[0, 1, 2, 3, 4, 7, 8, 9, 5, 6]
i:8,j:5
[0, 1, 2, 3, 4, 5, 7, 8, 9, 6]
i:9,j:6
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

3.选择排序

选择排序: 从数组首位开始将数组中的所有元素遍历, 每次遍历选出剩下未排序的元素中最小的那个元素与本次遍历的起始元素交换位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static int[] selectSort(int [] array) {
printArray(array);
System.out.println("------------------------------");

int len = array.length;
for (int i = 0; i < len; i++) {
int minIndex = i;
for (int j = i + 1; j < len; j++) {
// 与小的索引minIndex对应的值比较
if (array[minIndex] > array[j]) {
minIndex = j;
}
System.out.println("i:"+i+",j:"+j);
}
int temp = array[minIndex];
array[minIndex] = array[i];
array[i] = temp;

printArray(array);
}
return array;
}

中间过程输出结果:

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
[3, 9, 2, 1, 0, 8, 4, 7, 5, 6]
------------------------------
i:0,j:1
i:0,j:2
i:0,j:3
i:0,j:4
i:0,j:5
i:0,j:6
i:0,j:7
i:0,j:8
i:0,j:9
[0, 9, 2, 1, 3, 8, 4, 7, 5, 6]
i:1,j:2
i:1,j:3
i:1,j:4
i:1,j:5
i:1,j:6
i:1,j:7
i:1,j:8
i:1,j:9
[0, 1, 2, 9, 3, 8, 4, 7, 5, 6]
i:2,j:3
i:2,j:4
i:2,j:5
i:2,j:6
i:2,j:7
i:2,j:8
i:2,j:9
[0, 1, 2, 9, 3, 8, 4, 7, 5, 6]
i:3,j:4
i:3,j:5
i:3,j:6
i:3,j:7
i:3,j:8
i:3,j:9
[0, 1, 2, 3, 9, 8, 4, 7, 5, 6]
i:4,j:5
i:4,j:6
i:4,j:7
i:4,j:8
i:4,j:9
[0, 1, 2, 3, 4, 8, 9, 7, 5, 6]
i:5,j:6
i:5,j:7
i:5,j:8
i:5,j:9
[0, 1, 2, 3, 4, 5, 9, 7, 8, 6]
i:6,j:7
i:6,j:8
i:6,j:9
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
i:7,j:8
i:7,j:9
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
i:8,j:9
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]