算法——排序

引言

本文整理了常见的排序算法,方便以后查阅。算法相关的文章均收录于<算法系列文章>

排序算法

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
package bbm.sort;

/**
* 排序接口
*
* @author bbm
*/
public interface Sorter {
/**
* Sort
*
* @param nums source data
* @return sorted data
*/
int[] sort(int[] nums);

/**
* print data
*
* @param nums data
*/
default void print(int[] nums) {
for (int num : nums) {
System.out.print(num + " ");
}
System.out.println();
}
}

桶排序

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
package bbm.sort;

import java.util.LinkedList;

/**
* 前提:输入数据时均匀的独立的
* 桶排的思想是根据数据的取值范围,将它们按照从小到大的顺序分到不同的桶中,在同一个桶内的数据再进行排序
*
* 平均时间复杂度: O(n + k)
* 最差时间复杂度: O(n^2)
* 时间复杂度: O(n + k) 能优化到 O(n)
*
* @author bbm
*/
public class BucketSorter implements Sorter {
@Override
public int[] sort(int[] nums) {
LinkedList<Integer>[] buckets = new LinkedList[100000];
for (int i = 0; i < nums.length; i++) {
int bucket = nums[i] + 50000;
if (buckets[bucket] == null) {
buckets[bucket] = new LinkedList<>();
}
buckets[bucket].add(nums[i]);
}
int index = 0;
for (int i = 0; i < buckets.length; i++) {
if (buckets[i] != null) {
buckets[i].sort(Integer::compareTo);
for (int data : buckets[i]) {
nums[index++] = data;
}
}
}
return nums;
}
}

计数排序

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
package bbm.sort;

/**
* 计数排序不需要进行数组数据的大小比较,在使用该排序方法时,我们需要知道数组 nums 的数据范围,本例中我们假设-50000 <= nums[i] <= 50000
* 然后我们需要创建一个保存临时数据的数组 counts,保证对任意下标 x 都有 nums[x] = i, counts[i] = <nums 中小于 i 的元素的个数>
* 然后,我们扫描待排序的数组,根据该数 i 在 counts 数组中的记录,可以得到 nums 中小于 i 的元素个数,也就得到 i 所处的正确位置
*
* 时间复杂度: O(n + k)
* 空间复杂度: O(n + k) 能优化到 O(k)
*
* 我觉得在 counts 中没必要记录小于 i 的元素个数,只需要记录等于 i 的元素个数就够了,这时候我们只需要从左到右遍历 counts
* 每当 number = counts[index] > 0 时,只需要将 number 个 index 推入 result 数组即可,理论上它和计数排序效率差不多
* 具体参考 {@link CountingSorter#countingSort(int, int[])}
*
* @author bbm
*/
public class CountingSorter implements Sorter {

@Override
public int[] sort(int[] nums) {
if (nums == null) {
return null;
}
if (nums.length == 1) {
return nums;
}
int[] counts = new int[100000];
for (int data : nums) {
counts[data + 50000] += 1;
}
return countingSort(nums, counts);
}

private int[] countingSort(int[] nums, int[] counts) {
int[] result = new int[nums.length];
for (int i = 1; i < counts.length; i++) {
counts[i] = counts[i - 1] + counts[i];
}
for (int i = nums.length - 1; i >= 0; i--) {
result[counts[nums[i] + 50000] - 1] = nums[i];
counts[nums[i] + 50000] -= 1;
}
return result;
}

private int[] countingSort(int size, int[] counts) {
int[] result = new int[size];
int index = 0;
for (int i = 0; i < counts.length; i++) {
if (counts[i] > 0) {
for (int j = 0; j < counts[i]; j++) {
result[index++] = i - 50000;
}
}
}
return result;
}
}

堆排序

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
67
68
69
70
71
package bbm.sort;

