數(shù)據(jù)結(jié)構(gòu)—八大排序-創(chuàng)新互聯(lián)

本文所有排序以升序?yàn)槔?/p>創(chuàng)新互聯(lián)公司自2013年起，先為通道等服務(wù)建站，通道等地企業(yè)，進(jìn)行企業(yè)商務(wù)咨詢服務(wù)。為通道企業(yè)網(wǎng)站制作PC+手機(jī)+微官網(wǎng)三網(wǎng)同步一站式服務(wù)解決您的所有建站問題。

目錄

一、直接插入排序

二、希爾排序

三、選擇排序??

四、堆排序

五、冒泡排序

六、快速排序

遞歸版本

1、hoare版本

2、挖坑法

3、前后指針法（推薦這種寫法）

快速排序的優(yōu)化

1、三數(shù)取中法

2、遞歸到小子區(qū)間?

非遞歸版本

七、歸并排序

遞歸實(shí)現(xiàn)：

非遞歸實(shí)現(xiàn)：

八、計(jì)數(shù)排序?

八大排序的穩(wěn)定性總結(jié)：

一、直接插入排序

基本思想：我們平時(shí)玩撲克牌時(shí)，摸牌階段的排序就用到了插入排序的思想

1、當(dāng)插入第n個(gè)元素時(shí)，前面的n-1個(gè)數(shù)已經(jīng)有序

2、用這第n個(gè)數(shù)與前面的n-1個(gè)數(shù)比較，找到要插入的位置，將其插入（原來位置上的數(shù)不會(huì)被覆蓋，因?yàn)樘崆氨４媪耍?/p>

3、原來位置上的數(shù)據(jù)，依次后移

具體實(shí)現(xiàn)：

①單趟的實(shí)現(xiàn)（將x插入到 [0,end] 的有序區(qū)間）

即一般情況下的插入，我們隨機(jī)列舉了一些數(shù)字，待插入的數(shù)字分為兩種情況

（1）待插入的數(shù)字是在前面有序數(shù)字的中間數(shù)，直接比較將x賦值給end+1位置

（2）x是最小的一個(gè)數(shù)，end就會(huì)到達(dá)-1的位置，最后直接將x賦值給end+1位置

②整個(gè)數(shù)組排序的實(shí)現(xiàn)?

我們一開始并不知道數(shù)組是不是有序的，所以我們控制下標(biāo)，end從0開始，將end+1位置的值始終保存到x中，循環(huán)進(jìn)行單趟排序即可，最后結(jié)束時(shí)end=n-2，n-1位置的數(shù)字保存到x中

總體代碼：

