首页 > 代码库 > 基数排序
基数排序
概要
本章介绍排序算法中的基数排序。内容包括：
1. 基数排序介绍
2. 基数排序图文说明
3. 基数排序实现
3.1 基数排序C实现
3.2 基数排序C++实现
3.3 基数排序Java实现
转载请注明出处：http://www.cnblogs.com/skywang12345/p/3603669.html
更多排序和算法请参考：数据结构与算法系列 目录
基数排序介绍
基数排序(Radix Sort)是桶排序的扩展，它的基本思想是：将整数按位数切割成不同的数字，然后按每个位数分别比较。
具体做法是：将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
基数排序图文说明
基数排序图文说明
通过基数排序对数组{53, 3, 542, 748, 14, 214, 154, 63, 616}，它的示意图如下：
在上图中，首先将所有待比较树脂统一为统一位数长度，接着从最低位开始，依次进行排序。
1. 按照个位数进行排序。
2. 按照十位数进行排序。
3. 按照百位数进行排序。
排序后，数列就变成了一个有序序列。
基数排序代码
/* * 获取数组a中最大值 * * 参数说明： * a -- 数组 * n -- 数组长度 */ int get_max(int a[], int n) { int i, max; max = a[0]; for (i = 1; i < n; i++) if (a[i] > max) max = a[i]; return max; } /* * 对数组按照"某个位数"进行排序(桶排序) * * 参数说明： * a -- 数组 * n -- 数组长度 * exp -- 指数。对数组a按照该指数进行排序。 * * 例如，对于数组a={50, 3, 542, 745, 2014, 154, 63, 616}； * (01) 当exp=1表示按照"个位"对数组a进行排序 * (02) 当exp=10表示按照"十位"对数组a进行排序 * (03) 当exp=100表示按照"百位"对数组a进行排序 * ... */ void count_sort(int a[], int n, int exp) { int output[n]; // 存储"被排序数据"的临时数组 int i, buckets[10] = {0}; // 将数据出现的次数存储在buckets[]中 for (i = 0; i < n; i++) buckets[ (a[i]/exp)%10 ]++; // 更改buckets[i]。目的是让更改后的buckets[i]的值，是该数据在output[]中的位置。 for (i = 1; i < 10; i++) buckets[i] += buckets[i - 1]; // 将数据存储到临时数组output[]中 for (i = n - 1; i >= 0; i--) { output[buckets[ (a[i]/exp)%10 ] - 1] = a[i]; buckets[ (a[i]/exp)%10 ]--; } // 将排序好的数据赋值给a[] for (i = 0; i < n; i++) a[i] = output[i]; } /* * 基数排序 * * 参数说明： * a -- 数组 * n -- 数组长度 */ void radix_sort(int a[], int n) { int exp; // 指数。当对数组按各位进行排序时，exp=1；按十位进行排序时，exp=10；... int max = get_max(a, n); // 数组a中的最大值 // 从个位开始，对数组a按"指数"进行排序 for (exp = 1; max/exp > 0; exp *= 10) count_sort(a, n, exp); }
radix_sort(a, n)的作用是对数组a进行排序。
1. 首先通过get_max(a)获取数组a中的最大值。获取最大值的目的是计算出数组a的最大指数。
2. 获取到数组a中的最大指数之后，再从指数1开始，根据位数对数组a中的元素进行排序。排序的时候采用了桶排序。
3. count_sort(a, n, exp)的作用是对数组a按照指数exp进行排序。
下面简单介绍一下对数组{53, 3, 542, 748, 14, 214, 154, 63, 616}按个位数进行排序的流程。
(01) 个位的数值范围是[0,10)。因此，参见桶数组buckets[]，将数组按照个位数值添加到桶中。
(02) 接着是根据桶数组buckets[]来进行排序。假设将排序后的数组存在output[]中；找出output[]和buckets[]之间的联系就可以对数据进行排序了。
基数排序实现
基数排序C实现
实现代码(radix_sort.c)
1 /** 2 * 基数排序：C 语言 3 * 4 * @author skywang 5 * @date 2014/03/15 6 */ 7 8 #include <stdio.h> 9 10 // 数组长度 11 #define LENGTH(array) ( (sizeof(array)) / (sizeof(array[0])) ) 12 13 /* 14 * 获取数组a中最大值 15 * 16 * 参数说明： 17 * a -- 数组 18 * n -- 数组长度 19 */ 20 int get_max(int a[], int n) 21 { 22 int i, max; 23 24 max = a[0]; 25 for (i = 1; i < n; i++) 26 if (a[i] > max) 27 max = a[i]; 28 return max; 29 } 30 31 /* 32 * 对数组按照"某个位数"进行排序(桶排序) 33 * 34 * 参数说明： 35 * a -- 数组 36 * n -- 数组长度 37 * exp -- 指数。对数组a按照该指数进行排序。 38 * 39 * 例如，对于数组a={50, 3, 542, 745, 2014, 154, 63, 616}； 40 * (01) 当exp=1表示按照"个位"对数组a进行排序 41 * (02) 当exp=10表示按照"十位"对数组a进行排序 42 * (03) 当exp=100表示按照"百位"对数组a进行排序 43 * ... 44 */ 45 void count_sort(int a[], int n, int exp) 46 { 47 int output[n]; // 存储"被排序数据"的临时数组 48 int i, buckets[10] = {0}; 49 50 // 将数据出现的次数存储在buckets[]中 51 for (i = 0; i < n; i++) 52 buckets[ (a[i]/exp)%10 ]++; 53 54 // 更改buckets[i]。目的是让更改后的buckets[i]的值，是该数据在output[]中的位置。 55 for (i = 1; i < 10; i++) 56 buckets[i] += buckets[i - 1]; 57 58 // 将数据存储到临时数组output[]中 59 for (i = n - 1; i >= 0; i--) 60 { 61 output[buckets[ (a[i]/exp)%10 ] - 1] = a[i]; 62 buckets[ (a[i]/exp)%10 ]--; 63 } 64 65 // 将排序好的数据赋值给a[] 66 for (i = 0; i < n; i++) 67 a[i] = output[i]; 68 } 69 70 /* 71 * 基数排序 72 * 73 * 参数说明： 74 * a -- 数组 75 * n -- 数组长度 76 */ 77 void radix_sort(int a[], int n) 78 { 79 int exp; // 指数。当对数组按各位进行排序时，exp=1；按十位进行排序时，exp=10；... 80 int max = get_max(a, n); // 数组a中的最大值 81 82 // 从个位开始，对数组a按"指数"进行排序 83 for (exp = 1; max/exp > 0; exp *= 10) 84 count_sort(a, n, exp); 85 } 86 87 void main() 88 { 89 int i; 90 int a[] = {53, 3, 542, 748, 14, 214, 154, 63, 616}; 91 int ilen = LENGTH(a); 92 93 printf("before sort:"); 94 for (i=0; i<ilen; i++) 95 printf("%d ", a[i]); 96 printf("\n"); 97 98 radix_sort(a, ilen); 99 100 printf("after sort:"); 101 for (i=0; i<ilen; i++) 102 printf("%d ", a[i]); 103 printf("\n"); 104 }
基数排序C++实现
实现代码(RadixSort.cpp)
1 /** 2 * 基数排序：C++ 3 * 4 * @author skywang 5 * @date 2014/03/15 6 */ 7 8 #include<iostream> 9 using namespace std; 10 11 /* 12 * 获取数组a中最大值 13 * 14 * 参数说明： 15 * a -- 数组 16 * n -- 数组长度 17 */ 18 int getMax(int a[], int n) 19 { 20 int i, max; 21 22 max = a[0]; 23 for (i = 1; i < n; i++) 24 if (a[i] > max) 25 max = a[i]; 26 return max; 27 } 28 29 /* 30 * 对数组按照"某个位数"进行排序(桶排序) 31 * 32 * 参数说明： 33 * a -- 数组 34 * n -- 数组长度 35 * exp -- 指数。对数组a按照该指数进行排序。 36 * 37 * 例如，对于数组a={50, 3, 542, 745, 2014, 154, 63, 616}； 38 * (01) 当exp=1表示按照"个位"对数组a进行排序 39 * (02) 当exp=10表示按照"十位"对数组a进行排序 40 * (03) 当exp=100表示按照"百位"对数组a进行排序 41 * ... 42 */ 43 void countSort(int a[], int n, int exp) 44 { 45 int output[n]; // 存储"被排序数据"的临时数组 46 int i, buckets[10] = {0}; 47 48 // 将数据出现的次数存储在buckets[]中 49 for (i = 0; i < n; i++) 50 buckets[ (a[i]/exp)%10 ]++; 51 52 // 更改buckets[i]。目的是让更改后的buckets[i]的值，是该数据在output[]中的位置。 53 for (i = 1; i < 10; i++) 54 buckets[i] += buckets[i - 1]; 55 56 // 将数据存储到临时数组output[]中 57 for (i = n - 1; i >= 0; i--) 58 { 59 output[buckets[ (a[i]/exp)%10 ] - 1] = a[i]; 60 buckets[ (a[i]/exp)%10 ]--; 61 } 62 63 // 将排序好的数据赋值给a[] 64 for (i = 0; i < n; i++) 65 a[i] = output[i]; 66 } 67 68 /* 69 * 基数排序 70 * 71 * 参数说明： 72 * a -- 数组 73 * n -- 数组长度 74 */ 75 void radixSort(int a[], int n) 76 { 77 int exp; // 指数。当对数组按各位进行排序时，exp=1；按十位进行排序时，exp=10；... 78 int max = getMax(a, n); // 数组a中的最大值 79 80 // 从个位开始，对数组a按"指数"进行排序 81 for (exp = 1; max/exp > 0; exp *= 10) 82 countSort(a, n, exp); 83 } 84 85 int main() 86 { 87 int i; 88 int a[] = {53, 3, 542, 748, 14, 214, 154, 63, 616}; 89 int ilen = (sizeof(a)) / (sizeof(a[0])); 90 91 cout << "before sort:"; 92 for (i=0; i<ilen; i++) 93 cout << a[i] << " "; 94 cout << endl; 95 96 radixSort(a, ilen); // 基数排序 97 98 cout << "after sort:"; 99 for (i=0; i<ilen; i++) 100 cout << a[i] << " "; 101 cout << endl; 102 103 return 0; 104 }
基数排序Java实现
实现代码(RadixSort.java)
1 /** 2 * 基数排序：Java 3 * 4 * @author skywang 5 * @date 2014/03/15 6 */ 7 8 public class RadixSort { 9 10 /* 11 * 获取数组a中最大值 12 * 13 * 参数说明： 14 * a -- 数组 15 * n -- 数组长度 16 */ 17 private static int getMax(int[] a) { 18 int max; 19 20 max = a[0]; 21 for (int i = 1; i < a.length; i++) 22 if (a[i] > max) 23 max = a[i]; 24 25 return max; 26 } 27 28 /* 29 * 对数组按照"某个位数"进行排序(桶排序) 30 * 31 * 参数说明： 32 * a -- 数组 33 * exp -- 指数。对数组a按照该指数进行排序。 34 * 35 * 例如，对于数组a={50, 3, 542, 745, 2014, 154, 63, 616}； 36 * (01) 当exp=1表示按照"个位"对数组a进行排序 37 * (02) 当exp=10表示按照"十位"对数组a进行排序 38 * (03) 当exp=100表示按照"百位"对数组a进行排序 39 * ... 40 */ 41 private static void countSort(int[] a, int exp) { 42 //int output[a.length]; // 存储"被排序数据"的临时数组 43 int[] output = new int[a.length]; // 存储"被排序数据"的临时数组 44 int[] buckets = new int[10]; 45 46 // 将数据出现的次数存储在buckets[]中 47 for (int i = 0; i < a.length; i++) 48 buckets[ (a[i]/exp)%10 ]++; 49 50 // 更改buckets[i]。目的是让更改后的buckets[i]的值，是该数据在output[]中的位置。 51 for (int i = 1; i < 10; i++) 52 buckets[i] += buckets[i - 1]; 53 54 // 将数据存储到临时数组output[]中 55 for (int i = a.length - 1; i >= 0; i--) { 56 output[buckets[ (a[i]/exp)%10 ] - 1] = a[i]; 57 buckets[ (a[i]/exp)%10 ]--; 58 } 59 60 // 将排序好的数据赋值给a[] 61 for (int i = 0; i < a.length; i++) 62 a[i] = output[i]; 63 64 output = null; 65 buckets = null; 66 } 67 68 /* 69 * 基数排序 70 * 71 * 参数说明： 72 * a -- 数组 73 */ 74 public static void radixSort(int[] a) { 75 int exp; // 指数。当对数组按各位进行排序时，exp=1；按十位进行排序时，exp=10；... 76 int max = getMax(a); // 数组a中的最大值 77 78 // 从个位开始，对数组a按"指数"进行排序 79 for (exp = 1; max/exp > 0; exp *= 10) 80 countSort(a, exp); 81 } 82 83 public static void main(String[] args) { 84 int i; 85 int a[] = {53, 3, 542, 748, 14, 214, 154, 63, 616}; 86 87 System.out.printf("before sort:"); 88 for (i=0; i<a.length; i++) 89 System.out.printf("%d ", a[i]); 90 System.out.printf("\n"); 91 92 radixSort(a); // 基数排序 93 94 System.out.printf("after sort:"); 95 for (i=0; i<a.length; i++) 96 System.out.printf("%d ", a[i]); 97 System.out.printf("\n"); 98 } 99 }
上面3种实现的原理和输出结果都是一样的。下面是它们的输出结果：
before sort:53 3 542 748 14 214 154 63 616
after sort:3 14 53 63 154 214 542 616 748
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。