排序算法
归并排序
稳定的nlogn排序算法,每次将区间分为两半，分别进行排序最后进行合并。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| void mergeSort(int l, int r) {
if (l >= r) return;
int mid = l + r >> 1;
mergeSort(l, mid);
mergeSort(mid + 1, r);
merge(l, mid, r);
}
void merge(int l, int m, int r) {
int s = l;
int j = m + 1;
int idx = l;
while (l <= m && j <= r) {
if (arr0[l] <= arr0[j]) arr1[idx++] = arr0[l++];
else arr1[idx++] = arr0[j++];
}
while (l <= m) arr1[idx++] = arr0[l++];
while (j <= r) arr1[idx++] = arr0[j++];
if (r + 1 - s >= 0) System.arraycopy(arr1, s, arr0, s, r + 1 - s);
}
|
希尔排序
插入排序的升级版,时间复杂度比插入排序低。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| void shellSort(int[] arr) {
int grep = arr.length;
while (grep > 1) {
grep /= 2;
for (int i = 0; i < arr.length; i++) {
int v = arr[i];
int j = i;
while (j - grep >= 0 && arr[j - grep] >= v) {
arr[j] = arr[j - grep];
j -= grep;
}
arr[j] = v;
}
}
}
|
快速排序
根据pivot来进行x次交换,pivot最好随机,期望时间复杂度nlogn
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| void quickSort(int[] arr, int l, int r) {
if (l >= r) return;
int i = l - 1, j = r + 1;
int pivot = arr[i + j >> 1];
while (i < j) {
do i++; while (arr[i] < pivot);
do j--; while (arr[j] > pivot);
if (i < j) {
arr[i] ^= arr[j];
arr[j] ^= arr[i];
arr[i] ^= arr[j];
}
}
quickSort(arr, l, j);
quickSort(arr, j + 1, r);
}
|
冒泡排序
1
2
3
4
5
6
7
8
9
10
11
12
| void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (arr[i] > arr[j]) {
arr[i] ^= arr[j];
arr[j] ^= arr[i];
arr[i] ^= arr[j];
}
}
}
}
|
选择排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| void selectSort(int[] arr) {
for (int i = 0; i < n - 1; i++) {
int minValue = arr[i];
int idx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < minValue) {
idx = j;
minValue = arr[j];
}
}
if (idx != i) {
arr[i] ^= arr[idx];
arr[idx] ^= arr[i];
arr[i] ^= arr[idx];
}
}
}
|
插入排序
1
2
3
4
5
6
7
8
| void insertSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n; i++) {
int j = i, v = arr[i];
while (j - 1 >= 0 && arr[j - 1] > v) arr[j] = arr[--j];
arr[j] = v;
}
}
|
堆排序
核心函数down(),根据堆的结构比较好想,heapify()时间复杂度证明比较难:用等比数列求和进行证明。
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
| static class HeapSort {
int[] arr;
int n;
HeapSort(int[] _arr) {
n = _arr.length;
arr = new int[n + 1];
System.arraycopy(_arr, 0, arr, 1, n);
}
void heapify() {
for (int i = n / 2; i > 0 ; i--) {
down(i);
}
}
void down(int idx) {
int ls = idx * 2, rs = idx * 2 + 1;
int os = idx;
if (ls <= n && arr[ls] < arr[os]) os = ls;
if (rs <= n && arr[rs] < arr[os]) os = rs;
if (os != idx) {
arr[os] ^= arr[idx];
arr[idx] ^= arr[os];
arr[os] ^= arr[idx];
down(os);
}
}
int poll() {
int res = arr[1];
arr[1] = arr[n--];
down(1);
return res;
}
}
|
计数排序
不能处理负数,如果有负数就得加偏移量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| void countSort(int[] arr) {
int n = arr.length;
Integer[] array = new Integer[1000];
for (var e : arr) {
if (array[e] == null) array[e] = 1;
else array[e] += 1;
}
int idx = 0;
for (int i = 0; i < 1000; i++) {
if (array[i] != null) {
int cnt = array[i];
while (cnt-- > 0) arr[idx++] = i;
}
}
}
|
桶排序
根据数据范围,和数据数量确定每个桶的size，再进而确定需要多少个桶,通过通用公式计算每个数所在桶,再对每个桶单独排序,最后合并起来就是排序好的结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| void bucketSort(int[] arr) {
int min = 0x3f3f3f3f, max = -min;
for(var e : arr) {
min = Math.min(min, e);
max = Math.max(max, e);
}
int bucketSize = (max - min) / arr.length + 1;
int bucketCount = (max - min) / bucketSize + 1;
List<Integer>[] lists = new ArrayList[bucketCount];
Arrays.setAll(lists, e -> new ArrayList<>());
for (var e : arr) {
lists[(e - min) / bucketSize].add(e);
}
for (var list : lists) list.sort(Comparator.comparing(e -> e));
int idx = 0;
for (int i = 0; i < bucketCount; i++) {
for (var e : lists[i])
arr[idx++] = e;
}
}
|
基数排序
核心思想: 用0~9表示位上面的数,总共10个桶,遍历maxLen次,每次遍历当前位,将每个数放到自己值的位置。时间复杂度稳定O(k * n),不能处理负数,如果有负数就得加偏移量。
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
| void radixSort(int[] arr) {
LinkedList<Integer>[] lists = new LinkedList[10];
Arrays.setAll(lists, e -> new LinkedList<>());
int maxLen = -1;
for (var e : arr) maxLen = Math.max(getLength(e), maxLen);
for (int i = 1; i <= maxLen; i++) {
for (var e : arr) lists[getIndexValue(i, e)].add(e);
int idx = 0;
for (var list : lists) {
while (!list.isEmpty()) {
arr[idx++] = list.poll();
}
}
}
}
int getLength(int num) {
int ans = 0;
while (num > 0) {
num /= 10;
ans++;
}
return ans;
}
int getIndexValue(int k, int num) {
int res = num % 10;
for (int i = 0; i < k; i++) {
res = num % 10;
num /= 10;
}
return res;
}
|