/**
* 堆排的思想是先将数组想象成一个完全二叉树,根节点是 index=0,它的两个子节点是 index=1 和 index=2, 如下图所示
* 0
* /\
* 1 2
* /\ /\
* 3 4 5 6
* 在此基础上,我们将构建最大堆,所谓最大堆的特性是:每个节点都大于它的两个子节点,也就是说根节点是最大的数
* 建立最大堆的思路是从 length / 2 号节点开始从下往上的检查各个节点是否大于其子节点,如果发现不满足,则交换节点的数据
* 当遍历到根节点时,就完成了最大堆的建立
* 基于最大堆的特性,我们知道根节点一定是最大的节点,所以我们将根节点和数组最后一个节点交换,然后将最后一个节点排除
* 并从根节点出发重新修复剩余节点,让其满足最大堆的性质,重复上述过程直到数组被排除到只剩下一个节点时,整个数据就是有序的了
*
* 时间复杂度: O(n*log(n))
* 时间复杂度: O(1)
*
* @author bbm
*/
public class HeapSorter implements Sorter {

@Override
public int[] sort(int[] nums) {
if (nums == null) {
return null;
}
if (nums.length == 1) {
return nums;
}
buildMaxHeap(nums);
heapSort(nums);
return nums;
}

private void heapSort(int[] nums) {
for (int i = nums.length - 1; i > 0; i--) {
int temp = nums[0];
nums[0] = nums[i];
nums[i] = temp;
maxHeap(nums, i, 0);
}
}

private void buildMaxHeap(int[] nums) {
for (int i = nums.length / 2; i >= 0; i--) {
maxHeap(nums, nums.length, i);
}
}

private void maxHeap(int[] nums, int size, int index) {
int left = index * 2 + 1;
int right = index * 2 + 2;
int largest;
if (left < size && nums[left] > nums[index]) {
largest = left;
} else {
largest = index;
}
if (right < size && nums[right] > nums[largest]) {
largest = right;
}
if (largest != index) {
int temp = nums[index];
nums[index] = nums[largest];
nums[largest] = temp;
maxHeap(nums, size, largest);
}
}

}

插入排序

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
package bbm.sort;

/**
* 插入排序将数组分为左侧和右侧,认为左侧是排好序的数组(起初左侧数组只包含一个元素,即下标 0 元素),右侧是待处理的数组
* 然后从下标 1 开始处理右侧数组,将其依次与左侧数组中的每个元素进行比较,从而将其插入到合适的位置
*
* 时间复杂度: O(n^2)
* 空间复杂度: O(1)
*
* @author bbm
*/
public class InsertSorter implements Sorter {

@Override
public int[] sort(int[] nums) {
if (nums == null) {
return new int[0];
}
if (nums.length < 2) {
return nums;
}
// print(nums);
for (int i = 1; i < nums.length; i++) {
int tmp = nums[i];
for (int j = i - 1; j >= 0; j--) {
if (tmp < nums[j]) {
nums[j + 1] = nums[j];
nums[j] = tmp;
}
}
// print(nums);
}
return nums;
}
}

归并排序

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
67
68
69
70
71
72
73
74
75
76
77
78
79
package bbm.sort;

