??博主CSDN主頁:杭電碼農(nóng)-NEO??
?
?專欄分類:八大排序?qū)?
?
??代碼倉庫:NEO的學(xué)習(xí)日記??
?
??關(guān)注我??帶你學(xué)習(xí)排序知識
? ????

1. 前言

我們已經(jīng)學(xué)過的:
插入排序,希爾排序,選擇排序,堆排序
快速排序等等都是比較排序
也就是需要通過數(shù)據(jù)的比較來進行排序

而這里的計數(shù)排序比較特殊
它用的是一一對應(yīng)的映射關(guān)系
它不用比較數(shù)據(jù)就能排好序

本篇文章分享的是:
計數(shù)排序思路以及代碼全解

2. 計數(shù)排序基本思路

基本思路:

• 找出數(shù)組中的最大值和最小值
• 動態(tài)開辟一個空間
• 元素個數(shù)為最大值-最小值+1
• 再統(tǒng)計數(shù)據(jù)出現(xiàn)的次數(shù)

先定義一個無序數(shù)組:

int a[]={2,5,3,0,2,3,0,3};

此情況的分析:

1. 數(shù)組最大值為5,最小值為0
2. 開辟6個空間,統(tǒng)計數(shù)據(jù)出現(xiàn)的次數(shù)
3. 開辟的數(shù)組中:
4. 第一個元素對應(yīng)的是最小值0的個數(shù)
5. 最后一個元素對應(yīng)的是最大值5的個數(shù)
6. 中間的1,2,3,4不管原數(shù)組有沒有都寫上
7. 統(tǒng)計完后重新導(dǎo)入原數(shù)組

畫圖理解:

3. 特殊情況分析

?
特殊情況:最小值為0

上面舉例說明中,最小值是0.
所以開辟的數(shù)組中:
下標(biāo)為0的位置對應(yīng)數(shù)據(jù)0的個數(shù)
下標(biāo)為5的位置對應(yīng)數(shù)據(jù)5的個數(shù)
?

當(dāng)最小值不為0時:

假設(shè)我們再定義一個數(shù)組:

int a[]={1000,1200,1001,1500,1300,1301};

1. 最大值為1500,最小值為1000
2. 開辟一個長度為1500-1000+1=501的數(shù)組
   (注意:長度為501的數(shù)組下標(biāo)范圍為0~500)
3. 我們把開辟的數(shù)組稱為數(shù)組b
4. 此時b下標(biāo)為0的點對應(yīng)數(shù)據(jù)1000
5. b下標(biāo)為501的點對應(yīng)數(shù)據(jù)1500的個數(shù)

以此我們得出一個結(jié)論:

待排序數(shù)組中的元素X
映射到數(shù)組b的X-min的位置

?
畫圖理解:

4. 計數(shù)排序代碼實現(xiàn)

我們分步驟來實現(xiàn):

1. 函數(shù)參數(shù)以及返回值:

//計數(shù)排序
void CountSort(int* a, int n)
{
	//...
}

2. 找最值:

	int max = a[0];
	int min = a[0];
	//找最值
	for (int i = 1; i < n; i++)
	{
		if (max < a[i])
		{
			max = a[i];
		}
		if (a[i] < min)
		{
			min = a[i];
		}
	}
	int range = max - min + 1;//動態(tài)開辟數(shù)組的元素個數(shù)
	int* count = (int*)calloc(range, sizeof(int));//將元素初始化為0

2. 計數(shù):

//計數(shù)
	for (int i = 0; i < n; i++)
	{
		count[a[i] - min]++;
		//計數(shù)是去原數(shù)組中計數(shù)
	    //所以循環(huán)次數(shù)是n
	}

3. 根據(jù)次數(shù)進行排序:

	int j = 0;
	for (int i = 0; i < range; i++)
	{
		while (count[i]--)//只要count數(shù)組中元素不為0就賦值到原數(shù)組
		{
			a[j++] = i + min;
		}
	}
	free(count);//用完后釋放空間
	count = NULL;

5. 計數(shù)排序缺陷

問題:

當(dāng)數(shù)組中出現(xiàn)負數(shù)時.
比如:

int a[]={0,5,3,3,-1,2,0};

最小值是-1,最大值是5
這時開辟5-(-1)+1=7個空間有問題
?
解決方法:

我們知道-1的補碼是:(32位機器下)
11111111111111111111111111111111

只需要將 -1 看作是一個無符號數(shù)
即:11111111...的無符號數(shù)是
十進制的: 4,294,967,295.

這時這個數(shù)組變成了
最大值為4,294,967,295
最小值為0.
開辟4,294,967,296個空間
進行計數(shù)排序

?
總結(jié):

• 計數(shù)排序適合數(shù)據(jù)比較集中的數(shù)組
• 范圍較大,有負數(shù)或者浮點數(shù)就不適合了

6. 計數(shù)排序復(fù)雜度分析

1. 時間復(fù)雜度分析:

一共有三個板塊:

• 選最值.時間復(fù)雜度: O(N)
• 計數(shù).時間復(fù)雜度: O(N)
• 排序.時間復(fù)雜度: O(Range)

注:N代表原數(shù)組長度.
range代表動態(tài)開辟數(shù)組長度

計數(shù)排序總時間復(fù)雜度:

O( Max(N , Range) )

2. 空間復(fù)雜度分析:

開辟了一個大小為Range的空間

空間復(fù)雜度為:
O (Range)

7. 總結(jié)以及拓展

終于!
八大排序全部結(jié)束!

插入排序,希爾排序,選擇排序,堆排序
冒泡排序,快速排序,歸并排序
和本節(jié)講的計數(shù)排序.
在實際生活中都有很多運用
并且在面試時排序是必考的內(nèi)容!

要熟練掌握啊!
完結(jié)撒花!

當(dāng)然,排序部分還有穩(wěn)定性
各大排序的比較,與實際運用
這最后一步放在下一章講解文章來源地址http://www.zghlxwxcb.cn/news/detail-497869.html

到了這里，關(guān)于【八大排序(九)】計數(shù)排序-非比較排序法的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！