void InsertSort(int* a, int n)
{
	assert(a);

	for (int i = 0; i< n - 1; ++i)
	{
		int end = i;
		int x=a[end+1];//將end后面的值保存到x里面了
		//將x插入到[0，end]的有序區(qū)間
		while (end >= 0)
		{
			if (a[end] >x)
			{
				a[end + 1] = a[end];  //往后挪動(dòng)一位
				--end;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = x;      //x放的位置都是end的后一個(gè)位置
	}
	
}

直接插入排序總結(jié)：

①元素越接近有序，直接插入排序的效率越高?

②時(shí)間復(fù)雜度:O(N^2)

最壞的情況下，每次插入一個(gè)數(shù)字，前面的數(shù)字都要挪動(dòng)一下，一共需要挪動(dòng)1+2+3+……+n=n(n+1)/2?

③空間復(fù)雜度：O(1)

沒有借助額外的空間，只用到常數(shù)個(gè)變量

二、希爾排序

基本思想：

1、先選定個(gè)小于n的數(shù)字作為gap，所有距離為gap的數(shù)分為一組進(jìn)行預(yù)排序（直接插入排序）

2、再選一個(gè)小于gap的數(shù)，重復(fù)①的操作

3、當(dāng)gap=1時(shí)，相當(dāng)于整個(gè)數(shù)組就是一組，再進(jìn)行一次插入排序即可整體有序

例如：?

具體實(shí)現(xiàn)：

①單組排序

和前面的直接插入相同，就是把原來的間隔為1，現(xiàn)在變?yōu)間ap了，每組分別進(jìn)行預(yù)排序

②多組進(jìn)行排序

③整個(gè)數(shù)組進(jìn)行排序（控制gap）

多次預(yù)排序（gap>1）+ 一次插入排序（gap==1）

（1）gap越大，預(yù)排越快，越不接近于有序

（2）gap越小，預(yù)排越慢，越接近有序

結(jié)果就是：?

總體代碼：

void ShellSort(int* a, int n)
{

	int gap = n;
	while (gap >1)
	{
		gap /= 2;

		for (int i = 0; i< n - gap; i++)
		{
			int end = i;
			int x = a[end + gap];
			while (end >= 0)
			{
				if (a[end] >x)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = x;
		}
	}
}

希爾排序總結(jié)：

①希爾排序是對(duì)直接插入排序的優(yōu)化

②時(shí)間復(fù)雜度：O(N^1.3)

③空間復(fù)雜度：O(1)?

三、選擇排序?

基本思想：

每次從數(shù)組中選出大的或者最小的，存放在數(shù)組的最右邊或者最左邊，直到全部有序?

具體實(shí)現(xiàn)：

我們這里進(jìn)行了優(yōu)化，一次排序中，直接同時(shí)選出大的數(shù)（a[maxi]）和最小的數(shù)（a[mini]）放在最右邊和最左邊，這樣排序效率是原來的2倍

①單趟排序

找到最小的數(shù)字（a[mini]）和大的數(shù)字（a[maxi]），將他們放在最左邊和最右邊

ps：其中的begin，end保存記錄左右的下標(biāo)，mini，maxi記錄保存最小值和大值得下標(biāo)

②整個(gè)數(shù)組排序

begin++和end--這樣下次就可以排剩下的n-2個(gè)數(shù)字，再次進(jìn)行單趟，如此可構(gòu)成循環(huán)，直到begin小于end

整體代碼：

void SelectSort(int* a, int n)
{
	int begin = 0,end = n - 1;

	while (begina[maxi])
			{
				maxi = i;
			}
		}
		Swap(&a[mini], &a[begin]);
		//當(dāng)begin==maxi時(shí)，大值會(huì)被換走，修正一下
		if (begin==maxi)
		{
			maxi=mini;
		}
		Swap(&a[maxi], &a[end]);
		begin++;
		end--;
	}
}

直接選擇排序總結(jié)：

①直接選擇排序很好理解，但實(shí)際效率不高，很少使用

②時(shí)間復(fù)雜度：O(N^2)

③空間復(fù)雜度：O(1)

四、堆排序

基本思想：

1、將待排序的序列構(gòu)造成一個(gè)大堆，根據(jù)大堆的性質(zhì)，當(dāng)前堆的根節(jié)點(diǎn)（堆頂）就是序列中大的元素；

2、將堆頂元素和最后一個(gè)元素交換，然后將剩下的節(jié)點(diǎn)重新構(gòu)造成一個(gè)大堆；

3、重復(fù)步驟2，如此反復(fù)，從第一次構(gòu)建大堆開始，每一次構(gòu)建，我們都能獲得一個(gè)序列的大值，然后把它放到大堆的尾部。最后，就得到一個(gè)有序的序列了。

小結(jié)論：

排升序，建大堆

排降序，建小堆

具體實(shí)現(xiàn)：、

①向下調(diào)整算法

我們將給定的數(shù)組序列，建成一個(gè)大堆，建堆從根節(jié)點(diǎn)開始就需要多次的向下調(diào)整算法

堆的向下調(diào)整算法（使用前提）：
（1）若想將其調(diào)整為小堆，那么根結(jié)點(diǎn)的左右子樹必須都為小堆。
（2）若想將其調(diào)整為大堆，那么根結(jié)點(diǎn)的左右子樹必須都為大堆。

向下調(diào)整算法的基本思想：

1、從根節(jié)點(diǎn)開始，選出左右孩子值較大的一個(gè)?

2、如果選出的孩子的值大于父親的值，那么就交換兩者的值

3、將大的孩子看做新的父親，繼續(xù)向下調(diào)整，直到調(diào)整到葉子節(jié)點(diǎn)為止

