犧牲空間換時間的非比較排序之計數(shù)排序和基數(shù)排序-創(chuàng)新互聯(lián)

非比較排序試用于元素比較集中的序列。

成都創(chuàng)新互聯(lián)服務(wù)項目包括青山網(wǎng)站建設(shè)、青山網(wǎng)站制作、青山網(wǎng)頁制作以及青山網(wǎng)絡(luò)營銷策劃等。多年來，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢、行業(yè)經(jīng)驗、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，青山網(wǎng)站推廣取得了明顯的社會效益與經(jīng)濟效益。目前，我們服務(wù)的客戶以成都為中心已經(jīng)輻射到青山省份的部分城市，未來相信會繼續(xù)擴大服務(wù)區(qū)域并繼續(xù)獲得客戶的支持與信任！

1、計數(shù)排序

1. 找出待排序的數(shù)組中大和最小的元素

2. 統(tǒng)計數(shù)組中每個值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組C的第i項

3. 對所有的計數(shù)累加（從C中的第一個元素開始，每一項和前一項相加）

4. 反向填充目標(biāo)數(shù)組：將每個元素i放在新數(shù)組的第C(i)項，每放一個元素就將C(i)減去1

void CountSort(int *a, int size)
{
	assert(a);
	int max = a[0];
	int min = a[0];
	for (int i = 1; i < size; i++)
	{
		if (max < a[i])
			max = a[i];
		if (min > a[i])
			min = a[i];
	}
	int CountSize = max - min + 1;//該序列的范圍在min~max之間，所以開辟max-min+1
	int *CountArray = new int[CountSize];
	memset(CountArray,0,CountSize*sizeof(int));
	for (int i = 0; i < size; i++)
	{
		CountArray[a[i]-min]++;//比如序列在1萬到2萬之間，那么1萬應(yīng)該存在下標(biāo)為0的數(shù)組上
	}
	int index = 0;
	for (int i = 0; i <= CountSize; i++)
	{
		int count = CountArray[i];
		while (count-- > 0)
		{
			a[index++] = i+ min;//那么此時下標(biāo)為0的數(shù)，就是1萬
		}
	}
}

2、基數(shù)排序

基數(shù)排序指的是先把序列中的每個數(shù)中的個位排序，然后十位排序，直到超過序列中大數(shù)的位數(shù)

void DigitSort(int *a, int size)
{
	assert(a);
	int bit = 1, sum = 10;
	for (int i = 0; i < size; i++)
	{

		while (a[i] >= sum)   //取大數(shù)的位數(shù)
		{
			bit++;
			sum *= 10;
		}
	}
	int digit = 1;
	int *bucket = new int[size];
	while (digit <= bit)
	{
		int count[10] = { 0 };
		int position[10] = { 0 };
		for (int i = 0; i < size; i++)
		{
			int numbit = pow(10,digit-1);
			int bitvalue = (a[i] / numbit) % 10;
			count[bitvalue]++;  
		}
		for (int i = 1; i < 10; i++)
		{
			position[i] = position[i - 1] + count[i - 1];
		}
		for (int i = 0; i < size; i++)
		{
			int numbit = pow(10, digit - 1);
			int bitvalue = (a[i] / numbit) % 10;
			bucket[position[bitvalue]++] = a[i];
		}
		digit++;      
		memcpy(a,bucket,size*sizeof(int));
	}
}

創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國云服務(wù)器，動態(tài)BGP最優(yōu)骨干路由自動選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證， 機房獨有T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確進行流量調(diào)度，確保服務(wù)器高可用性。佳節(jié)活動現(xiàn)已開啟，新人活動云服務(wù)器買多久送多久。

標(biāo)題名稱：犧牲空間換時間的非比較排序之計數(shù)排序和基數(shù)排序-創(chuàng)新互聯(lián)
當(dāng)前URL：http://muchs.cn/article22/ceeccc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站策劃、靜態(tài)網(wǎng)站、網(wǎng)站設(shè)計、做網(wǎng)站、品牌網(wǎng)站建設(shè)、動態(tài)網(wǎng)站

廣告

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