java 實現(xiàn)計數(shù)排序和桶排序?qū)嵗a

目錄

比較和非比較的區(qū)別

常見的快速排序、歸并排序、堆排序、冒泡排序等屬于比較排序。在排序的最終結(jié)果里，元素之間的次序依賴于它們之間的比較。每個數(shù)都必須和其他數(shù)進行比較，才能確定自己的位置。

在 冒泡排序 之類的排序中，問題規(guī)模為n，又因為需要比較n次，所以平均時間復(fù)雜度為O(n²)。在 歸并排序、快速排序 之類的排序中，問題規(guī)模通過分治法消減為logN次，所以時間復(fù)雜度平均 O(nlogn) 。

比較排序的優(yōu)勢是，適用于各種規(guī)模的數(shù)據(jù)，也不在乎數(shù)據(jù)的分布，都能進行排序?？梢哉f，比較排序適用于一切需要排序的情況。

計數(shù)排序、基數(shù)排序、桶排序則屬于非比較排序。非比較排序是通過確定每個元素之前，應(yīng)該有多少個元素來排序。針對數(shù)組arr，計算arr[i]之前有多少個元素，則唯一確定了arr[i]在排序后數(shù)組中的位置。

非比較排序只要確定每個元素之前的已有的元素個數(shù)即可，所有一次遍歷即可解決。算法時間復(fù)雜度 O(n) 。

非比較排序時間復(fù)雜度底，但由于非比較排序需要占用空間來確定唯一位置。所以對數(shù)據(jù)規(guī)模和數(shù)據(jù)分布有一定的要求。

計數(shù)排序

計數(shù)排序適用數(shù)據(jù)范圍

計數(shù)排序需要占用大量空間，它僅適用于數(shù)據(jù)比較集中的情況。比如 [0~100]，[10000~19999] 這樣的數(shù)據(jù)。

過程分析

計數(shù)排序的基本思想是： 對每一個輸入的元素arr[i]，確定小于 arr[i] 的元素個數(shù)。

所以可以直接把 arr[i] 放到它輸出數(shù)組中的位置上。假設(shè)有5個數(shù)小于 arr[i]，所以 arr[i] 應(yīng)該放在數(shù)組的第6個位置上。

下面給出兩種實現(xiàn)：

算法流程（1）

需要三個數(shù)組:

待排序數(shù)組 int[] arr = new int[]{4,3,6,3,5,1};

輔助計數(shù)數(shù)組 int[] help = new int[max - min + 1]; //該數(shù)組大小為待排序數(shù)組中的最大值減最小值+1

輸出數(shù)組 int[] res = new int[arr.length];

1.求出待排序數(shù)組的最大值max=6， 最小值min=1

2.實例化輔助計數(shù)數(shù)組help，help數(shù)組中每個下標對應(yīng)arr中的一個元素， help用來記錄每個元素出現(xiàn)的次數(shù)

3.計算 arr 中每個元素在help中的位置 position = arr[i] - min，此時 help = [1,0,2,1,1,1]; （3出現(xiàn)了兩次，2未出現(xiàn)）

4.根據(jù) help 數(shù)組求得排序后的數(shù)組，此時 res = [1,3,3,4,5,6]

public static int[] countSort1(int[] arr){
  if (arr == null || arr.length == 0) {
    return null;
  }
  
  int max = Integer.MIN_VALUE;
  int min = Integer.MAX_VALUE;
  
  //找出數(shù)組中的最大最小值
  for(int i = 0; i < arr.length; i++){
    max = Math.max(max, arr[i]);
    min = Math.min(min, arr[i]);
  }
  
  int help[] = new int[max];
  
  //找出每個數(shù)字出現(xiàn)的次數(shù)
  for(int i = 0; i < arr.length; i++){
    int mapPos = arr[i] - min;
    help[mapPos]++;
  }
  
  int index = 0;
  for(int i = 0; i < help.length; i++){
    while(help[i]-- > 0){
      arr[index++] = i+min;
    }
  }
  
  return arr;
}

算法流程（2）

需要三個數(shù)組:

待排序數(shù)組 int[] arr = new int[]{4,3,6,3,5,1};

