Radix sort is a non-comparative sorting algorithm. It avoids comparison by creating and distributing elements into buckets according to their radix. For elements with more than one significant digit, this bucketing process is repeated for each digit, while preserving the ordering of the prior step, until all digits have been considered. For this reason, radix sort has also been called bucket sort and digital sort.
前言 基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的稳定性排序法。
基数排序 基数排序(桶排序)介绍:
1)基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是通过键值的各个位的值,将要排序的元素分配至某些“桶”中,达到排序的作用; 2)基数排序法是属于稳定性的排序,基数排序法的是效率高的稳定性排序法; 3)基数排序(Radix Sort)是桶排序的扩展; 4)基数排序是1887年赫尔曼·何乐礼发明的。它是这样实现的:将整数按位数切割成不同的数字,然后按每个位数分别比较。
基数排序基本思想:
将所有待比较数值统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
基数排序解析:
基数排序动图:
基数排序代码:
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 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 public class RadixSort { public static void main (String[] args) { int [] arr = new int [8000000 ]; for (int i = 0 ; i < 8000000 ; i++) { arr[i] = (int ) (Math.random() * 8000000 ); } long start = System.currentTimeMillis(); radixSort(arr); long end = System.currentTimeMillis(); System.out.println("8000000个数字排序所用时间:" + (end - start)); } public static void radixSort (int [] arr) { int max = arr[0 ]; for (int i = 1 ; i < arr.length; i++) { if (arr[i] > max) { max = arr[i]; } } int maxLength = (max + "" ).length(); int [][] bucket = new int [10 ][arr.length]; int [] bucketElementCounts = new int [10 ]; for (int i = 0 , n = 1 ; i < maxLength; i++, n *= 10 ) { for (int j = 0 ; j < arr.length; j++) { int digitOfElement = arr[j] / n % 10 ; bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j]; bucketElementCounts[digitOfElement]++; } int index = 0 ; for (int k = 0 ; k < bucketElementCounts.length; k++) { if (bucketElementCounts[k] != 0 ) { for (int l = 0 ; l < bucketElementCounts[k]; l++) { arr[index++] = bucket[k][l]; } } bucketElementCounts[k] = 0 ; } } } }
延伸 基数排序 基数排序-菜鸟教程 基数排序 radix sort Radix Sort Algorithm 韩顺平数据结构和算法
<
Algorithm Linear Search
Algorithm Merge Sort
>