使用基數排序任意數據類型(一)

[ 來源：.Net教程 | 作者：.Net教程 | 時間：2008-2-22 | 去論壇]      - -

基數排序作為我認為最快速的排序方法一直是我研究的重點,它具有優異的穩定性O(n*基數),和其他排序方法比較在性能上是很優異的,但是因為它的一些局限性一直有很多中基礎數據類型無法使用它進行排序.經過我的研究終於可以排序任意的數據類型了...^_^

下面是排序的主要執行代碼:

using System;
using System.Collections;
using System.Text;
using System.Collections.Generic;

namespace WindowsApplication3
...{
    public class RadixSort
    ...{
        const int MaxCount = 257;
        Queue[] count1 = new Queue[MaxCount];
        Queue[] count2 = new Queue[MaxCount];
        /**//// <summary>
        /// 構造
        /// </summary>
        public RadixSort()
        ...{
            for (int a = 0; a < MaxCount; a++)
      ...{
                count1[a] = new Queue(1000,8);
                count2[a] = new Queue(1000,8);

            }
        }




        public void CompositorData(ref List<RadixSortItem> Data)
        ...{
            Queue data1 = new Queue();
            Queue data2 = new Queue();

            foreach (RadixSortItem item in Data)
            ...{
                if (item.IsNegative)
                ...{
                    data2.Enqueue(item);
           }
                else
                ...{
                    data1.Enqueue(item);
                }
            }

            DateTime bt1 = DateTime.Now;
            Data.Clear();
            Compositor(ref data1);
            Compositor(ref data2);

            TimeSpan bts1 = DateTime.Now - bt1;

            RadixSortItem[] radixSortItems = new RadixSortItem[data2.Count];
            data2.CopyTo(radixSortItems,0);
            Data.AddRange(radixSortItems);
            radixSortItems = new RadixSortItem[data1.Count];
            data1.CopyTo(radixSortItems, 0);
            Data.AddRange(radixSortItems);
        }



        /**//// <summary>
   /// 執行排序
        /// </summary>
        /// <param name="Data"></param>
        void Compositor(ref Queue data)
        ...{
            int MaxBasc = 0;
            int BascIndex = 0;
            DateTime bt1 = DateTime.Now;

            while (data.Count > 0)
            ...{
                RadixSortItem item = (RadixSortItem)data.Dequeue();
                
                if (MaxBasc < item.DataLen)
                ...{
                    MaxBasc = item.DataLen;
                }
                if (BascIndex < item.DataLen)
           ...{
                    byte bb1 = item.Data[BascIndex];
                    count1[bb1 + 1].Enqueue(item);
                }
                else
                ...{
                    count1[0].Enqueue(item);
                }
            }
            BascIndex++;
            int end = 1;
            TimeSpan bts1 = DateTime.Now - bt1;
            while (BascIndex < MaxBasc)
            ...{
                if (BascIndex < MaxBasc)
                ...{
           &nbsp;        bt1 = DateTime.Now;
                    for (int a = 0; a < MaxCount; a++)
                    ...{
                        Queue temp = count1[a];
                        while (temp.Count > 0)
                        ...{
                            RadixSortItem item = (RadixSortItem)temp.Dequeue();
                            if (BascIndex < item.DataLen)
                            ...{
                                count2[item.Data[BascIndex] + 1].Enqueue(item);
                            }
                            else
                ...{
                                count2[0].Enqueue(item);
                            }
                        }
                    }
                    BascIndex++;
                    end = 2;
                    bts1 = DateTime.Now - bt1;
                }

                if (BascIndex < MaxBasc)
                ...{
                    
                    for (int a = 0; a < MaxCount; a++)
                    ...{
                        while (count2[a].Count > 0)
               ...{
                            RadixSortItem item = (RadixSortItem)count2[a].Dequeue();
                            if (BascIndex < item.DataLen)
                            ...{
                                byte bb1 = item.Data[BascIndex];
                                count1[bb1 + 1].Enqueue(item);
                            }
                            else
                            ...{
                                count1[0].Enqueue(item);
                            }
                        }
                    }
                    
                    BascIndex++;
                    end = 1;
                }
            }


            

            Queue[] SortQueue;
            if (end == 1)
            ...{
                SortQueue = count1;
            }
            else
            ...{
                SortQueue = count2;
            }
            for (int a = 0; a < SortQueue.Length; a++)
            ...{
                while (SortQueue[a].Count > 0)
        ;        ...{
                    data.Enqueue(SortQueue[a].Dequeue());
                }
            }
        }
    }
}

可以看到此排序器利用RadixSortItem對象包裝了要排序的數據

RadixSortItem對象如下:

using System;
using System.Collections.Generic;
using System.Text;

namespace WindowsApplication3
...{
    public class RadixSortItem
    ...{
        public byte[] Data;
        public bool IsNegative;
        public int DataLen;


    }
}

可以看出任何數據類型的對象可以合理的轉化為一個byte[]數組就可以調用RadixSort來進行排序了..

如何轉化..待續...