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

目錄

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

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

在 冒泡排序 之類(lèi)的排序中，問(wèn)題規(guī)模為n，又因?yàn)樾枰容^n次，所以平均時(shí)間復(fù)雜度為O(n²)。在 歸并排序、快速排序 之類(lèi)的排序中，問(wèn)題規(guī)模通過(guò)分治法消減為logN次，所以時(shí)間復(fù)雜度平均 O(nlogn) 。

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

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

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

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

計(jì)數(shù)排序

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

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

過(guò)程分析

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

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

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

算法流程（1）

需要三個(gè)數(shù)組:

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

輔助計(jì)數(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í)例化輔助計(jì)數(shù)數(shù)組help，help數(shù)組中每個(gè)下標(biāo)對(duì)應(yīng)arr中的一個(gè)元素， help用來(lái)記錄每個(gè)元素出現(xiàn)的次數(shù)

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

4.根據(jù) help 數(shù)組求得排序后的數(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];
  
  //找出每個(gè)數(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）

需要三個(gè)數(shù)組:

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

輔助計(jì)數(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í)例化輔助計(jì)數(shù)數(shù)組help， help用來(lái)記錄每個(gè)元素之前出現(xiàn)的元素個(gè)數(shù)

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

4.根據(jù) help 數(shù)組求得排序后的數(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];
  
  //找出每個(gè)數(shù)字出現(xiàn)的次數(shù)
  for(int i = 0; i < arr.length; i++){
    int mapPos = arr[i] - min;
    help[mapPos]++;
  }
  
  //計(jì)算每個(gè)數(shù)字應(yīng)該在排序后數(shù)組中應(yīng)該處于的位置
  for(int i = 1; i < help.length; i++){
    help[i] = help[i-1] + help[i];
  }
  
  //根據(jù)help數(shù)組進(jìn)行排序
  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ì)數(shù)排序，并非標(biāo)準(zhǔn)的桶排序。有問(wèn)題的文章：

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

桶排序算法

排序算法 之 桶排序

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

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

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

過(guò)程分析

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

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

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

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

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

4.每個(gè)桶各自排序

5.遍歷桶數(shù)組，把排序好的元素放進(jìn)輸出數(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>());
  }
  
  //將每個(gè)元素放入桶
  for(int i = 0; i < arr.length; i++){
    int num = (arr[i] - min) / (arr.length);
    bucketArr.get(num).add(arr[i]);
  }
  
  //對(duì)每個(gè)桶進(jìn)行排序
  for(int i = 0; i < bucketArr.size(); i++){
    Collections.sort(bucketArr.get(i));
  }
  
  System.out.println(bucketArr.toString());
  
}

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

最新評(píng)論