//向下調(diào)整算法
//以建大堆為例
void AdJustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;
	//默認(rèn)左孩子較大
	while (child< n)
	{
		if (child + 1< n && a[child+1] >a[child ])//如果這里右孩子存在，
                                       //且更大，那么默認(rèn)較大的孩子就改為右孩子
		{
			child++;
		}
		if(a[child]>a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

②建堆（將給定的任意數(shù)組建成大堆）

建堆思想：

從倒數(shù)第一個(gè)非葉子節(jié)點(diǎn)開始，從后往前，依次將其作為父親，依次向下調(diào)整，一直調(diào)整到根的位置

建堆圖示：

//最后一個(gè)葉子結(jié)點(diǎn)的父親為i，從后往前，依次向下調(diào)整，直到調(diào)到根的位置
for (int i = (n - 1 - 1) / 2; i >= 0; --i)
{
	AdJustDown(a, n, i);
}

③堆排序（利用堆刪的思想進(jìn)行）

堆排序的思想：

1、建好堆之后，將堆頂?shù)臄?shù)字與最后一個(gè)數(shù)字交換
2、將最后一個(gè)數(shù)字不看，剩下的n-1個(gè)數(shù)字再向下調(diào)整成堆再進(jìn)行第1步

3、直到最后只剩一個(gè)數(shù)停止，這樣就排成有序的了

for (int end = n - 1; end >0; --end)
{
	Swap(&a[end], &a[0]);
	AdJustDown(a, end, 0);
}

整體代碼如下：

void AdJustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;
	
	while (child< n)
	{
		if (child + 1< n && a[child+1] >a[child ])
                                       
		{
			child++;
		}
		if(a[child]>a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

//堆排序
void HeapSort(int*a,int n)
{
	
	for (int i = (n - 1 - 1) / 2;i>=0;--i)
	{
		AdJustDown(a,n,i);
	}
	
	for (int end = n - 1; end >0; --end)
	{
		Swap(&a[end],&a[0]);
		AdJustDown(a,end,0);
	}
}
五、冒泡排序

冒泡排序的基本思想：

一趟過程中，前后兩個(gè)數(shù)依次比較，將較大的數(shù)字往后推，下一次只需要比較剩下的n-1個(gè)數(shù)，如此往復(fù)?

//優(yōu)化版本的冒泡排序
void BubbleSort(int* a, int n)
{
	int end = n-1;
	while (end>0)
	{
		int exchange = 0;
		for (int i = 0; i< end; i++)
		{
			if (a[i] >a[i + 1])
			{
				Swap(&a[i], &a[i + 1]);
				exchange = 1;
			}
		}
		if (exchange == 0)//單趟過程中，若沒有交換過，證明已經(jīng)有序，沒有必要再排序
		{
			break;
		}
		end--;
	}
}

冒泡排序總結(jié)：

①非常容易理解的排序

②時(shí)間復(fù)雜度:O(N^2)

③空間復(fù)雜度:O(1)

六、快速排序

遞歸版本 1、hoare版本

hoare的單趟思想：

1、左邊作key，右邊先走找到比key小的值

2、左邊后走找到大于key的值

3、然后交換left和right的值

4、一直循環(huán)重復(fù)上述1 2 3步

5、兩者相遇時(shí)的位置，與最左邊選定的key值交換

這樣就讓key到達(dá)了正確的位置上

動(dòng)圖演示：??

//hoare版本
//單趟排序  讓key到正確的位置上   keyi表示key的下標(biāo)，并不是該位置的值
int partion1(int* a, int left, int right)
{
	int keyi = left;//左邊作keyi
	while (left< right)
	{   //右邊先走，找小于keyi的值
		while (left< right && a[right] >= a[keyi])
		{
			right--;
		}
		//左邊后走，找大于keyi的值
		while (left< right && a[left]<= a[keyi])
		{
			left++;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[left], &a[keyi]);
	return left;
}

void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;

	int keyi = partion1(a, left, right);
	//[left,keyi-1] keyi [keyi+1,right]
	QuickSort(a, left, keyi - 1);
	QuickSort(a, keyi + 1, right);
}
2、挖坑法

其實(shí)本質(zhì)上是hoare的變形

挖坑法單趟思想：

1、先將最左邊第一個(gè)數(shù)據(jù)存放在臨時(shí)變量key中，形成一個(gè)坑位

2、右邊先出發(fā)找到小于key的值，然后將該值丟到坑中去，此時(shí)形成一個(gè)新坑位

3、左邊后出發(fā)找到大于key的值，將該值丟入坑中去，此時(shí)又形成一個(gè)新的坑位

4、一直循環(huán)重復(fù)1 2 3步

5、直到兩邊相遇時(shí)，形成一個(gè)新的坑，最后將key值丟進(jìn)去

這樣key就到達(dá)了正確的位置上了

動(dòng)圖演示：?

//挖坑法
int partion2(int* a, int left, int right)
{
	int key = a[left];
	int pit = left;
	while (left< right)
	{
		while (left< right && a[right] >= key)
		{
			right--;
		}
		a[pit] = a[right];//填坑
		pit=right;


		while (left< right && a[left]<= key)
		{
			left++;
		}
		a[pit] = a[left];//填坑
		pit=left;
	}
	a[pit] = key;
	return pit;
}

void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;

	int keyi = partion2(a, left, right);
	//[left,keyi-1] keyi [keyi+1,right]
	QuickSort(a, left, keyi - 1);
	QuickSort(a, keyi + 1, right);
}
3、前后指針法（推薦這種寫法）

前后指針的思想：

1、初始時(shí)選定prev為序列的開始，cur指針指向prev的后一個(gè)位置，同樣選擇最左邊的第一個(gè)數(shù)字作為key

2、cur先走，找到小于key的值，找到就停下來

3、++prev

4、交換prev和cur為下標(biāo)的值

5、一直循環(huán)重復(fù)2 3 4步，停下來后，最后交換key和prev為下標(biāo)的值

這樣key同樣到達(dá)了正確的位置

動(dòng)圖演示：?

int partion3(int* a, int left, int right)
{
	int prev = left;
	int cur = left + 1;
	int keyi = left;
	while (cur<= right)
	{
		if (a[cur]< a[keyi] && ++prev != cur)//prev != cur  防止cur和prev相等時(shí)，相當(dāng)于自己和自己交換，可以省略
		{                                   //前置 ++ 的優(yōu)先級(jí)大于 != 不等于的優(yōu)先級(jí)
			Swap(&a[prev], &a[cur]);
		}
		++cur;
	}
	Swap(&a[keyi], &a[prev]);
	return prev;
}

void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;

	int keyi = partion3(a, left, right);
	//[left,keyi-1] keyi [keyi+1,right]
	QuickSort(a, left, keyi - 1);
	QuickSort(a, keyi + 1, right);
}