/**
* 利用分治思想,将数组平均地划分为 2 段,然后对这两段递归地再向下划分,直到每段的长度都为 1 时(长度为 1 意味着已经有序),开始进行合并
* 合并过程就是不断地从要合并的两段(有序)数组中找最小的数,然后放入一个新的排好序的数组中
*
* 时间复杂度: O(n*log(n))
* 空间复杂度: O(n)
*
* @author bbm
*/
public class MergeSorter implements Sorter {
@Override
public int[] sort(int[] nums) {
if (nums == null) {
return null;
}
if (nums.length < 2) {
return nums;
}
return sort(nums, 0, nums.length);
}

private int[] sort(int[] nums, int p, int r) {
if (p < r) {
if (r - p >= 2) {
// 当前待处理的数组长度大于 2,进行递归拆分
int q = (p + r) / 2;
sort(nums, p, q);
sort(nums, q, r);
merge(nums, p, q, r);
} else {
// 当前待处理的数组长度等于 2,直接进行合并
if (nums[p] > nums[r - 1]) {
int tmp = nums[r - 1];
nums[r - 1] = nums[p];
nums[p] = tmp;
}
}
}
return nums;
}

private void merge(int[] nums, int p, int q, int r) {
// 复制左右两个数组,复制完成后,nums 的 [p, r) 段就作为合并之后的 result 数组
int[] leftArray = subArray(nums, p, q);
int[] rightArray = subArray(nums, q, r);
int leftIndex = 0;
int rightIndex = 0;
for (int i = p; i < r; i++) {
if (leftArray.length <= leftIndex) {
// 左数组已经为空,将右数组的数据按序添加到 result 中
nums[i] = rightArray[rightIndex];
rightIndex++;
} else if (rightArray.length <= rightIndex) {
// 右数组已经为空,将左数组的数据按序添加到 result 中
nums[i] = leftArray[leftIndex];
leftIndex++;
} else if (leftArray[leftIndex] < rightArray[rightIndex]) {
// 左数组当前处理的数较小,将这个较小的数据添加到 result 中
nums[i] = leftArray[leftIndex];
leftIndex++;
} else {
// 右数组当前处理的数较小,将这个较小的数据添加到 result 中
nums[i] = rightArray[rightIndex];
rightIndex++;
}
}
}

private int[] subArray(int[] nums, int p, int q) {
int[] result = new int[q - p];
for (int i = 0; p < q; i++) {
result[i] = nums[p];
p++;
}
return result;
}
}

快速排序

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
67
68
package bbm.sort;

/**
* 快排使用了分治的思想,它每次选取要处理的数组中最厚的一个元素作为主元素,然后遍历整个数组,利用下标来将数组划分成左右两个部分
* 左部都是比主元素小的数据,右部都是比主元素大的数据,当处理完除主元素外的其他所有元素时,左部的末尾就是主元素在排好序的数组中应该处于的位置
* 也就是说每一轮上述处理过程,都将为一个主元素找到合适的位置,这个位置就是排序完成之后该元素该在的位置,很明显我们需要把主元素放到这个位置上来
* 然后递归的处理主元素左右两部分数组,直到左右数组的大小都为 1 为止
* 总结成一句话就是:每轮迭代都会为一个元素找到正确的位置
*
* 很显然,如果数组本来是逆序的,当我们选最后一个元素作为主元素时,划分出来的左部数组为空,右部数组为 size - 1,这样的话快排会退化成 O(n^2)
* 为了解决这个问题,我们可以引入随机化的过程,不是总选取最后一个节点作为主元素,而是随机选择一个元素,这样比较平衡
* 详见 {@link QuickSorter#randomPartition(int[], int, int)}
* 不过我在 LeetCode 上跑测试集发现不进行随机化反而更快,可能他们的已经足够随机化了,我们再进行随机化反而增加了消耗
*
* 平均时间复杂度: O(n*log(n))
* 最差时间复杂度: O(n^2)
* 时间复杂度: O(1)
*
* @author bbm
*/
public class QuickSorter implements Sorter {

@Override
public int[] sort(int[] nums) {
if (nums == null) {
return null;
}
if (nums.length == 1) {
return nums;
}
quickSort(nums, 0, nums.length - 1);
return nums;
}

private void quickSort(int[] nums, int p, int r) {
if (p < r) {
int q = partition(nums, p, r);
quickSort(nums, p, q - 1);
quickSort(nums, q + 1, r);
}
}

private int randomPartition(int[] nums, int p, int r) {
int i = (int) (Math.random() * (r - p)) + p;
int temp = nums[i];
nums[i] = nums[r];
nums[r] = temp;
return partition(nums, p, r);
}

private static int partition(int[] nums, int p, int r) {
int pivot = nums[r];
int leftEnd = p - 1;
for (int rightEnd = p; rightEnd < r; rightEnd++) {
if (nums[rightEnd] < pivot) {
leftEnd++;
int temp = nums[leftEnd];
nums[leftEnd] = nums[rightEnd];
nums[rightEnd] = temp;
}
}
leftEnd++;
int temp = nums[leftEnd];
nums[leftEnd] = nums[r];
nums[r] = temp;
return leftEnd;
}
}

