Skynet

          ---------- ---------- 我的新 blog : liukaiyi.cublog.cn ---------- ----------

            BlogJava :: 首頁 :: 聯系 :: 聚合  :: 管理
            112 Posts :: 1 Stories :: 49 Comments :: 0 Trackbacks
          下面介紹的排序都為:非比較排序法

          這里個人認為在某些特定的地方非比較排序的速度非常明顯;
          比如 : 對待排數據中有順序分類,使用鴿巢總體分類,然后對不同類別的待排小數據集合采用 插入,快排等排序方式


          Counting sort :計數排序
          描述:迭代待排序數組出元素x,確定小于此元素[z]個數,然后把x放到它在的最終輸出數組[z]上。
          特性:與待排值有關;穩定的排序算法;待排序數據要求過于嚴格,無實際用處;
          算法的步驟如下:
             1. 找出待排序的數組中最大和最小的元素
             2. 統計數組中每個值為i的元素出現的次數,存入數組C的第i項
             3. 對所有的計數累加(從C中的第一個元素開始,每一項和前一項相加)
             4. 反向填充目標數組:將每個元素i放在新數組的第C(i)項,每放一個元素就將C(i)減去1


          Radix sort:基數排序
          描述:將所有待比較數值(正整數)統一為同樣的數位長度,數位較短的數前面補零. 然后, 從最低位開始, 依次進行一次排序.這樣從最低位排序一直到最高位排序完成以后, 數列就變成一個有序序列.
          排序方式:LSD 由右向左排;MSD 由左向右排
          特性:非比較排序;待排數據需要統一格式;
          假設需排序數列的取值范圍從1...k,我們于是建一個K+1元的數組 a[],并賦初值為0,然后便開始排序工作:
          算法的步驟如下:
             1. 按輸入順序讀入數列,如果所讀的元素為i(1<=i<=k),我們就將a[i]的值加一,這樣直到讀完所有的元素。
             2. 讀出元素并排序:我們遍歷整個數組,如果a[i]=j(j>=0),我們就輸出j次i(表示元素i在原先數列中出現了j次),這樣輸出的序列就是已排序的。
             3. 由于一般排序算法涉及到元素之間的比較,如果化成比較樹可以知道,這樣的排序算法復雜度的下限是O(N*lnN),而計數排序沒有比較元素,所以所需排序時間就少了,我們可以看到計數排序的復雜度為O(n*k),其中k(k的定義同上)為合并排列所需的時間,是個常數。
             4. 此算法適合所需排列的元素取值范圍不大的情況下,否則會造成空間的消耗,比如,一共100個元素,其取值范圍從1-100000,顯然這個時候用基數排序是不合適的。



          Bucket sort:桶排序
          描述:工作的原理是將陣列分到有限數量的桶子里。每個桶子再個別排序(有可能再使用別的排序算法或是以遞回方式繼續使用桶排序進行排序)。
          桶排序以下列程序進行:
             1. 設置一個定量的陣列當作空桶子。
             2. 尋訪序列,并且把項目一個一個放到對應的桶子去。
             3. 對每個不是空的桶子進行排序。
             4. 從不是空的桶子里把項目再放回原來的序列中。



          Pigeonhole sort:鴿巢排序
          描述:是一種時間復雜度為O(n)且在不可避免遍歷每一個元素并且排序的情況下效率最好的一種排序算法. 但它只有在差值(或者可被映射在差值)很小的范圍內的數值排序的情況下實用.
          算法的步驟如下:與桶排同





          整理 www.aygfsteel.com/Good-Game
          posted on 2009-12-08 14:21 劉凱毅 閱讀(1771) 評論(1)  編輯  收藏 所屬分類: 算法/函數

          Feedback

          # re: 跟我一起學 - 算法導論 - 線性時間排序 2009-12-11 16:30 av
          收藏le~  回復  更多評論
            

          主站蜘蛛池模板: 梅河口市| 和龙市| 南昌市| 永德县| 绍兴市| 潮安县| 湘阴县| 江达县| 宁强县| 彭阳县| 陇川县| 定西市| 民勤县| 晋中市| 毕节市| 民县| 读书| 纳雍县| 新干县| 秦安县| 友谊县| 八宿县| 辽阳县| 赤峰市| 怀化市| 城步| 铁岭市| 博罗县| 安塞县| 桓仁| 和龙市| 无为县| 大冶市| 濮阳市| 仁怀市| 彭州市| 郧西县| 阜阳市| 佛学| 普宁市| 云霄县|