遞歸展開圖

快速排序的優(yōu)化 1、三數(shù)取中法

快速排序?qū)τ跀?shù)據(jù)是敏感的，如果這個(gè)序列是非常無序，雜亂無章的，那么快速排序的效率是非常高的，可是如果數(shù)列有序，時(shí)間復(fù)雜度就會(huì)從O(N*logN)變?yōu)镺(N^2)，相當(dāng)于冒泡排序了

若每趟排序所選的key都正好是該序列的中間值，即單趟排序結(jié)束后key位于序列正中間，那么快速排序的時(shí)間復(fù)雜度就是O(NlogN)

但是這是理想情況，當(dāng)我們面對(duì)一組極端情況下的序列，就是有序的數(shù)組，選擇左邊作為key值的話，那么就會(huì)退化為O(N^2)的復(fù)雜度，所以此時(shí)我們選擇首位置，尾位置，中間位置的數(shù)分別作為三數(shù)，選出中間位置的數(shù)，放到最左邊，這樣選key還是從左邊開始，這樣優(yōu)化后，全部都變成了理想情況

//快排的優(yōu)化
//三數(shù)取中法
int GetMidIndex(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	
	if (a[left]< a[right])
	{
		if (a[mid]< a[right])
		{
			return mid;
		}
		else if (a[mid] >a[right])
		{
			return right;
		}
		else
		{
			return left;
		}
	}

	else
	{
		
		if (a[mid] >a[left])
		{
			return left;
		}
		else if (a[mid]< a[right])
		{
			return right;
		}
		else
		{
			return mid;
		}
	}

}
int partion5(int* a, int left, int right)
{
	//三數(shù)取中,面對(duì)有序時(shí)是最壞的情況O(N^2)，現(xiàn)在每次選的key都是中間值，變成最好的情況了
	int midi = GetMidIndex(a, left, right);
	Swap(&a[midi], &a[left]);//這樣還是最左邊作為key

	int prev = left;
	int cur = left + 1;
	int keyi = left;
	while (cur<= right)
	{
		if (a[cur]< a[keyi] && ++prev != cur)//prev != cur  防止cur和prev相等時(shí)，相當(dāng)于自己和自己交換，可以省略
		{                                   //前置 ++ 的優(yōu)先級(jí)大于 != 不等于的優(yōu)先級(jí)
			//++prev;
			Swap(&a[prev], &a[cur]);
		}
		++cur;
	}
	Swap(&a[keyi], &a[prev]);
	return prev;
}
2、遞歸到小子區(qū)間?

