网站建设 海口,哪里有网站设计公司,注册地址和办公地址,怎么制作一个网站的二维码简介
基数排序是一种非比较性排序算法#xff0c;它通过将待排序的数据拆分成多个数字位进行排序。 实现原理 首先找出待排序数组中的最大值#xff0c;并确定排序的位数。 从最低位#xff08;个位#xff09;开始#xff0c;按照个位数的大小进行桶排序#xff0c;将…简介
基数排序是一种非比较性排序算法它通过将待排序的数据拆分成多个数字位进行排序。 实现原理 首先找出待排序数组中的最大值并确定排序的位数。 从最低位个位开始按照个位数的大小进行桶排序将元素放入对应的桶中。 将各个桶中的元素按照存放顺序依次取出组成新的数组。 接着按照十位数进行桶排序再次将元素放入对应的桶中。 再次将各个桶中的元素按照存放顺序依次取出组成新的数组。 重复上述操作以百位、千位、万位等位数为基准进行排序直至所有位数都被排序。
代码实现
public static void RadixSort(int[] array){if (array null || array.Length 2){return;}//获取数组中的最大值确定排序的位数int max GetMaxValue(array);//进行基数排序for (int exp 1; max / exp 0; exp * 10){CountingSort(array, exp);}}private static void CountingSort(int[] array, int exp){int arrayLength array.Length;int[] output new int[arrayLength];int[] count new int[10];//统计每个桶中的元素个数for (int i 0; i arrayLength; i){count[(array[i] / exp) % 10];}//计算每个桶中最后一个元素的位置for (int i 1; i 10; i){count[i] count[i - 1];}//从原数组中取出元素放入到输出数组中for (int i arrayLength - 1; i 0; i--){output[count[(array[i] / exp) % 10] - 1] array[i];count[(array[i] / exp) % 10]--;}//将输出数组复制回原数组for (int i 0; i arrayLength; i){array[i] output[i];}}private static int GetMaxValue(int[] arr){int max arr[0];for (int i 1; i arr.Length; i){if (arr[i] max){max arr[i];}}return max;}public static void RadixSortRun(){int[] array { 19, 27, 46, 48, 99, 888, 50, 2, 4, 44, 47, 36, 38, 15, 26, 5, 3 };Console.WriteLine(排序前数组 string.Join(, , array));RadixSort(array);Console.WriteLine(排序后数组 string.Join(, , array));} 运行结果 总结
基数排序是一种稳定的排序算法它的时间复杂度为O(d*(nr))其中d是位数n是元素个数r是基数桶的个数。相比其他比较性排序算法基数排序的优势在于减少了元素之间的比较次数并且可以处理负数。但是基数排序的缺点是需要额外的空间来存储临时数组。 C#十大排序总结-CSDN博客
