数据结构与算法--经典10大排序算法（动图演示）【建议收藏】_数据结构排序动图

十大经典排序算法总结（动图演示）

算法分类

• 十大常见排序算法可分为两大类：
  • 比较排序算法：通过比较来决定元素的位置，由于时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序
  • 非比较类型排序：不通过比较来决定元素的相对次序，他可以突破基于比较排序的时间下限，以线性时间运行，因此也称为线性时间非比较类排序
    

相关概念

• 稳定排序：如果原数据中a在b之前，而且a=b，排序后a任然在b之前
• 不稳定排序：如果原数据中a在b之前，而且a=b，排序后a在b之后
• 时间复杂度：对排序数据的总的操作次数，反映当n变化时候，操作次数呈现出什么规律
• 空间复杂度：指算法在计算机内执行时所需要的存储空间的度量，他也是数据规模n的函数。

冒泡排序

• 冒泡排序是一种简单的排序算法，重复遍历需要排序的数列，一次比较两个元素，如果他们顺序错误就把他们交换过来。持续遍历交换直到排序完成。

算法分析

• 比较相邻元素，如果前一个比后一个大，就交换他们
• 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该就变成了最大值
• 针对所有元素重复以上步骤，除了最后一个
• 重复1~3步骤直到完成排序

动图展示

代码实现：

public class BubbleSort {
    public static int[] getArrayData(){
        int[] arrayData = new int[20];
        Random random = new Random();
        for (int i = 0; i < 20; i++) {
            arrayData[i] = random.nextInt(1000);
        }
        return arrayData;
    }

    /**
     * 时间复杂度 O(n^2) 空间复杂度O(1)
     * 从小到大排序冒泡排序
     * */
    public static int[] bubbleSort(int[] arrayData){
        if(null == arrayData || arrayData.length <= 1){
            return arrayData;
        }
         for (int i = 0; i < arrayData.length; i++) {
            for (int j = 0; j < arrayData.length - 1; j++) {
                if(arrayData[j] > arrayData[i]){
                    int temp = arrayData[j];
                    arrayData[j] = arrayData[i];
                    arrayData[i] = temp;
                }
            }
        }
        return arrayData;
    }