隨著遞歸深度的增加，遞歸次數(shù)以每層2倍的速度增加，這對(duì)效率有著很大的影響，當(dāng)待排序序列的長(zhǎng)度分割到一定大小后，繼續(xù)分割的效率比插入排序要差，此時(shí)可以使用插排而不是快排

我們可以當(dāng)劃分區(qū)間長(zhǎng)度小于10的時(shí)候，用插入排序?qū)κＯ碌臄?shù)進(jìn)行排序

//小區(qū)間優(yōu)化法，可以采用直接插入排序
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;

	if (right - left + 1< 10)
	{
		InsertSort(a + left, right - left + 1);
	}
	else
	{
		int keyi = partion5(a, left, right);
		//[left,keyi-1] keyi [keyi+1,right]
		QuickSort(a, left, keyi - 1);
		QuickSort(a, keyi + 1, right);
	}
}
非遞歸版本

遞歸的算法主要是在劃分子區(qū)間，如果要非遞歸實(shí)現(xiàn)快排，只要使用一個(gè)棧來保存區(qū)間就可以了。一般將遞歸程序改成非遞歸首先想到的就是使用棧，因?yàn)檫f歸本身就是一個(gè)壓棧的過程。

非遞歸的基本思想：

1. 申請(qǐng)一個(gè)棧，存放排序數(shù)組的起始位置和終點(diǎn)位置。

2. 將整個(gè)數(shù)組的起始位置和終點(diǎn)位置入棧。

3. 由于棧的特性是：后進(jìn)先出，right后進(jìn)棧，所以right先出棧。

定義一個(gè)end接收棧頂元素，出棧操作、定義一個(gè)begin接收棧頂元素，出棧操作。

4. 對(duì)數(shù)組進(jìn)行一次單趟排序，返回key關(guān)鍵值的下標(biāo)。

5. 這時(shí)候需要排基準(zhǔn)值key左邊的序列。

如果只將基準(zhǔn)值key左邊序列的起始位置和終點(diǎn)位置存入棧中，等左邊排序完將找不到后邊的區(qū)間。所以先將右邊序列的起始位置和終點(diǎn)位置存入棧中，再將左邊的起始位置和終點(diǎn)位置后存入棧中。

6.判斷棧是否為空，若不為空 重復(fù)4、5步、若為空則排序完成。

void QuickSortNonR(int* a, int left, int right)
{
	Stack st;
	StackInit(&st);
	StackPush(&st,left);
	StackPush(&st, right);

	while (!StackEmpty(&st))
	{
		int end = StackTop(&st);
		StackPop(&st);

		int begin = StackTop(&st);
		StackPop(&st);

		int keyi = partion5(a,begin,end);
		//區(qū)間被成兩部分了 [begin,keyi-1] keyi [keyi+1,end]
		if (keyi + 1< end)
		{
			StackPush(&st,keyi+1);
			StackPush(&st,end);
		}
		if (keyi-1>begin)
		{
			StackPush(&st, begin);
			StackPush(&st, keyi -1);
		}
	}
	StackDestroy(&st);
}

快速排序的總結(jié)：

①快排的整體綜合性能和使用場(chǎng)景都是比較好的，所以才敢叫快速排序

