??前言

什么是計(jì)數(shù)排序？計(jì)數(shù)排序的思想是什么？它是如何實(shí)現(xiàn)的？

本文會(huì)對(duì)計(jì)數(shù)排序進(jìn)行由淺入深的探究，讓你徹底掌握計(jì)數(shù)排序！

???計(jì)數(shù)排序的概念

??什么是計(jì)數(shù)排序？

? 計(jì)數(shù)排序又稱為鴿巢原理，是對(duì)哈希直接定址法的變形應(yīng)用。

? 統(tǒng)計(jì)每個(gè)元素出現(xiàn)的次數(shù)，然后根據(jù)元素的大小順序?qū)⑺鼈兎湃胝_的位置。

??計(jì)數(shù)排序思想

計(jì)數(shù)排序是一種小眾的排序,它適合于數(shù)據(jù)密集的場(chǎng)景,按最大數(shù)的數(shù)值來開空間。

?絕對(duì)映射

假設(shè)現(xiàn)有一組數(shù)據(jù),最大的數(shù)據(jù)是1000,那么便會(huì)開一千個(gè)大小的空間,這種屬于絕對(duì)映射,在極端的場(chǎng)景下,極易造成空間上的浪費(fèi)，比如現(xiàn)在有5,99,88,1000,8888,452,635,82,777,555,只有10個(gè)數(shù)但是最大的數(shù)是8888因此要開8888大小的空間,剩余的空間全部都浪費(fèi)了。

?相對(duì)映射

因此絕大多數(shù)情況下,都會(huì)使用相對(duì)映射。

具體的步驟如下：

1. 找出待排序數(shù)組中的最大值和最小值，并創(chuàng)建一個(gè)計(jì)數(shù)數(shù)組，長(zhǎng)度為最大值和最小值之差加1。
2. 遍歷待排序數(shù)組，統(tǒng)計(jì)每個(gè)元素出現(xiàn)的次數(shù)，并將次數(shù)存儲(chǔ)在計(jì)數(shù)數(shù)組的相應(yīng)位置上。
3. 對(duì)計(jì)數(shù)數(shù)組進(jìn)行累加操作，得到每個(gè)元素在排序后數(shù)組中的最終位置。
4. 創(chuàng)建一個(gè)與待排序數(shù)組長(zhǎng)度相同的臨時(shí)數(shù)組，用于存儲(chǔ)排序后的結(jié)果。
5. 從后向前遍歷待排序數(shù)組，根據(jù)計(jì)數(shù)數(shù)組中每個(gè)元素的值，將元素放入臨時(shí)數(shù)組的相應(yīng)位置上。
6. 將臨時(shí)數(shù)組中的元素復(fù)制回待排序數(shù)組，完成排序。

???計(jì)數(shù)排序的實(shí)現(xiàn)

??實(shí)現(xiàn)思路

1. 找到數(shù)組中的最小值和最大值，以確定計(jì)數(shù)數(shù)組的大小。
2. 然后，根據(jù)最小值和最大值計(jì)算計(jì)數(shù)數(shù)組的大小，并分配內(nèi)存空間。
3. 接下來，將計(jì)數(shù)數(shù)組的所有元素初始化為0。
4. 然后，遍歷原數(shù)組，統(tǒng)計(jì)每個(gè)元素出現(xiàn)的次數(shù)，將統(tǒng)計(jì)結(jié)果保存在計(jì)數(shù)數(shù)組中。
5. 接著，使用兩個(gè)循環(huán)，將計(jì)數(shù)數(shù)組中的元素按照次數(shù)依次放回原數(shù)組中。
6. 最后，釋放計(jì)數(shù)數(shù)組的內(nèi)存空間。

??代碼實(shí)現(xiàn)

