桶排序 + 排序穩定性及總結

桶排序

桶排序思想下的排序：計數排序 & 基數排序

1)桶排序思想下的排序都是不基于比較的排序

2)時間複雜度為O(N)，額外空間負載度O(M)

3)應用範圍有限，需要樣本的資料狀況滿足桶的劃分

1）一般來講，計數排序要求，樣本是整數，且範圍比較窄(員工年齡)

2）一般來講，基數排序要求，樣本是10進制的正整數

一旦要求稍有更新，改寫代價增加是顯而易見的

計數排序

/**
 * 計數排序
 */
public class CountSort {

    //對員工年齡進行排序
    public static void sort(int[] ages){
        if(ages ==null || ages.length < 2){
            return;
        }
        //1.找出最大年齡
        int maxAge = Integer.MIN_VALUE;
        for (int age : ages) {
            maxAge = Math.max(maxAge,age);
        }
        //輔助數組
        int[] help = new int[maxAge + 1];
        for (int i = 0; i < ages.length; i++) {
            help[ages[i]]++;
        }
        //周遊輔助數組，把數組放到ages中
        int i = 0;
        for (int j = 0; j < help.length; j++) {
            while (help[i]-- >0){
                ages[i++] = j;
            }
        }

    }
}
           

基數排序

package com.lzf2.class07;

import java.util.Arrays;

/**
 * 基數排序
 */
public class RadixSort {
    // only for no-negative value
    public static void radixSort(int[] arr){
        if(arr==null || arr.length < 2){
            return;
        }
        radixSort(arr,0,arr.length - 1,maxbits(arr));
    }
    //最大數有多少位
    public static int maxbits(int[] arr){
        int max = Integer.MIN_VALUE;
        for (int i : arr) {
             max = Math.max(max,i);
        }
        int res = 0;
        while (max != 0){
            res++;
            max /= 10;
        }
        return res;
    }
    public static int getDigit(int x, int d) {
        return ((x / ((int) Math.pow(10, d - 1))) % 10);
    }
    // arr[L..R]排序  ,  最大值的十進制位數digit
    public static void radixSort(int[] arr, int L, int R, int digit) {
        int radix = 10;//基數
        int[] help = new int[R - L + 1];
        for (int d = 1; d <= digit; d++) {//有多少位就進出多少次

            int[] count = new int[radix];//統計該位上每個數字的個數
            for (int i = L; i <= R; i++) {
                int num = getDigit(arr[i],d);
                count[num]++;
            }
            //把count改成累加和
            for (int i = 1; i < radix; i++) {
                count[i] = count[i] + count[i - 1];
            }
            //從由往左周遊原數組，調整好位置
            for (int i = R; i >= L; i--) {
                int num = getDigit(arr[i],d);
                help[count[num] - 1] = arr[i];
                count[num]--;
            }
            //輔助數組拷貝回原數組
            for (int i = L,j = 0; i <= R; i++,j++) {
                arr[i] = help[j];
            }
        }


    }


    // for test
    public static void comparator(int[] arr) {
        Arrays.sort(arr);
    }

    // for test
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random());
        }
        return arr;
    }

    // for test
    public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    // for test
    public static boolean isEqual(int[] arr1, int[] arr2) {
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
            return false;
        }
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    // for test
    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    // for test
    public static void main(String[] args) {
        int testTime = 500000;
        int maxSize = 100;
        int maxValue = 100000;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            radixSort(arr1);
            comparator(arr2);
            if (!isEqual(arr1, arr2)) {
                succeed = false;
                printArray(arr1);
                printArray(arr2);
                break;
            }
        }
        System.out.println(succeed ? "Nice!" : "Fucking fucked!");

        int[] arr = generateRandomArray(maxSize, maxValue);
        printArray(arr);
        radixSort(arr);
        printArray(arr);

    }
}
           

排序的穩定性

穩定性是指同樣大小的樣本再排序之後不會改變相對次序

對基礎類型來說，穩定性毫無意義

對非基礎類型來說，穩定性有重要意義

有些序算法可以實作成穩定的， 而有些排序算法無論如何都實作不成穩定的

排序總結

1）不基于比較的排序，對樣本資料有嚴格要求，不易改寫

2）基于比較的排序，隻要規定好兩個樣本怎麼比大小就可以直接複用

3）基于比較的排序，時間複雜度的極限是O(NlogN)

4）時間複雜度O(NlogN)、額外空間複雜度低于O(N)、且穩定的基于比較的排序是不存在的。

5）為了絕對的速度選快排、為了省空間選堆排、為了穩定性選歸并

常見的坑

1）歸并排序的額外空間複雜度可以變成O(1)，“歸并排序 内部緩存法”，但是将變得不再穩定。

2）“原地歸并排序" 是垃圾貼，會讓時間複雜度變成O(N^2)

3）快速排序穩定性改進，“01 stable sort”，但是會對樣本資料要求更多。

在整型數組中，請把奇數放在數組左邊，偶數放在數組右邊，要求所有奇數之間原始的相對次序不變，所有偶數之間原始相對次序不變。時間複雜度做到O(N)，額外空間複雜度做到O(1)。

做不到

1）歸并排序的額外空間複雜度可以變成O(1)，“歸并排序 内部緩存法”，但是将變得不再穩定。

2）“原地歸并排序" 是垃圾貼，會讓時間複雜度變成O(N^2)

3）快速排序穩定性改進，“01 stable sort”，但是會對樣本資料要求更多。

在整型數組中，請把奇數放在數組左邊，偶數放在數組右邊，要求所有奇數之間原始的相對次序不變，所有偶數之間原始相對次序不變。時間複雜度做到O(N)，額外空間複雜度做到O(1)。

做不到