計數排序+桶排序+基數排序詳講（思路+圖解+代碼詳解）

文章目錄

計數排序+桶排序+基數排序
- 一、計數排序
- - - - 概念：
      - 寫法一：
      - 寫法二：
- 二、桶排序
- - - 概念
    - 代碼
- 三、基數排序
- - 概念
  - 1.LSD排序法（最低位優先法）
  - 2.MSD排序法（最高位優先法）
- 基數排序VS基數排序VS桶排序

計數排序+桶排序+基數排序

一、計數排序

在這里插入圖片描述

時間復雜度：
空間復雜度：
穩定性：穩定

概念：

非基于比較的排序
計數排序又稱為鴿巢原理，是對哈希直接定址法的變形應用

1.統計相同元素出現的個數

2.根據統計的結果將序列回收到原來的序列中
計數排序使用的場景：給出指定范圍內的數據進行排序
使用場景：一組集中在某個范圍內的數據

寫法一：

通過遍歷計數數組，循環輸出計數數組存的次數

在這里插入圖片描述

1.遍歷數組找到最小值最大值
2.根據最大最小值，申請一個計數數組
3.遍歷待排數組進行計數
4.遍歷計數數組進行輸出

 /*** 計數排序*無法保證穩定* @param array*/public static void countSort2(int[] array) {//1.遍歷數組找到最大值和最小值int MAX = array[0];int MIN = array[0];for (int i = 1; i < array.length; i++) {if (array[i] > MAX) {MAX = array[i];}if (array[i] < MIN) {MIN = array[i];}}//2.根據最大最小值，申請一個計數數組int len = MAX - MIN + 1;//長度int[] count = new int[len];//3. 遍歷待排數組進行計數for (int i = 0; i < array.length; i++) {count[array[i] - MIN]++;}//4.遍歷計數數組進行輸出int index = 0;//array數組新的下標for (int i = 0; i < count.length; i++) {while (count[i] > 0) {array[index] = i + MIN;//+最小值，求出真正的數count[i]--;index++;}}}

寫法二：

寫定數組的大小，用臨時數組存儲結構
計算每個元素在排序后的數組中的最終位置
根據計數數組將元素放到臨時數組b中，實現排序
從后往前，根據原來數組的內容，在計數數組中找到要填寫在b數組中的位置，
計數數組記錄的不再是數字出現是次數，而是應該在數組中存放的位置下標

在這里插入圖片描述

 /*** 計數排序*穩定* @param array*/public static void countSort(int[] array) {int len = array.length;final int MAX = 256;//常量確定數組大小int[] c = new int[MAX];//計數數組int[] b = new int[MAX];//臨時數組，存放結果//統計每個元素的出現次，進行計數for (int i = 0; i < len; i++) {c[array[i]]++;// 將a[i]作為索引，對應計數數組c中的位置加1}// 計算每個元素在排序后的數組中的最終位置for (int i = 1; i < MAX; i++) {c[i] += c[i - 1];// 計數數組中每個元素的值等于它前面所有元素的值之和}// 根據計數數組將元素放到臨時數組b中，實現排序for (int i = len - 1; i >= 0; i--) {b[c[array[i]] - 1] = array[i];// 將a[i]放入臨時數組b中的正確位置c[array[i]]--;// 對應計數數組c中的位置減1，確保相同元素能夠放在正確的位置}// 將臨時數組b中的元素復制回原數組a，完成排序for (int i = 0; i < len; i++) {array[i] = b[i];}}

二、桶排序

概念

劃分多個范圍相同的區間，每個子區間自排序，最后合并

桶排序是計數排序的擴展版本，計數排序：每個桶只存儲單一鍵值
桶排序：每個桶存儲一定范圍的數值，確定桶的個數和范圍
將待排序數組中的元素映射到各個對應的桶中，對每個桶進行排序
最后將非空桶中的元素逐個放入原序列中

在這里插入圖片描述

代碼

    public static void bucketSort(int[] array){// 計算最大值與最小值int max = Integer.MIN_VALUE;int min = Integer.MAX_VALUE;for(int i = 0; i < array.length; i++){max = Math.max(max, array[i]);min = Math.min(min, array[i]);}// 計算桶的數量int bucketNum = (max - min) / array.length + 1;ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);for(int i = 0; i < bucketNum; i++){bucketArr.add(new ArrayList<Integer>());}// 將每個元素放入桶for(int i = 0; i < array.length; i++){int num = (array[i] - min) / (array.length);bucketArr.get(num).add(array[i]);}// 對每個桶進行排序for(int i = 0; i < bucketArr.size(); i++){Collections.sort(bucketArr.get(i));}// 將桶中的元素賦值到原序列int index = 0;for(int i = 0; i < bucketArr.size(); i++){for(int j = 0; j < bucketArr.get(i).size(); j++){array[index++] = bucketArr.get(i).get(j);}}}

三、基數排序

概念

基數排序是一種非比較型整數排序算法
將整數按位數切割成不同的數字，然后按每個位數分別比較
使用場景：按位分割進行排序，適用于大數據范圍排序，打破了計數排序的限制
穩定性：穩定
按位分割技巧：arr[i] / digit % 10，其中digit為10^n。

在這里插入圖片描述

1.LSD排序法（最低位優先法）

從最低位向最高位依次按位進行計數排序。
進出的次數和最大值的位數有關
桶可以用隊列來表示
數組的每個元素都是隊列

在這里插入圖片描述

1.先遍歷找到最大值
2.求出最高位

在這里插入圖片描述

    public static void radixSortR(int[] array) {//10進制數，有10個桶，每個桶最多存array.length個數int[][] bucket = new int[10][array.length];//桶里面要存的具體數值int[] bucketElementCounts = new int[10];//用來計算，統計每個桶所存的元素的個數，每個桶對應一個元素//1.求出最大數int MAX = array[0];for (int i = 1; i < array.length; i++) {if (array[i] > MAX) {MAX = array[i];}}//求最大值的位數，先變成字符串，求字符串長度int MAXCount = (MAX + "").length();//最大位數的個數，進行幾次計數排序for (int i = 0; i < MAXCount; i++) {//i代表第幾次排序//放進桶中for (int k = 0; k < array.length; k++) {//k相當于遍歷待排數值//array[k] /(int) Math.pow(10, i)%10 求出每次要比較位的數//求的是個位，并且是對應趟數的個位int value = (array[k] / (int) Math.pow(10, i)) % 10;//根據求出的位數，找到對應桶，放到對應桶的位置bucket[value][bucketElementCounts[value]] = array[k];//不管value 為多少，bucketElementCounts[value]的值都為0//相當于存到對應桶的0位bucket[value][0]bucketElementCounts[value]++; //從0->1//對應桶的技術數組開始計數}//取出每個桶中的元素，賦值給數組int index = 0;//array新的下標for (int k = 0; k < bucketElementCounts.length; k++) {//遍歷每個桶if (bucketElementCounts[k] != 0) {//桶里有元素for (int j = 0; j < bucketElementCounts[k]; j++) {//比那里每個桶的元素array[index] = bucket[k][j];index++;}}bucketElementCounts[k] =0;//每個桶遍歷完后，清空每個桶的元素；}}}

2.MSD排序法（最高位優先法）

在這里插入圖片描述

從最高位向最低位依次按位進行排序。
按位遞歸分組收集
1.查詢最大值，獲取最高位的基數
2.按位分組，存入桶中
3.組內元素數量>1,下一位遞歸分組
4.組內元素數量=1.收集元素

   /*** 基數排序--MSD--遞歸* @param array*/public static void radixSortMSD(int[] array) {//1.求出最大數int MAX = array[0];for (int i = 1; i < array.length; i++) {if (array[i] > MAX) {MAX = array[i];}}//求最大值的位數，先變成字符串，求字符串長度int MAXCount = (MAX + "").length();// 計算最大值的基數int radix = new Double(Math.pow(10, MAXCount - 1)).intValue();int[] arr = msdSort(array, radix);System.out.println(Arrays.toString(arr));}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];// 當前分組計數加1groupCounter[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;}