輔助計數(shù)數(shù)組 int[] help = new int[max - min + 1]; //該數(shù)組大小為待排序數(shù)組中的最大值減最小值+1

輸出數(shù)組 int[] res = new int[arr.length];

1.求出待排序數(shù)組的最大值max=6， 最小值min=1

2.實例化輔助計數(shù)數(shù)組help， help用來記錄每個元素之前出現(xiàn)的元素個數(shù)

3.計算 arr 每個數(shù)字應(yīng)該在排序后數(shù)組中應(yīng)該處于的位置，此時 help = [1,1,4,5,6,7];

4.根據(jù) help 數(shù)組求得排序后的數(shù)組，此時 res = [1,3,3,4,5,6]

public static int[] countSort2(int[] arr){
  int max = Integer.MIN_VALUE;
  int min = Integer.MAX_VALUE;
  
  //找出數(shù)組中的最大最小值
  for(int i = 0; i < arr.length; i++){
    max = Math.max(max, arr[i]);
    min = Math.min(min, arr[i]);
  }
  
  int[] help = new int[max - min + 1];
  
  //找出每個數(shù)字出現(xiàn)的次數(shù)
  for(int i = 0; i < arr.length; i++){
    int mapPos = arr[i] - min;
    help[mapPos]++;
  }
  
  //計算每個數(shù)字應(yīng)該在排序后數(shù)組中應(yīng)該處于的位置
  for(int i = 1; i < help.length; i++){
    help[i] = help[i-1] + help[i];
  }
  
  //根據(jù)help數(shù)組進行排序
  int res[] = new int[arr.length];
  for(int i = 0; i < arr.length; i++){
    int post = --help[arr[i] - min];
    res[post] = arr[i];
  }
  
  return res;
}

桶排序

網(wǎng)絡(luò)流傳桶排序算法勘誤

網(wǎng)絡(luò)各博文中流程的桶排序算法實際上都是計數(shù)排序，并非標準的桶排序。有問題的文章：

經(jīng)典排序算法 - 桶排序Bucket sort

桶排序算法

排序算法 之 桶排序

最快最簡單的排序算法：桶排序
桶排序適用數(shù)據(jù)范圍

桶排序可用于最大最小值相差較大的數(shù)據(jù)情況，比如[9012,19702,39867,68957,83556,102456]。

但桶排序要求數(shù)據(jù)的分布必須均勻，否則可能導(dǎo)致數(shù)據(jù)都集中到一個桶中。比如[104,150,123,132,20000], 這種數(shù)據(jù)會導(dǎo)致前4個數(shù)都集中到同一個桶中。導(dǎo)致桶排序失效。

過程分析

桶排序的基本思想是： 把數(shù)組 arr 劃分為n個大小相同子區(qū)間（桶），每個子區(qū)間各自排序，最后合并 。

計數(shù)排序是桶排序的一種特殊情況，可以把計數(shù)排序當(dāng)成每個桶里只有一個元素的情況。

1.找出待排序數(shù)組中的最大值max、最小值min

2.我們使用 動態(tài)數(shù)組ArrayList 作為桶，桶里放的元素也用 ArrayList 存儲。桶的數(shù)量為(max-min)/arr.length+1

3.遍歷數(shù)組 arr，計算每個元素 arr[i] 放的桶

4.每個桶各自排序

5.遍歷桶數(shù)組，把排序好的元素放進輸出數(shù)組

public static void bucketSort(int[] arr){
  
  int max = Integer.MIN_VALUE;
  int min = Integer.MAX_VALUE;
  for(int i = 0; i < arr.length; i++){
    max = Math.max(max, arr[i]);
    min = Math.min(min, arr[i]);
  }
  
  //桶數(shù)
  int bucketNum = (max - min) / arr.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 < arr.length; i++){
    int num = (arr[i] - min) / (arr.length);
    bucketArr.get(num).add(arr[i]);
  }
  
  //對每個桶進行排序
  for(int i = 0; i < bucketArr.size(); i++){
    Collections.sort(bucketArr.get(i));
  }
  
  System.out.println(bucketArr.toString());
  
}

感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！

最新評論