[[421174]]

基數排序

概念

基數排序是非比較型整數排序算法，其原理是將整數按位分割進行排序。基數排序適用于大范圍數據排序，打破了計數排序的限制。由于整數也可以表達字符串(比如名字或日期)和特定格式的浮點數，所以基數排序也不是只能使用于整數。

2種排序方式

最低位優先法(LSD)：從最低位向最高位依次按位進行排序。

最高位優先法(MSD)：從最高位向最低位依次按位進行排序。

按位分割小技巧

arr[i] / digit % 10，其中digit為10^n。

LSD排序算法實現

算法思想

按位進行計數排序

算法實現代碼

/** 
     * 按位進行計數排序 
     * @param arr 
     * @param divid 
     * @return 
     */ 
private static int[] countingSort(int[] arr, int divid){ 
 
    int[] bucket = new int[10]; 
    for (int i = 0; i < arr.length; i++) { 
        bucket[arr[i] / divid % 10]++; 
    } 
 
    for (int i = 1; i < bucket.length; i++) { 
        bucket[i] = bucket[i-1] + bucket[i]; 
    } 
 
    int[] sortArr = new int[arr.length]; 
    for (int i = arr.length - 1; i >= 0; i--){ 
        int position = bucket[arr[i] / divid % 10]; 
        sortArr[position - 1] = arr[i]; 
        bucket[arr[i] / divid % 10]--; 
    } 
    return sortArr; 
} 
 
public static int[] radixSort(int[] arr) { 
    // 查找數組最大值 
    int max = arr[0]; 
    for (int i = 0; i < arr.length; i++) { 
        max = Math.max(arr[i], max); 
    } 
    // 按位排序 
    int digit = 1; 
    for (int i = 1; i < max; digit*=10, i = digit) { 
        arr = countingSort(arr, digit); 
    } 
    return arr; 
} 

排序驗證：

public static void main(String[] args) { 
     int[] arr = {999,1000,1001,1000,999,1005}; 
     System.out.println("排序前:" + JSON.toJSONString(arr)); 
     int[] sortArr = radixSort(arr); 
     System.out.println("排序后:" + JSON.toJSONString(sortArr)); 
 } 

排序前:[999,1000,1001,1000,999,1005] 排序后:[999,999,1000,1000,1001,1005]

MSD排序算法實現

算法思想

從最高位開始，按位分組，當組內元素個數>1時，遞歸下一位分組，一直分到個位結束;收集元素個數=1的。

算法步驟

• 查詢最大值，獲取最高位的基數。Math.pow(10, digit - 1)
• 按位分組，存入桶內。groupBucket[position][groupCounter[position]] =arr[i];
• 組內元素數量>1，下一位遞歸分組。if (groupBucket[i] > 1) {int[] tmp = msdSort(copyArr, radix / 10);}
• 組內元素數量=1，收集元素。sortArr[index++] = groupBucket[i][0];

比如，對數組[333,1002,1001,1000,333,1003,2000]進行排序，操作步驟如下：

算法實現代碼

public static int[] sort(int[] arr){ 
 
    int max = arr[0]; 
    for (int i = 0; i < arr.length; i++) { 
        // 獲取最大值 
        max = Math.max(arr[i], max); 
    } 
 
    // 獲取最大值的位數 
    int digit = getDataDigit(max); 
    // 計算最大值的基數 
    int radix = new Double(Math.pow(10, digit - 1)).intValue(); 
    // msd基數排序 
    return msdSort(arr, radix); 
} 
 
/** 
     * MSD 基數排序 
     * @param arr 
     * @param radix 
     * @return 
     */ 
