桶排序（Bucket Sort）

针对在固定范围的内的数据

package com.zsl.datastructalgorithm.date20220629;

import com.zsl.datastructalgorithm.date20220627.InsertSort;

import java.util.HashSet;
import java.util.Objects;
import java.util.Random;
import java.util.Set;

/**
 * 桶排序(线性排序，时间复杂度O(n))
 *          针对数据范围划分多个桶，桶之间有序，对桶内数据再排序，从而有序
 *
 * @author zsl
 * @date 2022/6/29 13:17
 * @email 249269610@qq.com
 */
public class BucketSort {

    public static void main(String[] args) {
        Random random = new Random(41);
        Set<Integer> set = new HashSet<>(2000);
        for (int i = 0; i < 2000; i++) {
            set.add(random.nextInt(10000));
        }
        ;
        Integer[] integers = set.toArray(new Integer[]{});
        int[] ints = new int[integers.length];
        for (int i = 0; i < integers.length; i++) {
            ints[i] = integers[i];
        }
        sort(ints);
        System.out.println();
    }



    /**
     * 对0-10000以内数组进行排序
     */
    public static void sort(int[] elements){
        if (elements.length < 2) return;

        bucketSort(elements);
    }

    private static void bucketSort(int[] elements) {
        // 元素个数少于100个使用插入排序
        if (elements.length < 100) {
            InsertSort.sort(elements);
        }

        // 桶排序
        Bucket[] buckets = new Bucket[10];
        for (int i = 0; i < elements.length; i++) {
            // 获取应该存储的桶位
            int bucketIndex = elements[i] / 2000;

            // 获取桶
            Bucket bucket = buckets[bucketIndex];

            // 如果桶为空就创建
            if (Objects.isNull(bucket)) {
                buckets[bucketIndex] = new Bucket();
                bucket = buckets[bucketIndex];
            }

            bucket.add(elements[i]);
        }

        int index = 0;
        // 遍历桶
        for (int i = 0; i < buckets.length; i++) {
            if (Objects.nonNull(buckets[i])) {
                // 获取桶信息
                int[] ints = buckets[i].getElements();
                int size = buckets[i].getSize();
                // 遍历桶中元素
                for (int j = 0; j < size; j++) {
                    elements[index++] = ints[j];
                }
            }
        }
    }


    /**
     * 桶对象
     */
    public static class Bucket {

        private int[] elements;
        private int size;

        public Bucket() {
            this.elements = new int[16];
            this.size = 0;
        }

        /**
         * 使用插入排序 保证桶中元素有序
         */
        public void add(int element) {
            // 扩容
            if (elements.length == size) {
                int[] dest = new int[size << 2];
                System.arraycopy(elements, 0, dest, 0, size);
                elements = dest;
            }

            int i = 0;
            // 利用插入排序
            for (; i < size; ++i) {
                // 找到要插入的位置
                if (elements[i] > element) {
                    // 先移动
                    for (int j = size; j > i; --j) {
                        elements[j] = elements[j - 1];
                    }
                    break;
                }
            }
            // 再存储
            elements[i] = element;
            ++size;
        }

        public int[] getElements() {
            return elements;
        }

        public int getSize() {
            return size;
        }
    }
}

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137

计数排序（Counting Sort）

针对种类少的数据，如年龄[0, 120]、高考成绩[0, 750]

package com.zsl.datastructalgorithm.date20220629;

import java.util.Random;

/**
 * 计数排序(线性排序，时间复杂度O(n))
 *      限制条件高，针对特定数据；如对年龄排序，假设[0, 120]都是会出现的结果，先遍历一边元素，计算每种结果的个数存储到数组中（new int[121]），
 *      再计数求和，遍历元素存储到对应的位置。
 *
 * @author zsl
 * @date 2022/6/29 13:18
 * @email 249269610@qq.com
 */
public class CountingSort {

    public static void main(String[] args) {
        Random random = new Random(41);
        int[] ints = new int[1000];
        for (int i = 0; i < 1000; i++) {
            ints[i] = random.nextInt(121);
        }

        sort(ints, 121);
        System.out.println();
    }

    public static void sort(int[] elements, int count) {
        if (elements.length < 2) return;

        countingSort(elements, count);
    }

    private static void countingSort(int[] elements, int count) {
        // 获取每个元素出现次数
        int[] counts = new int[count];
        for (int i = 0; i < elements.length; i++) {
            ++counts[elements[i]];
        }

        // 累加每个元素加上之前元素出现的次数
        for (int i = 1; i < counts.length; i++) {
            counts[i] = counts[i] + counts[i -1];
        }

        // 从后往前遍历
        int[] tmp = new int[elements.length];
        for (int i = elements.length; i > 0; --i) {
            int element = elements[i - 1];
            int index = --counts[element];
            tmp[index] = element;
        }

        // 拷贝排序好的元素
        System.arraycopy(tmp, 0, elements, 0, elements.length);
    }
}

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

基数排序（Radix Sort）

针对数据位数的，如手机号、单词

package com.zsl.datastructalgorithm.date20220629;

import com.zsl.datastructalgorithm.date20220627.InsertSort;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * 基数排序(线性排序，时间复杂度O(n))
 *      限制条件高，针对特定数据；如对11位手机号排序，通过对每位[0,9]的数字进行排序，从第1位到第11位逐渐有序，要求是稳定的。
 *
 * @author zsl
 * @date 2022/6/29 13:20
 * @email 249269610@qq.com
 */
public class RadixSort {
    static Random random = new Random(41);


    public static void main(String[] args) {
        int elementSize = 1000;

        int[] ints = new int[elementSize];
        for (int i = 0; i < elementSize; i++) {
            ints[i] = generateNumber(6);
        }

        sort(ints, 6);
        System.out.println();
    }

    /**
     * 随机生成1-6位数字
     *
     * @param maxLen 长度
     */
    public static int generateNumber(int maxLen) {
        if (maxLen > 6 || maxLen < 1) maxLen = 6;

        int num = random.nextInt(10);
        for (int i = 1; i < maxLen; i++) {
            num = num * 10 + random.nextInt(10);
        }
        return num;
    }


    public static void sort(int[] elements, int maxLen) {
        if (elements.length < 2) return;

        radixSort(elements, maxLen);
    }

    private static void radixSort(int[] elements, int maxLen) {
        if (elements.length < 100) {
            InsertSort.sort(elements);
            return;
        }

        // 构建基数桶(此处偷懒使用Java链表数据结构，充当桶结构)
        List[] base = new ArrayList[10];
        for (int i = 0; i < base.length; i++) {
            base[i] = new ArrayList<Integer>();
        }


        int remainder = 1;
        for (int i = 0; i < maxLen; i++) {
            remainder *= 10;
            radix_sort_c(elements, base, remainder);
        }
    }

    private static void radix_sort_c(int[] elements, List[] base, int remainder) {
        // 对remainder位进行排序，并存放到对应桶中
        for (int i = 0; i < elements.length; i++) {
            int index = elements[i] % remainder;

            // 缺位直接为0
            if (index < remainder / 10) index = 0;

            while (index >= 10) {
                index /= 10;
            }
            base[index].add(elements[i]);
        }

        // 拷贝到原位置
        int i = 0;
        for (List<Integer> list : base) {
            for (Integer integer : list) {
                elements[i++] = integer;
            }
            list.clear();
        }
    }
}

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

关系

• 都不是通过比较交换的排序，而是针对数据的特性进行排序
• 时间复杂度可以达到O(n)