友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
排序
.4. 快速排序
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
/**
* 快速排序，参考《算法·第4版》
*
* @author D瓜哥 · https://www.diguage.com
* @since 2025-10-16 11:27:33
*/
public void quickSort(Comparable[] array) {
sort(array, 0, array.length - 1);
}
private void sort(Comparable[] array, int lo, int hi) {
if (lo >= hi) {
return;
}
int j = partition(array, lo, hi);
sort(array, lo, j - 1);
sort(array, j + 1, hi);
}
private int partition(Comparable[] array, int lo, int hi) {
int i = lo, j = hi + 1;
Comparable v = array[lo];
while (true) {
while (array[++i].compareTo(v) < 0) {
if (i == hi) {
break;
}
}
while (v.compareTo(array[--j]) < 0) {
if (j == lo) {
break;
}
}
if (i >= j) {
break;
}
swap(array, i, j);
}
swap(array, lo, j);
return j;
}
private void swap(Comparable[] array, int i, int j) {
Comparable temp = array[i];
array[i] = array[j];
array[j] = temp;
}
| 快速排序！背也要背下来！！！！ |
.5. 归并排序
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
/**
* 数组：归并排序
*
* @author D瓜哥 · https://www.diguage.com
* @since 2025-11-03 20:51:11
*/
public void mergeSort(Comparable[] array) {
sort(array, 0, array.length - 1);
}
private void sort(Comparable[] array, int low, int high) {
if (low >= high) {
return;
}
int mid = low + (high - low) / 2;
sort(array, low, mid);
sort(array, mid + 1, high);
merge(array, low, mid, high);
}
private void merge(Comparable[] array, int low, int mid, int high) {
Comparable[] temp = new Comparable[high - low + 1];
int i = low, j = mid + 1, k = 0;
for (; k < temp.length && i <= mid && j <= high; k++) {
if (array[i].compareTo(array[j]) <= 0) {
temp[k] = array[i++];
} else {
temp[k] = array[j++];
}
}
// 只需要拷贝前半截剩余部分
if (i <= mid) {
int length = temp.length - k;
System.arraycopy(array, i, temp, k, length);
k += length;
}
// 后半截剩余部分不需要拷贝
System.arraycopy(temp, 0, array, low, k);
}
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
/**
* 链表：归并排序
*
* @author D瓜哥 · https://www.diguage.com
* @since 2025-11-03 21:17:41
*/
public ListNode mergeSort(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode mid = findMid(head);
ListNode left = mergeSort(head);
ListNode right = mergeSort(mid);
return merge(left, right);
}
private ListNode findMid(ListNode head) {
ListNode pre = head, slow = head, fast = head;
while (fast != null && fast.next != null) {
pre = slow;
slow = slow.next;
fast = fast.next.next;
}
pre.next = null;
return slow;
}
private ListNode merge(ListNode left, ListNode right) {
ListNode dummy = new ListNode();
ListNode curr = dummy;
while (left != null && right != null) {
if (left.val < right.val) {
curr.next = left;
left = left.next;
} else {
curr.next = right;
right = right.next;
}
curr = curr.next;
}
curr.next = left != null ? left : right;
return dummy.next;
}
.10. 基数排序
基数排序通过从低位到高位，对数字的每一位进行排序来获得排序结果。比较适合数量不多，但是每个数字之间相差很大的情况。而且时间复杂度是 \(O(nk)\)，n 表示数量， k 表示最大位数。
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
/**
* 基数排序
*
* @author D瓜哥 · https://www.diguage.com
* @since 2025-06-29 15:45:01
*/
public void radixSort(int[] array) {
if (null == array || array.length < 2) {
return;
}
int max = Arrays.stream(array).max().orElse(0);
int length = array.length;
for (int exp = 1; exp < max; exp *= 10) {
int[] counter = new int[10];
for (int num : array) {
// 获取指定位的值
int digit = (num / exp) % 10;
counter[digit]++;
}
// 将数量从小向大汇总，
// 稍作处理即可映射出每个数字应该存储的坐标
for (int i = 1; i < 10; i++) {
counter[i] += counter[i - 1];
}
// 存储临时结果
int[] temp = new int[length];
for (int i = length - 1; i >= 0; i--) {
int digit = (array[i] / exp) % 10;
// counter[digit] 是一个数量统计，-1 是指向应该存储的坐标
int index = counter[digit] - 1;
temp[index] = array[i];
counter[digit]--;
}
for (int i = 0; i < length; i++) {
array[i] = temp[i];
}
}
}