常見(jiàn)的排序算法（四）(歸并排序,計(jì)數(shù)排序,基數(shù)排序)-創(chuàng)新互聯(lián)

 歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱(chēng)為二路歸并。

10年積累的成都做網(wǎng)站、網(wǎng)站建設(shè)經(jīng)驗(yàn)，可以快速應(yīng)對(duì)客戶(hù)對(duì)網(wǎng)站的新想法和需求。提供各種問(wèn)題對(duì)應(yīng)的解決方案。讓選擇我們的客戶(hù)得到更好、更有力的網(wǎng)絡(luò)服務(wù)。我雖然不認(rèn)識(shí)你，你也不認(rèn)識(shí)我。但先網(wǎng)站策劃后付款的網(wǎng)站建設(shè)流程，更有平塘免費(fèi)網(wǎng)站建設(shè)讓你可以放心的選擇與我們合作。

（如果讀者不太了解什么叫分治法，可以去看看《算法導(dǎo)論》第一二章。）

歸并過(guò)程為：比較a[i]和a[j]的大小，若a[i]≤a[j]，則將第一個(gè)有序表中的元素a[i]復(fù)制到r[k]中，并令i和k分別加上1；否則將第二個(gè)有序表中的元素a[j]復(fù)制到r[k]中，并令j和k分別加上1，如此循環(huán)下去，直到其中一個(gè)有序表取完，然后再將另一個(gè)有序表中剩余的元素復(fù)制到r中從下標(biāo)k到下標(biāo)t的單元。歸并排序的算法我們通常用遞歸實(shí)現(xiàn)，先把待排序區(qū)間[s,t]以中點(diǎn)二分，接著把左邊子區(qū)間排序，再把右邊子區(qū)間排序，最后把左區(qū)間和右區(qū)間用一次歸并操作合并成有序的區(qū)間[s,t]。

代碼如下：

void Merge(int* a,int left, int mid, int right, int* tem)
{
	assert(a);
	assert(tem);
	int i = 0;
	int indix = mid+1;
	int begin = left;
	while(begin <= mid && indix <= right)
	{
		if(a[begin] > a[indix])
			tem[i++] = a[indix++];
		else
			tem[i++] = a[begin++];
	}
	while(begin <= mid) 
	tem[i++] = a[begin++];

	while( indix <= right)
		tem[i++] = a[indix++];

	for(int j = 0; j < i; j++)   將排好序的數(shù)組重新賦值給a
	{
		a[j+left] = tem[j];
	}
}

void mergsort(int* a,int left, int right,int*  tem)
{
	assert(a);
	assert(tem);
	int mid;
	if(left < right)
	{
		mid = (left + right)/2;
		mergsort(a,left,mid,tem);
		mergsort(a,mid+1,right,tem);
		Merge(a,left,mid,right,tem);
	}
}

bool MergeSort(int* a, int n)  
{  
	assert(a);
    int *p = new int[n];   開(kāi)辟一個(gè)跟a一樣大的空間，用來(lái)存放排序好的數(shù)據(jù)。
    if (p == NULL)  
        return false;  
    mergsort(a, 0, n - 1, p);  
    delete[] p;  
    return true;  
}

以上是遞歸算法

既然有遞歸算法，那也就有非遞歸的算法

void merge_sort(int * a, int length)
{
	assert(a);
        int i, left_min, left_max, right_min, right_max, next;  
        int *tmp = (int*)malloc(sizeof(int) * length); 

        if (tmp == NULL)
		{  
                printf("Error: out of memory\n");  
        }  

        for (i = 1; i < length; i *= 2)  
                for (left_min = 0; left_min < length - i; left_min = right_max)
				{   
                        right_min = left_max = left_min + i;  
                        right_max = left_max + i;  
                        if (right_max > length)  
                                right_max = length;  
                        next = 0;  

                        while (left_min < left_max && right_min < right_max)  
                                tmp[next++] = a[left_min] > a[right_min] ? 
								a[right_min++] : a[left_min++];  

                        while (left_min < left_max)  
                                a[--right_min] = a[--left_max]; 

                        while (next > 0)  
                                a[--right_min] = tmp[--next];  
                }  
        free(tmp);  
}

由此便可以看出遞歸和非遞歸在思想上是一致的，只是實(shí)現(xiàn)的方法不同罷了。

時(shí)間復(fù)雜度為O(nlogn) 這是該算法中最好、最壞和平均的時(shí)間性能。

空間復(fù)雜度為 O(n)

比較操作的次數(shù)介于(nlogn) / 2和nlogn - n + 1。

賦值操作的次數(shù)是(2nlogn)。歸并算法的空間復(fù)雜度為：0 (n)

歸并排序比較占用內(nèi)存，但卻是一種效率高且穩(wěn)定的算法。

計(jì)數(shù)排序

計(jì)數(shù)排序是一個(gè)非基于比較的排序算法，該算法于1954年由 Harold H. Seward 提出。它的優(yōu)勢(shì)在于在對(duì)一定范圍內(nèi)的整數(shù)排序時(shí)，它的復(fù)雜度為Ο(n+k)（其中k是整數(shù)的范圍），快于任何比較排序算法。

算法思想編輯

計(jì)數(shù)排序?qū)斎氲臄?shù)據(jù)有附加的限制條件：