②快排唯一死穴，就是排一些有序或者接近有序的序列，例如 2,3,2,3,2,3,2,3這樣的序列時(shí)，會(huì)變成O(N^2)的時(shí)間復(fù)雜度

③時(shí)間復(fù)雜度O(N*logN)

④空間復(fù)雜度O(logN)

七、歸并排序

歸并排序的基本思想（分治思想）：

1、（拆分）將一段數(shù)組分為左序列和右序列，讓他們兩個(gè)分別有序，再將左序列細(xì)分為左序列和右序列，如此重復(fù)該步驟，直到細(xì)分到區(qū)間不存在或者只有一個(gè)數(shù)字為止

2、（合并）將第一步得到的數(shù)字合并成有序區(qū)間

具體實(shí)現(xiàn)：

①拆分

②合并

遞歸實(shí)現(xiàn)：

從思想上來說和二叉樹很相似，所以我們可以用遞歸的方法來實(shí)現(xiàn)歸并排序

代碼如下：

void _MergeSort(int* a, int left, int right, int* tmp)
{
	if (left >= right)
	{
		return;
	}
	int mid = (left + right) / 2;
	_MergeSort(a, left, mid, tmp);
	_MergeSort(a, mid+1, right, tmp);
	
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int i = left;
	while (begin1<= end1 && begin2<= end2)
	{
		if (a[begin1]< a[begin2])
		{
			tmp[i++] = a[begin1++];
		}
		else
		{
			tmp[i++] = a[begin2++];
		}
	}
	while (begin1<= end1)
	{
		tmp[i++] = a[begin1++];
	}
	while (begin2<= end2)
	{
		tmp[i++] = a[begin2++];
	}
	for (int j = left; j<= right; j++)
	{
		a[j] = tmp[j];
	}
}
//歸并排序
void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int)*n);
	if (tmp == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	_MergeSort(a,0,n-1,tmp);

	free(tmp);
	tmp = NULL;
}
非遞歸實(shí)現(xiàn)：

我們知道，遞歸實(shí)現(xiàn)的缺點(diǎn)就是會(huì)一直調(diào)用棧，而棧內(nèi)存往往是很小的。所以，我們嘗試著用循環(huán)的辦法去實(shí)現(xiàn)

由于我們操縱的是數(shù)組的下標(biāo)，所以我們需要借助數(shù)組，來幫我們存儲(chǔ)上面遞歸得到的數(shù)組下標(biāo)，和遞歸的區(qū)別就是，遞歸要將區(qū)間一直細(xì)分，要將左區(qū)間一直遞歸劃分完了，再遞歸劃分右區(qū)間，而借助數(shù)組的非遞歸是一次性就將數(shù)據(jù)處理完畢，并且每次都將下標(biāo)拷貝回原數(shù)組

歸并排序的基本思路是將待排序序列a[0…n-1]看成是n個(gè)長(zhǎng)度為1的有序序列，將相鄰的有序表成對(duì)歸并，得到n/2個(gè)長(zhǎng)度為2的有序表；將這些有序序列再次歸并，得到n/4個(gè)長(zhǎng)度為4的有序序列；如此反復(fù)進(jìn)行下去，最后得到一個(gè)長(zhǎng)度為n的有序序列。

但是我們這是理想情況下（偶數(shù)個(gè)），還有特殊的邊界控制，當(dāng)數(shù)據(jù)個(gè)數(shù)不是偶數(shù)個(gè)時(shí)，我們所分的gap組，勢(shì)必會(huì)有越界的地方

第一種情況：

第二種情況：

代碼如下：

void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int)*n);
	if (tmp == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}

	int gap = 1;
	while (gap< n)
	{
		for (int i = 0; i< n; i += 2 * gap)
		{
			// [i,i+gap-1] [i+gap,i+2*gap-1]
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;

			// 核心思想：end1、begin2、end2都有可能越界
			// end1越界 或者 begin2 越界都不需要?dú)w并
			if (end1 >= n || begin2 >= n)
			{
				break;
			}
			
			// end2 越界，需要?dú)w并，修正end2
			if (end2 >= n)
			{
				end2 = n- 1;
			}

			int index = i;
			while (begin1<= end1 && begin2<= end2)
			{
				if (a[begin1]< a[begin2])
				{
					tmp[index++] = a[begin1++];
				}
				else
				{
					tmp[index++] = a[begin2++];
				}
			}

			while (begin1<= end1)
			{
				tmp[index++] = a[begin1++];
			}

			while (begin2<= end2)
			{
				tmp[index++] = a[begin2++];
			}

			// 把歸并小區(qū)間拷貝回原數(shù)組
			for (int j = i; j<= end2; ++j)
			{
				a[j] = tmp[j];
			}
		}

		gap *= 2;
	}

	free(tmp);
	tmp = NULL;
}