public static int[] msdSort(int[] arr, int radix){ 
 
    // 遞歸分組到個位，退出 
    if (radix <= 0) { 
        return arr; 
    } 
 
    // 分組計數器 
    int[] groupCounter = new int[10]; 
    // 分組桶 
    int[][] groupBucket = new int[10][arr.length]; 
    // 遍歷待排序數組，按位分組 
    for (int i = 0; i < arr.length; i++) { 
        // 計算分組桶位置 
        int position = arr[i] / radix % 10; 
        // 將元素存入分組 
        groupBucket[position][groupCounter[position]] = arr[i]; 
        // 當前分組計數加1 
        groupCounter[position]++; 
    } 
 
    int index = 0; 
    int[] sortArr = new int[arr.length]; 
 
    // 遍歷分組計數器 
    for (int i = 0; i < groupCounter.length; i++) { 
        // 組內元素數量>1，遞歸分組 
        if (groupCounter[i] > 1) { 
            int[] copyArr = Arrays.copyOf(groupBucket[i], groupCounter[i]); 
            // 遞歸分組 
            int[] tmp = msdSort(copyArr, radix / 10); 
            // 收集遞歸分組后的元素 
            for (int j = 0; j < tmp.length; j++) { 
                sortArr[index++] = tmp[j]; 
            } 
        } else if (groupCounter[i] == 1) { 
            // 收集組內元素數量=1的元素 
            sortArr[index++] = groupBucket[i][0]; 
        } 
    } 
 
    return sortArr; 
} 
 
/** 
     * 獲取數據的位數 
     * @param data 
     * @return 
     */ 
public static int getDataDigit(int data) { 
    //        int index = 0; 
    //        int digit = 1; 
    //        while (data / digit >0) { 
    //            digit *= 10; 
    //            index++; 
    //        } 
    //        return index; 
 
    return String.valueOf(data).length(); 
} 

驗證排序結果：

public static void main(String[] args) { 
    int[] arr = {333,1002,1001,1000,333,1003,2000}; 
    System.out.println("排序前:" + JSON.toJSONString(arr)); 
    int[] sortArr = sort(arr); 
    System.out.println("排序后:" + JSON.toJSONString(sortArr)); 
} 

排序前:[333,1002,1001,1000,333,1003,2000] 排序后:[333,333,1000,1001,1002,1003,2000]

三向切分字符快速排序

算法思想

按位將字符串切分為三個區間，小于v區間：[lo,lt-1]，等于v區間：[lt,gt]，大于v區間: [gt+1,hi]，依次遞歸三個區間。

算法步驟

• 定義小于v區間的看門狗lt，大于v區間的看門狗gt。
• 按位比較劃分三個區間。
• 遞歸三個區間。

算法實現代碼

/** 
     * 按位將字符串切分為三個區間 
     * 1. 小于v區間：[lo,lt] 
     * 2. 等于v區間：[lt,gt] 
     * 3. 大于v區間: [gt+1,hi] 
     * @param arr 
     * @param lo 
     * @param hi 
     * @param d 
     */ 
public static void sortStr(String[] arr, int lo, int hi, int d){ 
    if (hi <= lo) { 
        return; 
    } 
    // 定義小于v的看門lt, 大于v的看門gt 
    int lt = lo, gt = hi, i = lo + 1, v = charAt(arr[lo],d); 
    while (i <= gt){ 
        int t = charAt(arr[i], d); 
        if (t < v) { 
            exch(arr, i++, lt++); 
        } else if (t > v) { 
            exch(arr, i, gt--); 
        } else { 
            i++; 
        } 
    } 
 
    // 遞歸小于v的區間 
    sortStr(arr, lo, lt - 1, d); 
    // 遞歸等于v的區間 
    if (v >= 0) { 
        sortStr(arr, lt, gt, d + 1); 
    } 
    // 遞歸大于v的區間 
    sortStr(arr, gt + 1, hi, d); 
} 
private static int charAt(String s, int d) { 
    if (d < s.length()) { 
        return s.charAt(d); 
    } 
    return -1; 
} 
public static void exch(String[] arr, int sourceIdx, int targetIdx) { 
    String tmp = arr[sourceIdx]; 
    arr[sourceIdx] = arr[targetIdx]; 
    arr[targetIdx] = tmp; 
} 
結果驗證： 
 
 public static void main(String[] args) { 
     String[] a = new String[]{"by","air","she","shell","the","okay","bump","shirt","shells","sh","the","shells","the"}; 
     System.out.println("排序前:" + JSON.toJSONString(a)); 
     sortStr(a, 0, a.length - 1, 0); 
     System.out.println("排序后:" + JSON.toJSONString(a)); 
 } 

排序前:["by","air","she","shell","the","okay","bump","shirt","shells","sh","the","shells","the"] 排序后:["air","bump","by","okay","sh","she","shell","shells","shells","shirt","the","the","the"]

三種排序算法對比

總結

基數排序是穩定、非比較排序，適合用于大數據范圍的。