1、輸入的線性表的元素屬于有限偏序集S；

2、設(shè)輸入的線性表的長(zhǎng)度為n，|S|=k（表示集合S中元素的總數(shù)目為k），則k=O(n)。

在這兩個(gè)條件下，計(jì)數(shù)排序的復(fù)雜性為O(n)。

計(jì)數(shù)排序的基本思想是對(duì)于給定的輸入序列中的每一個(gè)元素x，確定該序列中值小于x的元素的個(gè)數(shù)（此處并非比較各元素的大小，而是通過(guò)對(duì)元素值的計(jì)數(shù)和計(jì)數(shù)值的累加來(lái)確定）。一旦有了這個(gè)信息，就可以將x直接存放到最終的輸出序列的正確位置上。例如，如果輸入序列中只有17個(gè)元素的值小于x的值，則x可以直接存放在輸出序列的第18個(gè)位置上。當(dāng)然，如果有多個(gè)元素具有相同的值時(shí)，我們不能將這些元素放在輸出序列的同一個(gè)位置上，因此，上述方案還要作適當(dāng)?shù)男薷摹?/p>

算法過(guò)程編輯

假設(shè)輸入的線性表L的長(zhǎng)度為n，L=L1,L2,..,Ln；線性表的元素屬于有限偏序集S，|S|=k且k=O(n)，S={S1,S2,..Sk}；則計(jì)數(shù)排序可以描述如下：

1、掃描整個(gè)集合S，對(duì)每一個(gè)Si∈S，找到在線性表L中小于等于Si的元素的個(gè)數(shù)T(Si)；

2、掃描整個(gè)線性表L，對(duì)L中的每一個(gè)元素Li，將Li放在輸出線性表的第T(Li)個(gè)位置上，并將T(Li)減1。

void CountSort(int* a,int size)
{
	int max = a[0];
	int min = a[0];
	for(int i = 1; i<size; i++)
	{
		if(a[i] > max)
			max = a[i];

		if(a[i] < min)
			min = a[i];
	}

	int* tem = new int[max-min +1]();
	
	for(int i =0; i < size; i++)
		tem[a[i] - min]++;

	int indix = 0;
	for(int i = 0; i< (max-min +1); i++)
	{
		
		while(tem[i] > 0)
		{
			a[indix++]= i + min;
			--tem[i];
		}
	}

	delete[] tem;
}

基數(shù)排序

基數(shù)排序（radix sort）屬于“分配式排序”（distribution sort），又稱(chēng)“桶子法”（bucket sort）或bin sort，顧名思義，它是透過(guò)鍵值的部份資訊，將要排序的元素分配至某些“桶”中，藉以達(dá)到排序的作用，基數(shù)排序法是屬于穩(wěn)定性的排序，其時(shí)間復(fù)雜度為O (nlog(r)m)，其中r為所采取的基數(shù)，而m為堆數(shù)，在某些時(shí)候，基數(shù)排序法的效率高于其它的穩(wěn)定性排序法。

其實(shí)他的實(shí)現(xiàn)，就想稀疏實(shí)現(xiàn)稀疏矩陣一樣，讀者可以在此借鑒，并且與之比較。

int Maxbit(int* a, int size)  //計(jì)算數(shù)組中大值得位數(shù)。
{
	int bit = 1;
	int num = 10;
	for(int i =0; i<size;i++)
	{
		if(a[i] > num)
		{
			++bit;
			num *= 10;
		}
	}
	return bit;
}

void RadixSort(int* a, int size)
{
	int indix = Maxbit(a,size);
	int* tem = new int[size];    //記錄該值
	int* count = new int[size];  //記錄次數(shù)
	int radix = 1;            進(jìn)位所用的值
	for(int i = 0; i<indix;i++)
	{
		for(int j = 0;j < size; j++)
		{
			count[j] = 0;
		}

		for(int j = 0; j<size; j++)
		{
			int k = (a[j]/radix) % 10;
			count[k]++;
		}
		for(int j = 1; j<size; j++)
			count[j] = count[j-1] +count [j];
		for(int j= size-1;j>=0;j--)
		{
			int k = (a[j]/radix) % 10;
			tem[count[k] -1] = a[j];
			count[k]--;
		}

		for(int j = 0;j < size; j++)
		{
			a[j] = tem[j];
		}

		radix = radix * 10;
		
	}

	delete[] tem;
	delete[] count;
}

以上形象圖解可看上篇博文中的超鏈接，給予讀者形象的理解和解答

這篇博文列舉了歸并排序,計(jì)數(shù)排序 , 基數(shù)排序，基本可以掌握其中概要，管中窺豹，不求甚解。如果你有任何建議或者批評(píng)和補(bǔ)充，請(qǐng)留言指出，不勝感激，更多參考請(qǐng)移步互聯(lián)網(wǎng)。

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

網(wǎng)頁(yè)題目：常見(jiàn)的排序算法（四）(歸并排序,計(jì)數(shù)排序,基數(shù)排序)-創(chuàng)新互聯(lián)
瀏覽路徑：http://bm7419.com/article40/dgdoho.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站建設(shè)、手機(jī)網(wǎng)站建設(shè)、移動(dòng)網(wǎng)站建設(shè)、網(wǎng)站策劃、做網(wǎng)站、搜索引擎優(yōu)化

廣告

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