歸并排序的總結(jié)：

①缺點(diǎn)是需要O(N)的空間復(fù)雜度，歸并排序更多的是解決磁盤外排序的問題

②時(shí)間復(fù)雜度:O(N*logN)

③空間復(fù)雜度:O(N)

八、計(jì)數(shù)排序?

又叫非比較排序，又稱為鴿巢原理，是對(duì)哈希直接定址法的變形應(yīng)用

基本思想：

1、統(tǒng)計(jì)相同元素出現(xiàn)的個(gè)數(shù)

2、根據(jù)統(tǒng)計(jì)的結(jié)果，將數(shù)據(jù)拷貝回原數(shù)組

具體實(shí)現(xiàn)：

①統(tǒng)計(jì)相同元素出現(xiàn)的個(gè)數(shù)

對(duì)于給定的任意數(shù)組a，我們需要開辟一個(gè)計(jì)數(shù)數(shù)組count，a[i]是幾，就對(duì)count數(shù)組下標(biāo)是幾++

這里我們用到了絕對(duì)映射，即a[i]中的數(shù)組元素是幾，我們就在count數(shù)組下標(biāo)是幾的位置++，但是對(duì)于數(shù)據(jù)比較聚集，不是從較小的數(shù)字開始，例如1001,1002,1003,1004這樣的數(shù)據(jù)，我們就可以用到相對(duì)映射的方法，以免開辟數(shù)組空間的浪費(fèi)，count數(shù)組的空間大小我們可以用a數(shù)組中大值減去最小值+1來確定（即：range=max-min+1）,我們可以得到count數(shù)組下標(biāo) j =a[i]-min

②根據(jù)count數(shù)組的結(jié)果，將數(shù)據(jù)拷貝回a數(shù)組

count[j]中數(shù)據(jù)是幾，說明該數(shù)出現(xiàn)了幾次，是0就不用拷貝

代碼如下：

void CountSort(int* a, int n)
{
	int min = a[0], max = a[0];//如果不賦值，min和max就是默認(rèn)隨機(jī)值，最好給賦值一個(gè)a[0]

	for (int i=1;imax)
		{
			 max=a[i];
		}
	}
	int range = max - min + 1;//控制新開數(shù)組的大小，以免空間浪費(fèi)
	int* count = (int*)malloc(sizeof(int) * range);
	memset(count,0, sizeof(int) * range);//初始化為全0
	if (count==NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}

	//1、統(tǒng)計(jì)數(shù)據(jù)個(gè)數(shù)
	for (int i=0;i

計(jì)數(shù)排序總結(jié)：

①在數(shù)據(jù)范圍比較集中時(shí)，效率很高，但是使用場(chǎng)景很有限，可以排負(fù)數(shù)，但對(duì)于浮點(diǎn)數(shù)無能為力

②時(shí)間復(fù)雜度：O(MAX(N,range))

③空間復(fù)雜度：O(range)

八大排序的穩(wěn)定性總結(jié)：

穩(wěn)定的排序有：直接插入排序、冒泡排序、歸并排序

不穩(wěn)定的排序有：希爾排序、選擇排序、堆排序、快速排序、計(jì)數(shù)排序

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

分享題目：數(shù)據(jù)結(jié)構(gòu)—八大排序-創(chuàng)新互聯(lián)
分享URL：http://bm7419.com/article14/cdipde.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站導(dǎo)航、移動(dòng)網(wǎng)站建設(shè)、微信小程序、商城網(wǎng)站、域名注冊(cè)、網(wǎng)站制作

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(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í)需注明來源： 創(chuàng)新互聯(lián)