//計(jì)數(shù)排序
void CountSort(int* a, int n)
{
	int min = a[0];
	int max = a[0];
	for (int i = 0; i < n; i++)
	{
		if (a[i] < min)
		{
			min = a[i];
		}
		if (a[i] > max)
		{
			max = a[i];
		}
	}
	int range = max - min + 1;
	int* count = (int*)malloc(sizeof(int) * range);
	if (count == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	memset(count, 0, sizeof(int) * range);
	for (int i = 0; i < n; i++)
	{
		count[a[i] - min]++;
	}
	int j = 0;
	for (int i = 0; i < range; i++)
	{
		while (count[i]--)
		{
			a[j++] = i + min;
		}
	}
}

??代碼解析

1. 尋找最小值和最大值： 首先，通過循環(huán)遍歷輸入數(shù)組 a，找到數(shù)組中的最小值 min 和最大值 max。這是為了確定排序范圍。
2. 確定排序范圍： 計(jì)算排序范圍 range，即 (max - min + 1)，這表示需要排序的整數(shù)范圍。
3. 創(chuàng)建計(jì)數(shù)數(shù)組： 使用 malloc 函數(shù)為計(jì)數(shù)數(shù)組 count 分配內(nèi)存，該數(shù)組的大小是排序范圍 range。計(jì)數(shù)數(shù)組用于存儲(chǔ)每個(gè)整數(shù)在輸入數(shù)組中出現(xiàn)的次數(shù)。
4. 初始化計(jì)數(shù)數(shù)組： 使用 memset 函數(shù)將計(jì)數(shù)數(shù)組 count 中的所有元素初始化為0。
5. 計(jì)數(shù)： 遍歷輸入數(shù)組 a，對(duì)于每個(gè)整數(shù) a[i]，將其減去 min 的值作為索引，然后在計(jì)數(shù)數(shù)組中對(duì)應(yīng)索引位置的值加1。這一步會(huì)統(tǒng)計(jì)每個(gè)整數(shù)在輸入數(shù)組中出現(xiàn)的次數(shù)。
6. 重構(gòu)排序數(shù)組： 使用兩個(gè)循環(huán)，首先遍歷計(jì)數(shù)數(shù)組 count，然后在內(nèi)部循環(huán)中，根據(jù)計(jì)數(shù)數(shù)組中的值，將相應(yīng)數(shù)量的整數(shù)值還原到原始輸入數(shù)組 a。這將完成排序過程。

???計(jì)數(shù)排序特性總結(jié)

??時(shí)間復(fù)雜度：

計(jì)數(shù)排序的時(shí)間復(fù)雜度為 O(n+k)，其中 n 是輸入數(shù)組的大小，k 是整數(shù)的范圍。它具有線性時(shí)間復(fù)雜度的優(yōu)點(diǎn)，適用于整數(shù)排序，特別是當(dāng)整數(shù)范圍相對(duì)較小且分布均勻時(shí)。

??空間復(fù)雜度

計(jì)數(shù)排序的空間復(fù)雜度取決于整數(shù)范圍，為 O(k)。因此，它需要額外的空間來存儲(chǔ)計(jì)數(shù)數(shù)組，當(dāng)整數(shù)范圍較大時(shí)可能會(huì)占用較多內(nèi)存。

??穩(wěn)定性

計(jì)數(shù)排序是一種穩(wěn)定的排序算法。穩(wěn)定性意味著具有相同值的元素在排序后仍保持相對(duì)順序不變。在計(jì)數(shù)排序中，具有相同值的元素會(huì)按照它們?cè)谳斎霐?shù)組中的順序被放置在輸出數(shù)組中。

??適用性限制

計(jì)數(shù)排序僅適用于整數(shù)排序，特別是當(dāng)整數(shù)范圍相對(duì)較小且分布均勻時(shí)。它不適用于排序包含負(fù)數(shù)或浮點(diǎn)數(shù)的數(shù)組。此外，如果整數(shù)范圍過大，可能會(huì)導(dǎo)致內(nèi)存占用過多。

??不適用于大規(guī)模數(shù)據(jù)

盡管計(jì)數(shù)排序具有線性時(shí)間復(fù)雜度的優(yōu)點(diǎn)，但它對(duì)于大規(guī)模數(shù)據(jù)集的排序可能并不理想。當(dāng)整數(shù)范圍非常大且分布不均勻時(shí)，計(jì)數(shù)排序的性能可能會(huì)受到限制。

??總結(jié)

計(jì)數(shù)排序適用于特定范圍內(nèi)的整數(shù)排序，并且在這種情況下具有穩(wěn)定的性能表現(xiàn)。然而，在應(yīng)用計(jì)數(shù)排序時(shí)，需要仔細(xì)考慮整數(shù)范圍和數(shù)據(jù)集的分布情況，以確保不會(huì)出現(xiàn)內(nèi)存占用過大或性能下降的情況。

???全篇總結(jié)

本章專門對(duì)計(jì)數(shù)排序從概念到實(shí)現(xiàn)，進(jìn)行了細(xì)致入微的講解，期望對(duì)你理解掌握計(jì)數(shù)有所幫助！

看到這里希望給博主留個(gè):??點(diǎn)贊??收藏??關(guān)注！
你們的點(diǎn)贊就是博主更新最大的動(dòng)力！
有問題可以評(píng)論或者私信呢秒回哦。

文章來源地址http://www.zghlxwxcb.cn/news/detail-738904.html

到了這里，關(guān)于【排序算法】 計(jì)數(shù)排序(非比較排序)詳解！了解哈希思想！的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！