/**
 * 冒泡排序
 * @param array
 */
public static void bubbleSort(int[] array){
    if(array.length == 0){
        return;
    }
    for(int i=0;i<array.length;i++){
        // 每一次都減少i個元素
        for(int j=0;j<array.length-1-i;j++){
            // 若相鄰的兩個元素比較后，前一個元素大于后一個元素，則交換位置。
            if(array[j]>array[j+1]){
                int temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }
        }
    }
}

public static void selectSort(int[] array){
    for(int i=0;i<array.length;i++){
        // 先以i為最小值的下標
        int min = i;
        // 然后從后面的數(shù)據(jù)中找出比array[min] 還小的值，就替換min為當前下標。
        for(int j=i+1;j<array.length;j++){
            if(array[j]<array[min]){
                min = j;
            }
        }
        // 最終如果最小值的下標不等于i了，那么將最小值與i位置的數(shù)據(jù)替換，即將最小值放到數(shù)組前面來，然后循環(huán)整個操作。
        if(min != i){
            int temp = array[i];
            array[i] = array[min];
            array[min] = temp;
        }
    }
}

public static void insertSort(int[] array){
     // 第一個元素被認為默認有序，所以遍歷無序元素從i1開始。
     for(int i=1;i<array.length;i++){
         int sortItem = array[i];
         int j = i;
         // 將當前元素插入到前面的有序元素里，將當前元素與前面有序元素從后往前挨個對比，然后將元素插入到指定位置。
         while (j>0 && sortItem < array[j-1]){
             array[j] = array[j-1];
             j--;
         }
         // 若當前元素在前面已排序里面不是最大的，則將它插入到前面已經(jīng)確定了位置里。
         if(j !=i){
             array[j] = sortItem;
         }
     }
 }

/**
 * 希爾排序
 * @param array
 */
public static void shellSort(int[] array){
    int len = array.length;
    int temp, gap = len / 2;
    while (gap > 0) {
        for (int i = gap; i < len; i++) {
            temp = array[i];
            int preIndex = i - gap;
            while (preIndex >= 0 && array[preIndex] > temp) {
                array[preIndex + gap] = array[preIndex];
                preIndex -= gap;
            }
            array[preIndex + gap] = temp;
        }
        gap /= 2;
    }
}

/**
     * 歸并排序
     * @param array     數(shù)組
     * @param left      0
     * @param right     array.length-1
     */
    public static void mergeSort(int[] array,int left,int right){
        if (right <= left){
            return;
        }
        // 一分為二
        int mid = (left + right)/2;
        // 對前半部分執(zhí)行歸并排序
        mergeSort(array, left, mid);
        // 對后半部分執(zhí)行歸并排序
        mergeSort(array, mid + 1, right);
        // 將分好的每個子序列，執(zhí)行排序加合并操作
        merge(array, left, mid, right);
    }
    /**
     * 合并加排序
     * @param array
     * @param left
     * @param middle
     * @param right
     */
    public static void merge(int[] array,int left,int middle,int right){
     // 中間數(shù)組
     int[] temp = new int[right - left + 1]; 
     int i = left, j = middle + 1, k = 0;
     while (i <= middle && j <= right) {
         // 若前面數(shù)組的元素小，就將前面元素的數(shù)據(jù)放到中間數(shù)組中
         if(array[i] <= array[j]){
             temp[k++] = array[i++];
         }else {
             // 若后面數(shù)組的元素小，就將后面數(shù)組的元素放到中間數(shù)組中
             temp[k++] = array[j++];
         }
     }
     // 若經(jīng)過上面的比較合并后，前半部分的數(shù)組還有數(shù)據(jù)，則直接插入中間數(shù)組后面
     while (i <= middle){
         temp[k++] = array[i++];
     }
     // 若經(jīng)過上面的比較合并后，后半部分的數(shù)組還有數(shù)據(jù)，則直接插入中間數(shù)組后面
     while (j <= right){
         temp[k++] = array[j++];
     }
     // 將數(shù)據(jù)從中間數(shù)組中復制回原數(shù)組
     for (int p = 0; p < temp.length; p++) {
         array[left + p] = temp[p];
     }
 }

/**
 * 快速排序
 * @param array 數(shù)組
 * @param begin 0
 * @param end   array.length-1
 */
public static void quickSort(int[] array, int begin, int end) {
    if (end <= begin) return;
    int pivot = partition(array, begin, end);
    quickSort(array, begin, pivot - 1);
    quickSort(array, pivot + 1, end);
}
/**
 * 分區(qū)
 * @param array
 * @param begin
 * @param end
 * @return
 */
public static int partition(int[] array, int begin, int end) {
    // pivot: 標桿位置，counter: 小于pivot的元素的個數(shù)
    int pivot = end, counter = begin;
    for (int i = begin; i < end; i++) {
        if (array[i] < array[pivot]) {
           // 替換，將小于標桿位置的數(shù)據(jù)放到開始位置算起小于標桿數(shù)據(jù)的第counter位
            int temp = array[counter];
            array[counter] = array[i];
            array[i] = temp;
            counter++;
        }
    }
    // 將標桿位置的數(shù)據(jù)移動到小于標桿位置數(shù)據(jù)的下一個位。
    int temp = array[pivot];
    array[pivot] = array[counter];
    array[counter] = temp;
    return counter;
}

/**
 * 堆排序
 * @param array
 */
