企业网站开发怎么样,软件设计专业介绍,wordpress网页游戏模板,wordpress 后台修改简介
基数排序#xff08;*Radix sort#xff09;是一种非比较排序算法#xff08;non-comparative sorting algorithm#xff09;。现代计算机的基数排序算法由 计数排序 算法的开发人哈罗德H西华德#xff08;Harold H. Seward#xff09;于1954年于麻省理工大学开发。…简介
基数排序*Radix sort是一种非比较排序算法non-comparative sorting algorithm。现代计算机的基数排序算法由 计数排序 算法的开发人哈罗德·H·西华德Harold H. Seward于1954年于麻省理工大学开发。
算法步骤
将待排序序列中的所有数视为同样的数位长度。从最低位开始依次按位进行一次计数排序。从最低位排序一直到最高位排序完成以后数列就变成一个有序序列。
计数排序可参考之前发布的【算法】计数排序。
因为要计算负数因此计数用的 数组 如下
0123456789101112131415161718-9-8-7-6-5-4-3-2-10123456789
[0 ~ 8] 用来表示负数 -9 至 -1。[9] 用于表示 0。[10 ~ 18] 用来表示整数 1 至 9。
举例有未排列序列如下
2633-5-215 从个位数开始排序
2[6]3[3]-[5]-1[2]1[5]63-5-25
计数数列则为
012345678910111213141516171811111
个位数排序为
-12-5331526 从十位数开始排序
-[1]2-[0]5[3]3[1]5[2]6-10312
计数序列为
012345678910111213141516171811111
十位数排序为
-12-5152633
完成排序
C语言实现
// 获取序列中最大位数
unsigned _maxSizeOfItem(const int *array, const unsigned length) {int max array[0];unsigned index 1;unsigned number_1 0;unsigned number_2 0;while (index length) {number_2 array[index];if (max 0) {number_1 max * -1;} else {number_1 max;}if (number_2 0) {number_2 * -1;}if (number_2 number_1) {max array[index];}index 1;}unsigned count 0;while (max ! 0) {max / 10;count 1;}return count;
}// 复制数组。
void _copyArray(int *from_arr, int *to_arr, const unsigned length) {for (unsigned index 0; index length; index) {to_arr[index] from_arr[index];}
}// 按位获取某个数对应的计数序列的索引值。
unsigned _getDigitByPlace(int num, const int place) {num / place;num num - num / 10 * 10;return num 9;
}void radixSort(int *array, const unsigned length) {unsigned radixs[RADIXS_SIZE] {0}; /* initialize array with 0. */unsigned radix 0;int *tmp_array calloc(length, sizeof(int));unsigned index 0;unsigned size _maxSizeOfItem(array, length);int place 1;for (unsigned count 0; count size; count) {// 按位开始计数排序。for (index 0; index length; index) {radix _getDigitByPlace(array[index], place);radixs[radix] 1;}for (index 1; index RADIXS_SIZE; index) {radixs[index] radixs[index] radixs[index - 1];}for (index 0; index length; index) {radix _getDigitByPlace(array[length - index - 1], place);radixs[radix] - 1;tmp_array[radixs[radix]] array[length - index - 1];}// 将完成计数排序后的序列 复制回原数组。_copyArray(tmp_array, array, length);// 重置计数序列。for (index 0; index RADIXS_SIZE; index) {radixs[index] 0;}// 下一个位。place * 10;}free(tmp_array);
}