基数排序

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
package bbm.sort;

/**
* 基数排序的思想是将数据按照 10 进制划分为多个位(这里我们假定最大数据的位数是 d = 5),然后从低位开始按照位大小进行排序
* 因为在数学中, 数位越高,数位值对数的大小的影响就越大, 所以如果我们用从高位到低位排序的话,会影响高位已经排好的大小关系
* 而从低位向高位排序的话,低位已经排好的顺序会被一直保持住,考虑 47 43 54 这三个数,按照个位排序后是 43 54 47,然后按 10 位排序时,
* 43 和 47 的顺序保持 43 47 54,而如果我们从高到低位排序时,就会变成 47 43 54,接下来我们要按个位为他们排序,就不得不将它们分成不同的组
* 因为如果分在同一组的话,按个位数排序的话会变成 43 54 47,其中 54 和 47 的大小关系被破坏
*
* 时间复杂度: O(n*k)
* 空间复杂度: O(n*k) 能优化到 O(n+k)
*
* @author bbm
*/
public class RadixSorter implements Sorter {
@Override
public int[] sort(int[] nums) {
int[][] sort = new int[20][nums.length];
for (int i = 1; i < 6; i++) {
int[] numbers = new int[20];
int mod = (int) (Math.pow(10, i));
int div = (int) (Math.pow(10, i - 1));
for (int num : nums) {
int digit = num % mod / div;
sort[digit + 10][numbers[digit + 10]] = num;
numbers[digit + 10] += 1;
}
int index = 0;
for (int k = 0; k < 20; k++) {
for (int l = 0; l < numbers[k]; l++) {
nums[index] = sort[k][l];
index++;
}
}
}
return nums;
}
}

测试代码

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
package bbm.sort;

import java.util.Arrays;
import java.util.Random;
import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertEquals;

/**
* @author bbm
*/
public class SorterTest {

@Test
public void testSort() {
Sorter sorter = new BucketSorter();
doTest(sorter);
sorter = new CountingSorter();
doTest(sorter);
sorter = new HeapSorter();
doTest(sorter);
sorter = new InsertSorter();
doTest(sorter);
sorter = new MergeSorter();
doTest(sorter);
sorter = new QuickSorter();
doTest(sorter);
sorter = new RadixSorter();
doTest(sorter);
}

private void doTest(Sorter sorter) {
int dataSize = 10000;
long time1 = 0;
long time2 = 0;
// 这里跑了很多次是为了减弱 JIT 的影响
for (int x = 0; x < 100; x++) {
int[] data = new int[dataSize];
int[] data2 = new int[dataSize];
Random rand = new Random(System.currentTimeMillis());
for (int i = 0; i < dataSize; i++) {
data[i] = rand.nextInt(dataSize);
data2[i] = data[i];
}
long start = System.currentTimeMillis();
Arrays.sort(data);
time1 += System.currentTimeMillis() - start;
start = System.currentTimeMillis();
int[] result = sorter.sort(data2);
time2 += System.currentTimeMillis() - start;
for (int i = 0; i < dataSize; i++) {
assertEquals(data[i], result[i]);
}
}
System.out.println(sorter.getClass().getSimpleName() + ": jdk speeds: " + time1 + " ms, my algorithm speeds " + time2 + " ms");
}
}

参考内容

[1] 《算法导论》
[2] 排序算法汇总

贝克街的流浪猫 wechat
您的打赏将鼓励我继续分享!
  • 本文作者: 贝克街的流浪猫
  • 本文链接: https://www.beikejiedeliulangmao.top/algorithm/sort/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!
  • 创作声明: 本文基于上述所有参考内容进行创作,其中可能涉及复制、修改或者转换,图片均来自网络,如有侵权请联系我,我会第一时间进行删除。