建站
咨詢
售后
建站咨詢
新聞中心
計(jì)數(shù)排序（Counting sort）于1954年由 Harold H. Seward提出，通過計(jì)數(shù)將時(shí)間復(fù)雜度降到了O(N)，是一種穩(wěn)定的線性時(shí)間排序算法，計(jì)數(shù)排序不是一個(gè)比較排序算法。
創(chuàng)新互聯(lián)是一家專注網(wǎng)站建設(shè)、網(wǎng)絡(luò)營銷策劃、微信小程序定制開發(fā)、電子商務(wù)建設(shè)、網(wǎng)絡(luò)推廣、移動(dòng)互聯(lián)開發(fā)、研究、服務(wù)為一體的技術(shù)型公司。公司成立十載以來，已經(jīng)為1000+成都地磅秤各業(yè)的企業(yè)公司提供互聯(lián)網(wǎng)服務(wù)。現(xiàn)在，服務(wù)的1000+客戶與我們一路同行，見證我們的成長；未來，我們一起分享成功的喜悅。
1. 計(jì)數(shù)排序的特征
當(dāng)輸入的元素是 n 個(gè) 0 到 k 之間的整數(shù)時(shí)，它的運(yùn)行時(shí)間是 Θ(n + k)。計(jì)數(shù)排序不是比較排序，排序的速度快于任何比較排序算法。
由于用來計(jì)數(shù)的數(shù)組C的長度取決于待排序數(shù)組中數(shù)據(jù)的范圍（等于待排序數(shù)組的最大值與最小值的差加上1），這使得計(jì)數(shù)排序?qū)τ跀?shù)據(jù)范圍很大的數(shù)組，需要大量時(shí)間和內(nèi)存。例如：計(jì)數(shù)排序是用來排序0到100之間的數(shù)字的最好的算法，但是它不適合按字母順序排序人名。但是，計(jì)數(shù)排序可以用在基數(shù)排序中的算法來排序數(shù)據(jù)范圍很大的數(shù)組。
通俗地理解，例如有 10 個(gè)年齡不同的人，統(tǒng)計(jì)出有 8 個(gè)人的年齡比 A 小，那 A 的年齡就排在第 9 位,用這個(gè)方法可以得到其他每個(gè)人的位置,也就排好了序。當(dāng)然，年齡有重復(fù)時(shí)需要特殊處理（保證穩(wěn)定性），這就是為什么最后要反向填充目標(biāo)數(shù)組，以及將每個(gè)數(shù)字的統(tǒng)計(jì)減去 1 的原因。
算法的步驟如下：
-
找出待排序的數(shù)組中最大和最小的元素
-
統(tǒng)計(jì)數(shù)組中每個(gè)值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組C的第i項(xiàng)
-
對(duì)所有的計(jì)數(shù)累加（從C中的第一個(gè)元素開始，每一項(xiàng)和前一項(xiàng)相加）
-
反向填充目標(biāo)數(shù)組：將每個(gè)元素i放在新數(shù)組的第C(i)項(xiàng)，每放一個(gè)元素就將C(i)減去1
代碼實(shí)現(xiàn)：
JavaScript
實(shí)例
function countingSort(arr, maxValue) {
var bucket = new Array(maxValue+1),
sortedIndex = 0;
arrLen = arr.length,
bucketLen = maxValue + 1;
for (var i = 0; i if (!bucket[arr[i]]) {
bucket[arr[i]] = 0;
}
bucket[arr[i]]++;
}
for (var j = 0; j while(bucket[j] > 0) {
arr[sortedIndex++] = j;
bucket[j]--;
}
}
return arr;
}
Python
實(shí)例
def countingSort(arr, maxValue):
bucketLen = maxValue+1
bucket = [0]*bucketLen
sortedIndex =0
arrLen = len(arr)
for i in range(arrLen):
if not bucket[arr[i]]:
bucket[arr[i]]=0
bucket[arr[i]]+=1
for j in range(bucketLen):
while bucket[j]>0:
arr[sortedIndex] = j
sortedIndex+=1
bucket[j]-=1
return arr
Go
實(shí)例
func countingSort(arr []int, maxValue int) []int {
bucketLen := maxValue + 1
bucket := make([]int, bucketLen) // 初始為0的數(shù)組
sortedIndex := 0
length := len(arr)
for i := 0; i for j := 0; j for bucket[j] > 0 {
arr[sortedIndex] = j
sortedIndex += 1
bucket[j] -= 1
}
}
return arr
}
Java
實(shí)例
public class CountingSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
// 對(duì) arr 進(jìn)行拷貝，不改變參數(shù)內(nèi)容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
int maxValue = getMaxValue(arr);
return countingSort(arr, maxValue);
}
private int[] countingSort(int[] arr, int maxValue) {
int bucketLen = maxValue + 1;
int[] bucket = new int[bucketLen];
for (int value : arr) {
bucket[value]++;
}
int sortedIndex = 0;
for (int j = 0; j while (bucket[j] > 0) {
arr[sortedIndex++] = j;
bucket[j]--;
}
}
return arr;
}
private int getMaxValue(int[] arr) {
int maxValue = arr[0];
for (int value : arr) {
if (maxValue return maxValue;
}
}
PHP
實(shí)例
function countingSort($arr, $maxValue = null)
{
if ($maxValue === null) {
$maxValue = max($arr);
}
for ($m = 0; $m $maxValue + 1; $m++) {
$bucket[] = null;
}
$arrLen = count($arr);
for ($i = 0; $i $arrLen; $i++) {
if (!array_key_exists($arr[$i], $bucket)) {
$bucket[$arr[$i]] = 0;
}
$bucket[$arr[$i]]++;
}
$sortedIndex = 0;
foreach ($bucket as $key => $len) {
if ($len !== null) $arr[$sortedIndex++] = $key;
if($len !== null){
for($j = 0; $j $len; $j++){
$arr[$sortedIndex++] = $key;
}
}
}
return $arr;
}
C
實(shí)例
#include
#include
#include
void print_arr(int *arr, int n) {
int i;
printf("%d", arr[0]);
for (i = 1; i printf(" %d", arr[i]);
printf("\n");
}
void counting_sort(int *ini_arr, int *sorted_arr, int n) {
int *count_arr = (int *) malloc(sizeof(int) * 100);
int i, j, k;
for (k = 0; k for (i = 0; i for (k = 1; k for (j = n; j > 0; j--)
sorted_arr[--count_arr[ini_arr[j - 1]]] = ini_arr[j - 1];
free(count_arr);
}
int main(int argc, char **argv) {
int n = 10;
int i;
int *arr = (int *) malloc(sizeof(int) * n);
int *sorted_arr = (int *) malloc(sizeof(int) * n);
srand(time(0));
for (i = 0; i printf("ini_array: ");
print_arr(arr, n);
counting_sort(arr, sorted_arr, n);
printf("sorted_array: ");
print_arr(sorted_arr, n);
free(arr);
free(sorted_arr);
return 0;
}
文章題目：詳解計(jì)數(shù)排序?qū)崿F(xiàn)方法
標(biāo)題網(wǎng)址：http://m.fisionsoft.com.cn/article/dpggdhs.html
