内部排序—基数排序

柔情只为你懂 2022-06-14 04:46 216阅读 0赞

基数排序的思想是设立r个队列，队列编号分别为0、1、2、…r-1。首先按最低有效位的值把n个关键字分配到这r个队列中；然后从小到大将各队列中的关键字依次收集起来；接着按次低有效位的值把刚收集起来的关键字分配到r个队列中。重复上述分配和收集过程，直到最高有效位。这样得到一个从小到大的有序关键字序列。为了减少记录的移动次数，队列可以采用链式存储分配，称为链队列。每个链队列有2个指针，分别指向队头和队尾。

基数排序时一种稳定的排序算法。对于n个记录，执行一次分配和收集的时间为O(n+r)。

如果关键字有d位，则执行d遍。所有总的运行时间为O(d(n+r))。对于不同的技术r,所用的时间是不同的，当r或d较小时，这种排序方法较为节省时间。基数排序适用于链式分配的记录排序，其要求是附加存储量是r个队列的头、尾指针，所以附加存储量为2r个存储单元。由于待排序记录是链式方式存储的，相对于顺序分配而言，还增加了n个指针域的空间。

///  /// 基数排序 /// 原理:待排数字中没有0,如果某桶内数字为0则表示该桶未被使用,输出时跳过即可 /// 
    /// 
    private int[] RadixSort(int[] arrData)
    {
        int array_x = 10;//桶数组第一维长度  最大数字不超过999999999...(array_x个9)
        int array_y = arrData.Length;//桶数组第二维长度,防止相同数组
        for (int i = 0; i < array_x; i++)
        {
            int[,] bucket = new int[array_x, array_y];
            foreach (var item in arrData)
            {
                int temp = (item / (int)Math.Pow(10, i)) % 10;
                for (int j = 0; j < array_y; j++)
                {
                    if (bucket[temp, j] == 0)
                    {
                        bucket[temp, j] = item;
                        break;
                    }
                }
            }
    
            int key = 0;
            for (int m = 0; m < array_x; m++)
            {
                for (int n = 0; n < array_y; n++)
                {
                    if (bucket[m, n] == 0) continue;
                    arrData[key++] = bucket[m, n];
                }
            }
        }
        return arrData;
    }