    public static void main(String[] args) {
        int[] arrayData = bubbleSort(getArrayData());
        for (int i = 0; i < arrayData.length; i++) {
            System.out.println(arrayData[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

选择排序

• 选择排序（selection sort）是一种简单的比较容易理解的算法，工作原理：在未排序的数列中找到最小的一个，将他的位置所在数据与数列首位交换，接着从生下未排序的元素中继续找最小的元素和第二个交换，直到数列末尾。

算法分析

• n个数据的数列排序经过n-1次查找可以完成排序
• 第i（0 <= i < n）次排序，默认数据第i个数据是最小的数据，从第i个数据开始遍历数列
• 如果发现有比第i个数据更小的数据 j，记录位置 j，将最小的数据更换成第j个，持续遍历查找到 第i个数据后最小的数据 j
• 将数列中第j个数据与第 i个数据进行交换
• 同样，的步骤对 第 i+1 个数据进行处理，直到第n-1 个数据。

动图演示

代码实现

public class BubbleSort {
    public static int[] getArrayData(){
        int[] arrayData = new int[20];
        Random random = new Random();
        for (int i = 0; i < 20; i++) {
            arrayData[i] = random.nextInt(1000);
        }
        return arrayData;
    }

    /**
     * 时间复杂度 O(n^2) 空间复杂度O(1)
     * 从小到大选择排序
     * */
    public static int[] selectionSort(int[] arrayData){
        if(null == arrayData || arrayData.length <=1){
            return arrayData;
        }
        for (int i = 0; i < arrayData.length; i++) {
            int last = arrayData[i];
            int position = i;
            for (int j = i+1; j < arrayData.length; j++) {
                if(last > arrayData[j]){
                    last = arrayData[j];
                    position = j;
                }
            }
            int temp = arrayData[i];
            arrayData[i] = arrayData[position];
            arrayData[position] = temp;
        }
        return arrayData;
    }

    public static void main(String[] args) {
        int[] arrayData = selectionSort(getArrayData());
        for (int i = 0; i < arrayData.length; i++) {
            System.out.println(arrayData[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

特点

• 选择排序是最稳定的排序算法之一，因为无论什么数据进去时间复杂度都是O(n^2)。所以用它的时候数据规模越小越好。唯一的好处是不额外占用内存，空间复杂度O(1)，理论上选择排序可能也是凭虚最容易理解的排序算法。

插入排序

• 插入排序算法工作原理是通过构建有序序列，对于未排序的数据，在一家排序序列中从后向前扫描，找到相应位置插入。也可以逐步移动到对应位置

算法分析

• 从第一个元素开始，此元素我们看成已经有序的，我们认为第一二个数据已经有序
• 取下一个元素，此处是第三元素，和之前有序列中的数据从后先前比较
• 如果已排序的改元素大于新元素，将这个元素移动到下一个位置
• 重复上这个步骤，直到找到一家排序的元素小于或者等于新元素的位置
• 建新元素插入到该位置的后面的空位上（上一步的数据交换已经完成这部操作）
• 重复以上2~5 步骤

动图演示

代码实现

public class BubbleSort {
    public static int[] getArrayData(){
        int[] arrayData = new int[20];
        Random random = new Random();
        for (int i = 0; i < 20; i++) {
            arrayData[i] = random.nextInt(1000);
        }
        return arrayData;
    }

    /**
     * 时间复杂度 O(n^2) 空间复杂度O(1)
     * 从小到大插入排序
     * */
    public static int[] insertionSort(int[] arrayData){
        if(null == arrayData || arrayData.length <= 1){
            return arrayData;
        }
         for (int i = 1; i < arrayData.length; i++) {
            for (int j = i; j > 0; j--) {
                if(arrayData[j-1] > arrayData[j]){
                    int temp = arrayData[j-1];
                    arrayData[j-1] = arrayData[j];
                    arrayData[j] = temp;
                }
            }
        }
        return arrayData;
    }

    public static void main(String[] args) {
        int[] arrayData = insertionSort(getArrayData());
        for (int i = 0; i < arrayData.length; i++) {
            System.out.println(arrayData[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

希尔排序

• 1959年shell发明的，第一个突破O(n^2)的一个排序算法，是简单插入排序的改进版本。他原插入排序不同在于，会分组进行比较，并且优先比较距离较远的元素。希尔排序又称为缩小增量排序。

算法分析

• 先将整个待排序的记录序列分割成若干子序列，并分别对子序列进行直接插入排序，具体分析如下
• 选择一个增量规则，将整个序列分成t1,t2，t3…tk，其中ti > tj，tk=1.
• 按照增量个数k，对序列进行k次遍历排序
• 每次排序，更具对应的增量ti，将待排序的序列分隔成若干个长度的m的子序列
• 分别对每个子序列进行直接插入排序，仅仅存在增量是1 的时候，整个序列作为一个整体子序列来处理，表长度就等于整个序列长度
• EX：此处比较绕，举个案例，长度为10的数列
  • 分组方法每次对半分组，第一次10/2 = 5 组，分别为：（0，5），（1，6），（2，7），（3，8），（4，9）
  • 接着第二次在对半分5/2 = 2组，分别为：（0，2，4，6，8），（1，3，5，7，9）
  • 第三次继续对半分2/2=1组：0，1，2，3，4，5，6，7，8，9
  • 每一次分组都将对各个组进行选择插入排序，得到最终结果

动图说明

代码实现

public class BubbleSort {
    public static int[] getArrayData(){
        int[] arrayData = new int[20];
        Random random = new Random();
        for (int i = 0; i < 20; i++) {
            arrayData[i] = random.nextInt(1000);
        }
        return arrayData;
    }

    /**
     * 时间复杂度评价 O(nlog2n) 空间复杂度O(1)
     * 从小到大希尔排序
     * */
    public static int[] shellSort(int[] arrayData){
        if(null == arrayData || arrayData.length <= 1){
            return arrayData;
        }
        for (int gap = arrayData.length/2; gap > 0 ;  ; gap/=2) {
            for (int i =gap; i<arrayData.length; i++){
             //此处i 在分组的第一组数据的最后一个数据 i+1 第二组，i+2第三组，依次类推
                //此处j 从该分组数据的最后一个数据向前遍历，遇到更大的值就交换
                // （用gap来区分分组，与插入排序一模一样，只不过简单插入排序间隔是i--，此处是i-=gap）
                for(int j = i;j-gap>=0;j-=gap){
                    if(arrayData[j-gap] > arrayData[j]){
                        int temp = arrayData[j];
                        arrayData[j] = arrayData[j-gap];
                        arrayData[j-gap] = temp;
                    }
                }
            }
        }
        return arrayData;
    }


    public static void main(String[] args) {
        int[] arrayData = shellSort(getArrayData());
        for (int i = 0; i < arrayData.length; i++) {
            System.out.println(arrayData[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

时间复杂度说明

• 希尔排序的核心在于间隔序列的设定，即可以提前设定好间隔序列，也可以动态定义间隔序列。
• 希尔排序执行时间依赖于对得到的序列的排序，取决于需要分组的多少,所以时间复杂度情况如下：
  • 最好情况：序列是正序排序，这种情况，需要进行的比较次数是n-1次。后移赋值操作为0 次，即O（n）
  • 最坏情况：O（nlog2n）
  • 平均时间复杂度：O（nlog2n）

归并排序

• 归并排序是建立在归并操作的基础上的一种有效的排序算法。算法核心是采用分治思想（Divide and conquer）的一个非常典型的应用。将已经有的子序列排序后合并，得到完全有序的序列，即先使每个子序列有序，在使子序列段间有序。若两个有序表合并成一个有序表，称为2-路归并

算法分析

• 吧长度为n的输入序列分为两个长度为n/2的子序列
• 对每个子序列分表采用归并排序（递归）直到序列长度足够小（>2）
• 将两个子序列排序好，并将两个子序列合并成一个最终序列

动图演示

代码实现

public class BubbleSort {
    public static int[] getArrayData(int size) {
        int[] arrayData = new int[size];
        Random random = new Random();
        for (int i = 0; i < size; i++) {
            arrayData[i] = random.nextInt(1000);
        }
        return arrayData;
    }

    /**
     * 时间复杂度O(nlogn) 空间复杂度O(n)
     * 从小到大，归并排序
     */
    public static int[] mergeSort(int[] arrayData) {
        if (null == arrayData || arrayData.length <= 1) {
            return arrayData;
        }
        //此处优化20210309
        if (arrayData.length <= 2) {
            return arrayData;
        }
        int middle = arrayData.length / 2;
        int[] left = Arrays.copyOfRange(arrayData, 0, middle);
        int[] right = Arrays.copyOfRange(arrayData, middle, arrayData.length);
        return merge(mergeSort(left), mergeSort(right));
    }

    public static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        //此处优化，不用冒泡排，基础情况只会存在2个元素，无需冒泡排序直接交换
        if (left.length == 2) {
            if (left[0] > left[1]) {
                int temp = left[0];
                left[0] = left[1];
                left[1] = temp;
            }

        }
        if (right.length == 2) {
            if (right[0] > right[1]) {
                int temp = right[0];
                right[0] = right[1];
                right[1] = temp;
            }
        }
        int leftPosition = left.length - 1;
        int rightPosition = right.length - 1;
        int resultPosition = result.length - 1;
        while (resultPosition >= 0) {
            if (rightPosition < 0 || (leftPosition >= 0 && left[leftPosition] > right[rightPosition])) {
                result[resultPosition--] = left[leftPosition--];
            } else {
                result[resultPosition--] = right[rightPosition--];
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] arrayData = mergeSort(getArrayData(20));
        for (int i = 0; i < arrayData.length; i++) {
            System.out.println(arrayData[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

算法总结

• 归并排序是一种稳定的排序。和选择排序一样，归并排序性能不受输入数据的影响，但是表现比选择排序要好得多，因为始终都是O(nlogn)的时间复杂度。代价是需要额外的内存空间。

快速排序

• 快速排序基本思想：通过一次排序将待排序的记录隔开成两个数列，数列中前部分数据比基准值小（或大），数列中后部分数据比基准值大（或小），则接下来继续对这两部分数列进行快速排序，直到整个序列有序。

算法分析

• 快速排序使用分治法吧一个数列（list）分为两个字数列（subList）。具体分析如下
• 从数列中跳出一个元素，称为基准值privot，我们默认每次将数列第一个数据作为基准值
• 此处用挖坑填写数据的方式将数据中小于 privot的数据放到数列左边，将数据大于privot的数据放到基准值右边，过程如下
  • 记起始，结束为止分别为left，right，基准值privot=left
  • 从right向前遍历找小于基准值的数据放到当前left位置
  • 从left向后遍历找大于基准值的数据，放到right位置，
  • 当left == right时候，将之前的privot数据放入left位置， 记当前位置temp
• 将原数量分为两个子数列：left~ temp-1，temp+1~right
• 递归得到有序数列

动图演示

代码实现

public class BubbleSort {
    public static int[] getArrayData(int size) {
        int[] arrayData = new int[size];
        Random random = new Random();
        for (int i = 0; i < size; i++) {
            arrayData[i] = random.nextInt(1000);
        }
        return arrayData;
    }

    /**
     * 时间复杂度平均O(nlog2^n) 空间复杂度O(nlog2^n)
     * 从小到大快速排序
     * */
    public static int[] quickSort(int[] arrayData) {
        if (null == arrayData || arrayData.length <= 1) {
            return arrayData;
        }
        quickSort(arrayData, 0, arrayData.length - 1);
        return arrayData;
    }

    public static void quickSort(int[] arrayData, int left, int right){
        if(left < right){
            int temp = swap2(arrayData, left, right);
            quickSort(arrayData, left, temp -1);
            quickSort(arrayData, temp +1, right);
        }
    }

    public static int swap2(int[] arrayData, int left, int right) {
        if(left < right){
            int positionData = arrayData[left];
            while (left < right){
                //从后先前找一个小于基准值positionData的数据
               while (right > left && arrayData[right] > positionData){
                   right --;
               }
               if(left < right){
                   arrayData[left] = arrayData[right];
                   left ++;
               }
               //从前向后找一个大于基准值的数据
               while (left < right && arrayData[left] < positionData){
                   left ++;
               }
               if(left < right){
                   arrayData[right] = arrayData[left];
                   right --;
               }
            }
            arrayData[left] = positionData;
        }
        return left;
    }

    public static void main(String[] args) {
        int[] beginArrayData = getArrayData(10);
        int[] arrayData = quickSort(beginArrayData);
        for (int i = 0; i < arrayData.length; i++) {
            System.out.println(arrayData[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

计数排序

• 计数排序不是基于比较的排序算法，核心在于输入的数据转换为键值存储在额外的空间中，作为线性时间复杂度的排序，计数排序要求输入的数据必须是有明确的范围的整数。

算法分析

• 找出数列中最大元素，最小元素
• 统计数组中最每个元素值的个数，并且存储到数组C的第i项（例如21这个数字出现两次，则C[21] = 2）
• 记录原数组初始位置position=0，从头遍历新数组C
• 当C元素为n ，将C下标存储到position位置，position向前增加一位，重复执行n次
• 得到最终有序数列

动图演示

public class BubbleSort {
    public static int[] getArrayData(int size) {
        int[] arrayData = new int[size];
        Random random = new Random();
        for (int i = 0; i < size; i++) {
            int temp = random.nextInt(100);
            if(temp > 100){
                arrayData[i] = temp;
            }else {
                int value = temp - 2*temp;
                arrayData[i] = value;
            }

        }
        return arrayData;
    }

    /**
     * 时间复杂度O(n+k), 空间复杂度O(n+k)
     * @author: liaojiamin
     * 从小到大计数排序
     */
    public static int[] countSortCompaNegative(int[] arrayData) {
        if (null == arrayData || arrayData.length <= 1) {
            return arrayData;
        }
        int minValue = arrayData[0];
        int maxvalue = arrayData[0];
        for (int i = 0; i < arrayData.length; i++) {
            if (arrayData[i] > maxvalue) {
                maxvalue = arrayData[i];
            }
            if (arrayData[i] < minValue) {
                minValue = arrayData[i];
            }
        }
        //全正数情况
        if (minValue >= 0) {
            return countSort(arrayData, maxvalue, false);
        }
        //全负数情况
        if (maxvalue <= 0) {
            return countSort(arrayData, Math.abs(minValue), true);
        }
        //正负兼有情况
        return countSortAll(arrayData, minValue, maxvalue);
    }

    public static int[] countSortAll(int[] arrayData, int minValue, int maxvalue){
        int[] nagative = new int[Math.abs(minValue) + 1];
        int[] positive = new int[maxvalue + 1];
        for (int i = 0; i < arrayData.length; i++) {
            if (arrayData[i] > 0) {
                int temp = positive[arrayData[i]];
                temp += 1;
                positive[arrayData[i]] = temp;
            } else {
                int nagativePosition = Math.abs(arrayData[i]);
                int temp = nagative[nagativePosition];
                temp += 1;
                nagative[nagativePosition] = temp;
            }
        }
        int position = 0;
        for (int i = nagative.length - 1; i >= 0; i--) {
            if(nagative[i] > 0){
                for (int j = 0; j < nagative[i]; j++) {
                    int value = i-2*i;
                    arrayData[position++] = value;
                }
            }
        }
        for (int i = 0; i < positive.length; i++) {
            if(positive[i] > 0){
                for (int j = 0; j < positive[i]; j++) {
                    arrayData[position ++] = i;
                }
            }
        }
        return arrayData;
    }

    public static int[] countSort(int[] arrayData, int maxValue, boolean isNegative) {
        if (null == arrayData || arrayData.length <= 1) {
            return arrayData;
        }
        int[] countArray = new int[maxValue + 1];
        for (int i = 0; i < arrayData.length; i++) {
            int value = Math.abs(arrayData[i]);
            int temp = countArray[value];
            temp += 1;
            countArray[value] = temp;
        }
        int position = 0;
        if (isNegative) {
            position = arrayData.length - 1;
        } else {
            position = 0;
        }
        for (int i = 0; i < countArray.length; i++) {
            if (countArray[i] > 0) {
                for (int j = 0; j < countArray[i]; j++) {
                    if (isNegative) {
                        //负数
                        int value = i-2*i;
                        arrayData[position--] = value;
                    } else {
                        arrayData[position++] = i;
                    }
                }
            }
        }
        return arrayData;
    }


  
    public static void main(String[] args) {
        int[] beginArrayData = getArrayData(20);
        int[] arrayData = countSortCompaNegative(beginArrayData);
        for (int i = 0; i < arrayData.length; i++) {
            System.out.println(arrayData[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
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

算法分析

• 以上算法分析以及 动图演示仅针对于全正数情况，以此类推，全负数，正负兼有的情况如代码实现，思想一致，归类的时候有一点不同
• 计数排序是一个稳定的排序算法，当输入的元素是n个0 到k 之间的证书时候，时间复杂度是O(n+k)，空间复杂度也是O(n+k)，排序速度比任何比较排序都要快。当k不是很大并且序列比较集中时候，计数排序是一个很有效的排序算法。

桶排序

• 桶排序是计数排序的升级版本，利用函数映射相关的思想，高效性取决于映射函数的确定，桶排序的工作原：假设需排序的数据基于均匀分配的一个区间的数据，将数据通过固定的算法分配到有限数量的桶中，每个桶在分别排序

算法分析

• 设置一个定量的数组当做空桶
• 遍历需待排序数列，得到min， max，通过（max- min）/bucksize +1,得到每个桶最多可能会容纳的个数（与你选取的hash算法有关系）
• 遍历待排序队列，将数据公共上面的算法一个一个放入桶中
• 对每个不是空桶中的数据信息排序
• 从不是空的桶中将数据按顺序取出，得到最终排序数据。

图片演示

代码实现

public static int[] getArrayData(int size) {
        int[] arrayData = new int[size];
        Random random = new Random();
        for (int i = 0; i < size; i++) {
            int temp = random.nextInt(100);
            if(temp > 0){
                arrayData[i] = temp;
            }else {
                int value = temp - 2*temp;
                arrayData[i] = value;
            }

        }
        return arrayData;
    }
/**
     * 时间复杂度O(n), 空间复杂度O(n+k)
     * 从小到大通排序
     * @author: liaojiamin
     * @date: 18:09 2020/11/16
     */
    public static int[] bucketSort(int[] arrayData){
        if (null == arrayData || arrayData.length <= 1) {
            return arrayData;
        }
        int pos = arrayData.length;
        //默认十个桶
        int bucketSize = 10;
        if(pos  <= 1){
            return arrayData;
        }
        int min = arrayData[0];
        int max = arrayData[0];
        for (int i = 0; i < pos; i++) {
            if(arrayData[i] < min){
                min = arrayData[i];
            }
            if(arrayData[i] > max){
                max = arrayData[i];
            }
        }
        int bucketCount = (max - min)/bucketSize + 1;
        //二维数组以为标识桶， 二维存放数字，最差情况所有数字在统一个桶中
        int[][] bucket = new int[bucketCount][pos];
        //统计最终桶中数据个数，做游标position作用，指定改桶下一个数据存放位置
        int[] index = new int[bucketCount];
        for (int i = 0; i < pos; i++) {
            int num = (arrayData[i] - min)/bucketSize ;
            //将 第num个桶的第index[index] 个数赋值
            bucket[num][index[num]++] = arrayData[i];
        }
        int position = 0;
        for (int i = 0; i < bucket.length; i++) {
            //对每一个进行插入排序
           insertionSort(bucket[i]);
            for (int j = bucket[i].length - index[i]; j < bucket[i].length; j++) {
                arrayData[position++] = bucket[i][j];
            }
        }
        return arrayData;

    }
/**
     * 时间复杂度 O(n^2) 空间复杂度O(1)
     * 从小到大插入排序
     */
    public static int[] insertionSort(int[] arrayData) {
        if (null == arrayData || arrayData.length <= 1) {
            return arrayData;
        }
        for (int i = 1; i < arrayData.length; i++) {
            for (int j = i; j > 0; j--) {
                if (arrayData[j - 1] > arrayData[j]) {
                    int temp = arrayData[j - 1];
                    arrayData[j - 1] = arrayData[j];
                    arrayData[j] = temp;
                }
            }
        }
        return arrayData;
    }
     public static void main(String[] args) {
        int[] beginArrayData = getArrayData(10);
        int[] arrayData = bucketSort(beginArrayData);
        for (int i = 0; i < arrayData.length; i++) {
            System.out.println(arrayData[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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

算法分析

• 桶排序最好情况下线性时间O(n)，桶排序的时间复杂度取决于对各个桶之间数据进行排序的时间复杂度，因为其他部分时间福再度就是O(n)，很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也就越少，但相应的空间消耗就越大。

基数排序

• 基数排序按照低位先排序，然后手机，接着高位在排序，在收集，依次类推，直到最高位。有时候有些属性是有优先顺序的，先按低优先级排序，最后的次序就是最高优先级高的在前面，高优先级相同的低优先级高的在前面。

算法分析

• 去的数组中最大数，并取得改数字的位数
• 申请新存储空间，二维数组，一维当做桶的位置，二维存储改桶的数字
• 遍历目标数列，最低位个位情况：将每个数字通过 取模，再取余得到他所在低位桶位置 （(key%10)/1）
• 将桶中数字依次遍历读取到目标数列中当成新的数量，
• 高位依次类推，继续执行第三，第四步骤，直到最高位，得到有序数列。

图片演示

代码实现

public static int[] getArrayData(int size) {
        int[] arrayData = new int[size];
        Random random = new Random();
        for (int i = 0; i < size; i++) {
            int temp = random.nextInt(100);
            if (temp > 0) {
                arrayData[i] = temp;
            } else {
                int value = temp - 2 * temp;
                arrayData[i] = value;
            }

        }
        return arrayData;
    }
    
 /**  
 *	时间复杂度 O(N*k) 空间复杂度O(N+k)
  * @author: liaojiamin
  * @description: 从小到大基数排序
  */
    public static int[] radixSort(int[] arrayData) {
        if (null == arrayData || arrayData.length <= 1) {
            return arrayData;
        }
        int max = arrayData[0];
        for (int i = 0; i < arrayData.length; i++) {
            if (arrayData[i] > max) {
                max = arrayData[i];
            }
        }
        int temp = max;
        int maxDigit = 0;
        int i = 10;
        while (temp > 0) {
            temp /= i;
            i *= 10;
            maxDigit++;
        }
        int mod = 10;
        int dev = 1;
        for (int j = 0; j < maxDigit; j++, dev *= 10, mod *= 10) {
            //这个地方可以优化，先获取最大桶的大小，就可以不用每个桶都arrayData.length
            int[][] tempArray = new int[10][arrayData.length];
            int[] tempIndex = new int[10];
            for (int k = 0; k < arrayData.length; k++) {
                int bucket = (arrayData[k]%mod)/dev;
                if(arrayData[k] > 0){
                    tempArray[bucket][tempIndex[bucket]++] = arrayData[k];
                }else {
                    tempArray[bucket][tempIndex[bucket]++] = -1;
                }
            }
            int index = 0;
            for (int s = 0; s < tempIndex.length; s++) {
                if (tempIndex[s] <= 0){
                    continue;
                }
                for (int i1 = 0; i1 < tempIndex[s]; i1++) {
                    if( tempArray[s][i1] > 0){
                        arrayData[index] = tempArray[s][i1];
                    }else {
                        arrayData[index] = 0;
                    }
                    index++;
                }
            }
        }
        return arrayData;
    }

 public static void main(String[] args) {
        int[] beginArrayData = getArrayData(20);
        int[] arrayData = radixSort(beginArrayData);
        for (int i = 0; i < arrayData.length; i++) {
            System.out.println(arrayData[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
67
68
69
70
71
72
73
74
75
76
77
78

算法分析

• 基数排序基于对各数据的每一位分别排序，分别收集，所以是稳定的。当基数排序的性能比桶排序略差，每次关键字的桶都需要O(n)的时间复杂度，而且分配之后得到新的关键字序列又要O(n)时间复杂度，所以时间复杂度取决于最大数据 是 k位，数据总量N因此得出时间复杂度O(2NK)。假如待排序数据可以分为d个关键字（最大d位），则基数排序的时间复杂度将是O(d2n)，当然d要远远小于n，因此基本上还是线性级别
• 基数排序的空间复杂度O(n+k)，其中k为桶的个数，一般n >> k，因此额外空间需要大概N个左右

上一篇：数据结构与算法–字符串：字符串替换
下一篇：数据结构与算法–简单栈实现及其应用