public static int[] heapSort(int[] array){
    int size = array.length;
    // 先將數(shù)據(jù)放入堆中
    for (int i = (int) Math.floor(size / 2); i >= 0; i--) {
        heapTopMove(array, i, size);
    }
    // 堆頂位置調(diào)整
    for(int i = size - 1; i > 0; i--) {
        swapNum(array, 0, i);
        size--;
        heapTopMove(array, 0,size);
    }
    return array;
}
/**
 * 堆頂位置維護
 * @param array
 * @param i
 * @param size
 */
public static void heapTopMove(int[] array,int i,int size){
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    int largest = i;
    if (left < size && array[left] > array[largest]) {
        largest = left;
    }
    if (right < size && array[right] > array[largest]) {
        largest = right;
    }
    if (largest != i) {
        swapNum(array, i, largest);
        heapTopMove(array, largest, size);
    }
}
/**
 * 比較交換
 * @param array
 * @param left
 * @param right
 */
public static void swapNum(int[] array,int left,int right){
    int temp = array[left];
    array[left] = array[right];
    array[right] = temp;
}

/**
 * 計數(shù)排序
 * @param array
 */
public static void countSort(int[] array){
    int bucketLen = getMaxValue(array) + 1;
    int[] bucket = new int[bucketLen];
    // 統(tǒng)計每個值出現(xiàn)的次數(shù)
    for (int value : array) {
        bucket[value]++;
    }
    // 反向填充數(shù)組
    int sortedIndex = 0;
    for (int j = 0; j < bucketLen; j++) {
        while (bucket[j] > 0) {
            array[sortedIndex++] = j;
            bucket[j]--;
        }
    }
}
/**
 * 獲取最大值
 * @param arr
 * @return
 */
private static int getMaxValue(int[] arr) {
    int maxValue = arr[0];
    for (int value : arr) {
        if (maxValue < value) {
            maxValue = value;
        }
    }
    return maxValue;
}

 /**
  * 桶排序
  * @param arr
  * @param bucketSize
  * @return
  */
 private static int[] bucketSort(int[] arr, int bucketSize){
     if (arr.length == 0) {
         return arr;
     }
     int minValue = arr[0];
     int maxValue = arr[0];
     // 計算出最大值和最小值
     for (int value : arr) {
         if (value < minValue) {
             minValue = value;
         } else if (value > maxValue) {
             maxValue = value;
         }
     }
     // 根據(jù)桶的長度以及數(shù)據(jù)的最大值和最小值，計算出桶的數(shù)量
     int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
     int[][] buckets = new int[bucketCount][0];
     // 利用映射函數(shù)將數(shù)據(jù)分配到各個桶中
     for (int i = 0; i < arr.length; i++) {
         int index = (int) Math.floor((arr[i] - minValue) / bucketSize);
         // 將數(shù)據(jù)填充到指定的桶中
         buckets[index] = appendBucket(buckets[index], arr[i]);
     }
     int arrIndex = 0;
     for (int[] bucket : buckets) {
         if (bucket.length <= 0) {
             continue;
         }
         // 對每個桶進行排序，這里使用了插入排序
         InsertSort.insertSort(bucket);
         for (int value : bucket) {
             arr[arrIndex++] = value;
         }
     }
     return arr;
 }
 /**
  * 擴容，并追加數(shù)據(jù)
  *
  * @param array
  * @param value
  */
 private static int[] appendBucket(int[] array, int value) {
     array = Arrays.copyOf(array, array.length + 1);
     array[array.length - 1] = value;
     return array;
 }

/**
 * 基數(shù)排序
 * @param array
 */
public static void radixSort(int[] array){
    // 獲取最高位
    int maxDigit = getMaxDigit(array);
    int mod = 10;
    int dev = 1;
    for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
        // 考慮負數(shù)的情況，這里擴展一倍隊列數(shù)，其中 [0-9]對應負數(shù)，[10-19]對應正數(shù) (bucket + 10)
        int[][] counter = new int[mod * 2][0];
        // 計數(shù)排序
        for (int j = 0; j < array.length; j++) {
            int bucket = ((array[j] % mod) / dev) + mod;
            counter[bucket] = appendBucket(counter[bucket], array[j]);
        }
        // 反向填充數(shù)組
        int pos = 0;
        for (int[] bucket : counter) {
            for (int value : bucket) {
                array[pos++] = value;
            }
        }
    }
}
/**
 * 獲取最高位數(shù)
 */
private static int getMaxDigit(int[] arr) {
    int maxValue = getMaxValue(arr);
    return getNumLength(maxValue);
}
/**
 * 獲取最大值
 * @param arr
 * @return
 */
private static int getMaxValue(int[] arr) {
    int maxValue = arr[0];
    for (int value : arr) {
        if (maxValue < value) {
            maxValue = value;
        }
    }
    return maxValue;
}
/**
 * 獲取整數(shù)的位數(shù)
 * @param num
 * @return
 */
protected static int getNumLength(long num) {
    if (num == 0) {
        return 1;
    }
    int lenght = 0;
    for (long temp = num; temp != 0; temp /= 10) {
        lenght++;
    }
    return lenght;
}
/**
 * 擴容，并追加數(shù)據(jù)
 *
 * @param array
 * @param value
 */
private static int[] appendBucket(int[] array, int value) {
    array = Arrays.copyOf(array, array.length + 1);
    array[array.length - 1] = value;
    return array;
}