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

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

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

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

目錄

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

常見(jiàn)的快速排序、歸并排序、堆排序、冒泡排序等屬于比較排序。在排序的最終結(jié)果里，元素之間的次序依賴(lài)于它們之間的比較。每個(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)行排序。可以說(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;
}

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

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

廣告

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