創(chuàng)新互聯(lián)www.cdcxhl.cn八線動態(tài)BGP香港云服務器提供商，新人活動買多久送多久，劃算不套路！

創(chuàng)新互聯(lián)專業(yè)成都做網(wǎng)站、網(wǎng)站制作，集網(wǎng)站策劃、網(wǎng)站設計、網(wǎng)站制作于一體，網(wǎng)站seo、網(wǎng)站優(yōu)化、網(wǎng)站營銷、軟文推廣等專業(yè)人才根據(jù)搜索規(guī)律編程設計，讓網(wǎng)站在運行后，在搜索中有好的表現(xiàn)，專業(yè)設計制作為您帶來效益的網(wǎng)站！讓網(wǎng)站建設為您創(chuàng)造效益。

本篇文章給大家分享的是有關如何利用java 實現(xiàn)一個計數(shù)排序功能，小編覺得挺實用的，因此分享給大家學習，希望大家閱讀完這篇文章后可以有所收獲，話不多說，跟著小編一起來看看吧。

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

目錄

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

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

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

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

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

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

非比較排序時間復雜度底，但由于非比較排序需要占用空間來確定唯一位置。所以對數(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ù)組中的位置上。假設有5個數(shù)小于 arr[i]，所以 arr[i] 應該放在數(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ù)組中每個下標對應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;
}

網(wǎng)站欄目：如何利用java實現(xiàn)一個計數(shù)排序功能-創(chuàng)新互聯(lián)
分享URL：http://www.chinadenli.net/article48/idsep.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供營銷型網(wǎng)站建設、外貿(mào)建站、全網(wǎng)營銷推廣、網(wǎng)站設計公司、網(wǎng)站營銷、App開發(fā)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)