[[394975]]

 基數(shù)排序

1. 基數(shù)排序(radix sort)屬于“分配式排序”(distribution sort)，又稱為“桶子法”(bucket sort)或bin sort,顧明思議，它是通過鍵值的各個(gè)位的值，將要排序的元素分配至某些桶中，達(dá)到排序的作用。
2. 基數(shù)排序?qū)儆诜€(wěn)定性的排序，基數(shù)排序法是效率高的穩(wěn)定性排序法。
3. 基數(shù)排序是桶排序的擴(kuò)展。
4. 基數(shù)排序是1887年赫爾曼·何樂禮發(fā)明的。它是這樣實(shí)現(xiàn)的：將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個(gè)位數(shù)分別比較。

排序的基本思想

將所有待比較的值統(tǒng)一為同樣的數(shù)位長(zhǎng)度，數(shù)位較短的數(shù)前面補(bǔ)零。然后，從最低位開始，依次進(jìn)行一次排序。這樣從最低位排序一直到最高位排序完成以后，數(shù)列就變成一個(gè)有序序列。

代碼案例

package com.xie.sort; 
 
public class RadixSort { 
    public static void main(String[] args) { 
        int[] arr = new int[8000000]; 
        for (int i = 0; i < 8000000; i++) { 
            arr[i] = (int)(Math.random()*800000000); 
        } 
        long start = System.currentTimeMillis(); 
        radixSort(arr); 
        long end = System.currentTimeMillis(); 
        System.out.println("耗時(shí)："+(end-start)+"ms"); 
        /* 
        800萬數(shù)據(jù)，耗時(shí)：939ms 
         */ 
    } 
 
    //基數(shù)排序 
    public static void radixSort(int[] arr) { 
 
        int max = arr[0]; 
        for (int i = 1; i < arr.length; i++) { 
            if (arr[i] > max) { 
                max = arr[i]; 
            } 
        } 
        //數(shù)組中的最長(zhǎng)位數(shù) 
        int maxLength = (max + "").length(); 
 
        //第1輪（針對(duì)每個(gè)元素的個(gè)位進(jìn)行排序處理） 
        //定義一個(gè)二維數(shù)組，表示10個(gè)桶，每個(gè)桶就是一個(gè)一維數(shù)組 
        //1.二維數(shù)組包含10個(gè)一維數(shù)組 
        //2.為了防止在放入數(shù)的時(shí)候，數(shù)據(jù)溢出，則每個(gè)一維數(shù)組（桶），大小定為arr.length 
        //3.基數(shù)排序是使用空間換時(shí)間的經(jīng)典算法 
        int[][] bucket = new int[10][arr.length]; 
 
        //為了記錄每個(gè)桶中，實(shí)際存放了多少數(shù)據(jù)，我們定義一個(gè)一維數(shù)組來記錄各個(gè)桶的每次放入的數(shù)據(jù)的個(gè)數(shù)。 
        //bucketElementCounts[0]，記錄的就是bucket[0]桶的放入數(shù)據(jù)的個(gè)數(shù)。 
        int[] bucketElementCounts = new int[10]; 
 
        //按照桶的順序（一維數(shù)組的下標(biāo)依次取出數(shù)據(jù)，放入原來數(shù)組） 
        int index = 0; 
        for (int i = 0, n = 10; i < maxLength; i++, n *= 10) { 
            for (int j = 0; j < arr.length; j++) { 
                //取出位數(shù) 
                int digitOfElement = arr[j] / n % 10; 
                //讓如對(duì)應(yīng)的桶中 
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j]; 
                bucketElementCounts[digitOfElement]++; 
            } 
 
            index = 0; 
            //遍歷每個(gè)桶，并將桶中的數(shù)據(jù)，放入原數(shù)組 
            for (int k = 0; k < bucketElementCounts.length; k++) { 
                //如果桶中有數(shù)據(jù)，才放入到原數(shù)組 
                if (bucketElementCounts[k] != 0) { 
                    //循環(huán)桶中第k個(gè)桶（即第k個(gè)一維數(shù)組),放入。 
                    for (int l = 0; l < bucketElementCounts[k]; l++) { 
                        //取出元素放入arr 
                        arr[index] = bucket[k][l]; 
                        index++; 
                    } 
                } 
                bucketElementCounts[k] = 0; 
            } 
        } 
    } 
} 

基數(shù)排序說明

1. 基數(shù)排序是拿空間換時(shí)間的，對(duì)海量數(shù)據(jù)進(jìn)行排序時(shí)，容易造成OutOfMemoryError.
2. 基數(shù)排序時(shí)穩(wěn)定的?！咀ⅲ杭俣ㄔ诖判虻挠涗浶蛄兄?，存在多個(gè)具有相同的關(guān)鍵字的記錄，若經(jīng)過排序，這些記錄的相對(duì)次序保持不變，即在原序列中r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種算法是穩(wěn)定的，否則不穩(wěn)定】。
3. 對(duì)于有負(fù)數(shù)的數(shù)組進(jìn)行基數(shù)排序,參考：https://code.i-harness.com/zh-CN/q/e98fa9