简单排序(冒泡排序,插入排序,选择排序)

说明

主要介绍了冒泡排序,插入排序和选择排序的流程。

冒泡排序

冒泡排序流程

arr[0...N-1]范围上:

arr[0]arr[1],谁大谁来到1位置;

arr[1]arr[2],谁大谁来到2位置

以此类推…

arr[N-2]arr[N-1],谁大谁来到第N-1个位置上

arr[0...N-2]范围上,重复上面的过程,但最后一步是arr[N-3]arr[N-2],谁大谁来到第N-2个位置上

arr[0...N-3]范围上,重复上面的过程,但最后一步是arr[N-4]arr[N-3],谁大谁来到第N-3个位置上

以此类推…

最后在arr[0~1]范围上,重复上面的过程,但最后一步是arr[0]arr[1],谁大谁来到第一个位置上

冒泡排序示例图

bubblesort

冒泡排序源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Code_0001_Sort {
public static void bubbleSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = arr.length - 1; i >= 0; i--) {
for (int j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
}

private static void swap(int[] arr, int i, int j) {
if (arr == null || arr.length < 2 || i == j) {
return;
}
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
}

插入排序

插入排序流程

想让arr[0...0]上有序,这个范围只有一个数,当然是有序的。

想让arr[0...1]上有序,所以从arr[1]开始往前看,如果arr[1] < arr[0],就交换。否则什么也不做。

以此类推…

想让arr[0...i]上有序,所以从arr[i]开始往前看,arr[i]这个数不停向左移动,一直移动到左边的数字不再比自己大,停止移动。

最后一步,

想让arr[0...N-1]上有序, arr[N-1]这个数不停向左移动,一直移动到左边的数字不再比自己大,停止移动。

估算时发现这个算法流程的复杂程度,会因为数据状况的不同而不同。

插入排序示例图

insertSort

插入排序代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Code_0001_Sort {
public static void insertionSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
int n = arr.length;
for (int i = 1; i < n; i++) {
for (int j = i - 1; j >= 0; j--) {
if (arr[j] > arr[j + 1]) {
swap(arr, j + 1, j);
}
}
}
}

public static void swap(int[] arr, int i, int j) {
if (arr == null || arr.length < 2 || i == j) {
return;
}
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
}

选择排序

选择排序流程

arr[0...N-1]范围上,找到最小值所在的位置,然后把最小值交换到0位置。

arr[1...N-1]范围上,找到最小值所在的位置,然后把最小值交换到1位置。

arr[2...N-1]范围上,找到最小值所在的位置,然后把最小值交换到2位置。

以此类推…

arr[N-1...N-1]范围上,找到最小值位置,然后把最小值交换到N-1位置。

所以选择排序的时间复杂度为O(N^2)

选择排序代码

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 Code_0001_Sort {

public static void selectionSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 0; i < arr.length - 1; i++) {
int min = i;
for (int j = i + 1; j < arr.length; j++) {
min = arr[j] < arr[min] ? j : min;
}
swap(arr, i, min);
}
}

private static void swap(int[] arr, int i, int j) {
if (arr == null || arr.length < 2 || i == j) {
return;
}
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}

}

更多

算法和数据结构笔记

参考资料