1. 数据结构与算法
2. 算法总结
| 排序算法 | 时间复杂度（最好） | 时间复杂度（最坏） | 时间复杂度（平均） | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n) | O(n^2) | O(n^2) | O(1) | ✔️ |
| 选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | ✘ |
| 插入排序 | O(n) | O(n^2) | O(n^2) | O(1) | ✔️ |
| 希尔排序 | O(nlogn) | O(nlog^2 n) | O(nlog^2 n) | O(1) | ✘ |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | ✔️ |
| 快速排序 | O(nlogn) | O(n^2) | O(nlogn) | O(logn) | ✘ |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | ✘ |
| 桶排序 | O(n) | O(n^2) | O(n) | O(n*k) | ✔️ |
| 计数排序 | O(n+k) | O(n+k) | O(n+k) | O(n+k) | ✔️ |
| 基数排序 | O(n*k) | O(n*k) | O(n*k) | O(n+k) | ✔️ |
3. 算法实现
冒泡排序
动图
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19public static void bubbleSort(int [] a) {
if(a.length <= 1) {
return;
}
for(int i = 0; i < a.length; i++) {
boolean flag = true; // 提前结束循环标志位
for(int j = 0; j < a.length-1-i; j++) {
if(a[j] > a[j+1]) {
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
flag = false; // 此次冒泡有数据交换
}
}
if(flag) {
break;
}
}
}
选择排序
动图
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21public static void selectionSort(int [] a) {
if(a.length <= 1) {
return;
}
for(int i=0; i<n-1; i++) {
// 查找最小值
int minIndex = i;
for(int j = i+1; j < n; j++) {
if(a[j] < a[minIndex]) {
minIndex = j;
}
}
// 交换
if(minIndex != i) {
int temp = a[i];
a[i] = a[minIndex];
a[minIndex] = temp;
}
}
}
插入排序
动图
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21public static void insertionSort(int [] a) {
if(a.length <= 1) {
return;
}
for (int i = 1; i < arr.length; i++) {
int value = a[i];
int j = i - 1;
// 查找要插入的位置并移动数据
for (; j >= 0; j--) {
if (a[j] > value) {
a[j+1] = a[j];
} else {
break;
}
}
if(j+1 != i) {
a[j+1] = value;
}
}
希尔排序
动图
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23public static void shellSort(int [] arr) {
if(arr.length <= 1) {
return;
}
int gap = 1;
while (gap < arr.length) {
gap = gap * 3 + 1;
}
while (gap > 0) {
for (int i = gap; i < arr.length; i++) {
int tmp = arr[i];
int j = i - gap;
while (j >= 0 && arr[j] > tmp) {
arr[j + gap] = arr[j];
j -= gap;
}
arr[j + gap] = tmp;
}
gap = (int) Math.floor(gap / 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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51// 归并排序算法, a是数组，n表示数组大小
public static void mergeSort(int[] a, int n) {
mergeSortInternally(a, 0, n-1);
}
// 递归调用函数
private static void mergeSortInternally(int[] a, int p, int r) {
// 递归终止条件
if (p >= r) return;
// 取p到r之间的中间位置q,防止（p+r）的和超过int类型最大值
int q = p + (r - p)/2;
// 分治递归
mergeSortInternally(a, p, q);
mergeSortInternally(a, q+1, r);
// 将A[p...q]和A[q+1...r]合并为A[p...r]
merge(a, p, q, r);
}
private static void merge(int[] a, int p, int q, int r) {
int i = p;
int j = q+1;
int k = 0; // 初始化变量i, j, k
int[] tmp = new int[r-p+1]; // 申请一个大小跟a[p...r]一样的临时数组
while (i<=q && j<=r) {
if (a[i] <= a[j]) {
tmp[k++] = a[i++]; // i++等于i:=i+1
} else {
tmp[k++] = a[j++];
}
}
// 判断哪个子数组中有剩余的数据
int start = i;
int end = q;
if (j <= r) {
start = j;
end = r;
}
// 将剩余的数据拷贝到临时数组tmp
while (start <= end) {
tmp[k++] = a[start++];
}
// 将tmp中的数组拷贝回a[p...r]
for (i = 0; i <= r-p; ++i) {
a[p+i] = tmp[i];
}
}
快速排序
动图
代码
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// 快速排序，a是数组，n表示数组的大小
public static void quickSort(int[] a, int n) {
quickSortInternally(a, 0, n-1);
}
// 快速排序递归函数，p,r为下标
private static void quickSortInternally(int[] a, int p, int r) {
if (p >= r) return;
int q = partition(a, p, r); // 获取分区点
quickSortInternally(a, p, q-1);
quickSortInternally(a, q+1, r);
}
private static int partition(int[] a, int p, int r) {
int pivot = a[r];
int i = p;
for(int j = p; j < r; ++j) {
if (a[j] < pivot) {
if (i == j) {
++i;
} else {
int tmp = a[i];
a[i++] = a[j];
a[j] = tmp;
}
}
}
int tmp = a[i];
a[i] = a[r];
a[r] = tmp;
System.out.println("i=" + i);
return i;
}
堆排序
动图
代码
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
50public class HeapSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
// 对 arr 进行拷贝，不改变参数内容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
int len = arr.length;
buildMaxHeap(arr, len);
for (int i = len - 1; i > 0; i--) {
swap(arr, 0, i);
len--;
heapify(arr, 0, len);
}
return arr;
}
private void buildMaxHeap(int[] arr, int len) {
for (int i = (int) Math.floor(len / 2); i >= 0; i--) {
heapify(arr, i, len);
}
}
private void heapify(int[] arr, int i, int len) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int largest = i;
if (left < len && arr[left] > arr[largest]) {
largest = left;
}
if (right < len && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
swap(arr, i, largest);
heapify(arr, largest, len);
}
}
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
桶排序
动图
代码
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
58public class BucketSort implements IArraySort {
private static final InsertSort insertSort = new InsertSort();
@Override
public int[] sort(int[] sourceArray) throws Exception {
// 对 arr 进行拷贝，不改变参数内容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
return bucketSort(arr, 5);
}
private int[] bucketSort(int[] arr, int bucketSize) throws Exception {
if (arr.length == 0) {
return arr;
}
int minValue = arr[0];
int maxValue = arr[0];
for (int value : arr) {
if (value < minValue) {
minValue = value;
} else if (value > maxValue) {
maxValue = value;
}
}
int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
int[][] buckets = new int[bucketCount][0];
// 利用映射函数将数据分配到各个桶中
for (int i = 0; i < arr.length; i++) {
int index = (int) Math.floor((arr[i] - minValue) / bucketSize);
buckets[index] = arrAppend(buckets[index], arr[i]);
}
int arrIndex = 0;
for (int[] bucket : buckets) {
if (bucket.length <= 0) {
continue;
}
// 对每个桶进行排序，这里使用了插入排序
bucket = insertSort.sort(bucket);
for (int value : bucket) {
arr[arrIndex++] = value;
}
}
return arr;
}
// 自动扩容，并保存数据
private int[] arrAppend(int[] arr, int value) {
arr = Arrays.copyOf(arr, arr.length + 1);
arr[arr.length - 1] = value;
return arr;
}
}
计数排序
动图
代码
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
45public class CountingSort {
// 计数排序，a是数组，n是数组大小。假设数组中存储的都是非负整数。
public static void countingSort(int[] a, int n) {
if (n <= 1) return;
// 查找数组中数据的范围
int max = a[0];
for (int i = 1; i < n; ++i) {
if (max < a[i]) {
max = a[i];
}
}
// 申请一个计数数组c，下标大小[0,max]
int[] c = new int[max + 1];
for (int i = 0; i < max + 1; ++i) {
c[i] = 0;
}
// 计算每个元素的个数，放入c中
for (int i = 0; i < n; ++i) {
c[a[i]]++;
}
// 依次累加
for (int i = 1; i < max + 1; ++i) {
c[i] = c[i-1] + c[i];
}
// 临时数组r，存储排序之后的结果
int[] r = new int[n];
// 计算排序的关键步骤了，有点难理解
for (int i = n - 1; i >= 0; --i) {
int index = c[a[i]]-1;
r[index] = a[i];
c[a[i]]--;
}
// 将结果拷贝会a数组
for (int i = 0; i < n; ++i) {
a[i] = r[i];
}
}
}
基数排序
动图
代码
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
58
59
60
61
62
63
64
65
66
67public class RadixSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
// 对 arr 进行拷贝，不改变参数内容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
int maxDigit = getMaxDigit(arr);
return radixSort(arr, maxDigit);
}
// 获取最高位数
private int getMaxDigit(int[] arr) {
int maxValue = getMaxValue(arr);
return getNumLenght(maxValue);
}
private int getMaxValue(int[] arr) {
int maxValue = arr[0];
for (int value : arr) {
if (maxValue < value) {
maxValue = value;
}
}
return maxValue;
}
protected int getNumLenght(long num) {
if (num == 0) {
return 1;
}
int lenght = 0;
for (long temp = num; temp != 0; temp /= 10) {
lenght++;
}
return lenght;
}
private int[] radixSort(int[] arr, int maxDigit) {
int mod = 10;
int dev = 1;
for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
// 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)
int[][] counter = new int[mod * 2][0];
for (int j = 0; j < arr.length; j++) {
int bucket = ((arr[j] % mod) / dev) + mod;
counter[bucket] = arrayAppend(counter[bucket], arr[j]);
}
int pos = 0;
for (int[] bucket : counter) {
for (int value : bucket) {
arr[pos++] = value;
}
}
}
return arr;
}
private int[] arrayAppend(int[] arr, int value) {
arr = Arrays.copyOf(arr, arr.length + 1);
arr[arr.length - 1] = value;
return arr;
}
}