成都創(chuàng)新互聯(lián)從2013年創(chuàng)立，先為濱州等服務(wù)建站，濱州等地企業(yè)，進(jìn)行企業(yè)商務(wù)咨詢服務(wù)。為濱州企業(yè)網(wǎng)站制作PC+手機(jī)+微官網(wǎng)三網(wǎng)同步一站式服務(wù)解決您的所有建站問(wèn)題。

文章目錄

• 排序的概念
• 一、常見(jiàn)的排序算法
• 二、代碼實(shí)現(xiàn)
• 總結(jié)

---

排序的概念 排序：所謂排序，就是使一串記錄，按照其中的某個(gè)或某些關(guān)鍵字的大小，遞增或遞減的排列起來(lái)的操作。 穩(wěn)定性：假定在待排序的記錄序列中，存在多個(gè)具有相同的關(guān)鍵字的記錄，若經(jīng)過(guò)排序，這些記錄的相對(duì)次 序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。 內(nèi)部排序：數(shù)據(jù)元素全部放在內(nèi)存中的排序。 外部排序：數(shù)據(jù)元素太多不能同時(shí)放在內(nèi)存中，根據(jù)排序過(guò)程的要求不能在內(nèi)外存之間移動(dòng)數(shù)據(jù)的排序。

---

一、常見(jiàn)的排序算法

我們根據(jù)排序的思想可分為4大類排序：

插入排序：插入排序又有直接插入排序和希爾排序

選擇排序：選擇排序和堆排序

交換排序：冒泡排序和快速排序

歸并排序：歸并排序

二、代碼實(shí)現(xiàn) 在這里給一個(gè)力扣鏈接用來(lái)幫助大家測(cè)試自己的排序的性能好壞

力扣鏈接：力扣

接下來(lái)我們就開(kāi)始實(shí)現(xiàn)這些排序，首先是直接插入排序：

---

如上圖所示就是直接插入的單趟排序，而完整的排序只需要讓end從要排序的數(shù)組的第一個(gè)數(shù)開(kāi)始依次實(shí)現(xiàn)上面的操作即可。

void InsertSort(int* a, int n)
{
	for (int i = 0; i< n - 1; i++)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (a[end] >tmp)
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

在這里可能會(huì)有人疑惑，為什么循環(huán)條件中i

下面我們來(lái)分析一下直接插入排序的時(shí)間復(fù)雜度和空間復(fù)雜度以及穩(wěn)定性。我們可以發(fā)現(xiàn)最壞的情況是一共N個(gè)數(shù)，end在交換的時(shí)候每個(gè)數(shù)都要挪動(dòng)，所以時(shí)間復(fù)雜度為O（N^2）,空間復(fù)雜度很明顯為O（1）因?yàn)槲覀兪窃谠瓟?shù)組移動(dòng)并沒(méi)有開(kāi)辟空間。那么直接插入排序是否穩(wěn)定呢？答案是穩(wěn)定，我們已經(jīng)說(shuō)過(guò)了，穩(wěn)定性是指相同的數(shù)在排序完后他們的相對(duì)順序不變也就是說(shuō)一個(gè)數(shù)組有兩個(gè)5，排序完后這兩個(gè)5的相對(duì)順序要和沒(méi)排序之前的順序一樣。而插入排序每次是將大的數(shù)往后插入并不會(huì)改變相同數(shù)的相對(duì)順序所以是穩(wěn)定的。

希爾排序：

希爾排序與插入排序的區(qū)別在于希爾排序會(huì)先進(jìn)行預(yù)排序，我們從上面的直接排序可以看出當(dāng)一個(gè)序列大部分是有序的時(shí)候用直接排序會(huì)非常快，因?yàn)樵诓恍枰苿?dòng)的時(shí)候我們直接break跳出循環(huán)了，那么這個(gè)時(shí)候預(yù)排序的優(yōu)勢(shì)就體現(xiàn)出來(lái)了，通過(guò)預(yù)排序?qū)⒁粋€(gè)序列中大部分?jǐn)?shù)變成有序的然后再直接排序就會(huì)省下更多的時(shí)間。

代碼如下：

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap >1)
	{
		gap = gap / 3 + 1;
		for (int i = 0; i< n - gap; i++)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] >tmp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

如圖所示是將整個(gè)數(shù)組4個(gè)為一組進(jìn)行預(yù)排序的圖，后面2個(gè)一組的與之相同就不畫了，從圖中我們可以發(fā)現(xiàn)為什么for循環(huán)里的條件是i

然后我們給出希爾排序時(shí)間復(fù)雜度為O(n^1.3)，希爾排序也是在原數(shù)組中進(jìn)行排序所以空間復(fù)雜度為O(1)，那么希爾排序穩(wěn)定嗎？答案是不穩(wěn)定，因?yàn)樵陬A(yù)排序階段就把相同數(shù)的相對(duì)順序打亂了所以不穩(wěn)定。

選擇排序：

選擇排序就是每次在數(shù)組中選一個(gè)大的數(shù)或者一個(gè)小的數(shù)然后放在數(shù)組第一個(gè)位置或者最后一個(gè)位置，然后縮小區(qū)間再繼續(xù)剛才的動(dòng)作。由于選擇排序相對(duì)簡(jiǎn)單并且容易理解所以我們直接上代碼，我們寫出的是每次遍歷的時(shí)候直接找出大的和最小的這樣效率上能有些提升。

代碼如下：

void swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void SelectSort(int* a, int n)
{
	int begin = 0;
	int end = n - 1;
	while (begin< end)
	{
		int min = begin;
		int max = begin;
		for (int i = begin; i<= end; i++)
		{
			if (a[i]< a[min])
			{
				min = i;
			}
			if (a[i] >a[max])
			{
				max = i;
			}
		}
		swap(&a[begin], &a[min]);
		if (max == begin)
		{
			max = min;
		}
		swap(&a[end], &a[max]);
		begin++;
		end--;
	}
}

我們需要注意的是在遍歷數(shù)組找大最小數(shù)的時(shí)候一定保存的是下標(biāo)而不是這個(gè)數(shù)，如果保存數(shù)字的話會(huì)有很多的麻煩，比如說(shuō)會(huì)缺失數(shù)據(jù)，因?yàn)槲覀兘粨Q是數(shù)組里的數(shù)交換，當(dāng)你直接保存的是數(shù)字本身而不是下標(biāo)的時(shí)候交換的就是max或min變量本身和數(shù)組中的數(shù)而不是數(shù)組中的兩個(gè)數(shù)交換。我們遍歷一遍數(shù)組后找到大的數(shù)的下標(biāo)和最小的數(shù)的下標(biāo)然后把最小的數(shù)和begin位置交換，在這里要注意一個(gè)細(xì)節(jié)，很有可能第一個(gè)數(shù)就是大的數(shù)這個(gè)時(shí)候max指向的是begin位置，而我們先將begin和min交換了這個(gè)時(shí)候大的數(shù)就到了min位置，所以我們需要用if判斷語(yǔ)句來(lái)將max的位置修正，然后再將大的數(shù)和end位置交換，然后縮小區(qū)間即可。當(dāng)begin==end的時(shí)候循環(huán)結(jié)束所有數(shù)都排序完成。這個(gè)時(shí)候我們來(lái)看一下選擇排序的時(shí)間復(fù)雜度，一共n個(gè)數(shù)每次進(jìn)入都需要遍歷一遍數(shù)組找到大或最小的數(shù)，雖然到最后區(qū)間會(huì)越來(lái)越小但是時(shí)間復(fù)雜度是最壞的情況所以時(shí)間復(fù)雜度為O（n^2）,由于是在數(shù)組上進(jìn)行排序所以空間復(fù)雜度為O（1）并沒(méi)有額外開(kāi)辟空間。那么選擇排序穩(wěn)定嗎？答案是不穩(wěn)定，原因如下圖：

堆排序：

堆排序我們?cè)谇懊娴奈恼轮性敿?xì)的講解了，這里就大致說(shuō)一下即可。堆排序升序要建大堆，因?yàn)榇蠖讯秧斣厥谴蟮模看螌⒍秧斣睾妥詈笠粋€(gè)元素交換，這樣大的數(shù)就到了最后一個(gè)，然后從堆頂元素開(kāi)始向下調(diào)整，調(diào)整后的堆頂元素就變成了堆中第二大的元素，然后讓總數(shù)--這樣下一次交換就是倒數(shù)第二個(gè)位置堆頂元素交換，就排好了大和第二大的數(shù)然后依次類推即可。

void swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
AdjustDown(HPDataType* a, int n, int parent)
{
	int child = 2 * parent + 1;
	while (child< n)
	{
		if ((child+1)< n && a[child + 1]< a[child])
		{
			child++;
		}
		if (a[parent] >a[child])
		{
			swap(&a[parent], &a[child]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}
//向下調(diào)整建堆
void HeapCreat(Heap* ps, HPDataType* a, int n)
{
	assert(ps);
	ps->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (ps->a == NULL)
	{
		perror("malloc:");
		exit(-1);
	}
	memcpy(ps->a, a, sizeof(HPDataType) * n);
	ps->capcity = ps->size = n;
	int end = n - 1;
	for (int i = (end - 1) / 2; i >= 0; i--)
	{
		AdjustDown(ps->a, n, i);
	}
}

void HeapSortUp(Heap* ps,HPDataType* a, int n)
{
	//升序建大堆  降序建小堆
	HeapCreat(ps, a, n);
	int end = n - 1;
	while (end >0)
	{
		swap(&ps->a[0], &ps->a[end]);
		AdjustDown(ps->a, end, 0);
		end--;
	}
}

由于在之前的文章中有很詳細(xì)的介紹堆，所以有不懂的可以去看看前面的文章，這里我們講解了一下思路就跳過(guò)了。那么堆排序的時(shí)間復(fù)雜度為多少呢？由于堆本質(zhì)上是完全二叉樹(shù)，二叉樹(shù)的高度為2^0~2^h-1，通過(guò)計(jì)算可得時(shí)間復(fù)雜度為O（N*logN）,并沒(méi)有額外開(kāi)辟空間所以空間復(fù)雜度為O（1），那么穩(wěn)定嗎？答案是不穩(wěn)定，因?yàn)槎雅判蛎看味家蛳抡{(diào)整在調(diào)整的過(guò)程中就會(huì)打亂相同數(shù)的相對(duì)順序，所以不穩(wěn)定。

冒泡排序：

冒泡排序相信對(duì)每個(gè)人來(lái)說(shuō)都不陌生，這里我們就直接上代碼了。

void swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void BubbleSort(int* a, int n)
{
	for (int i = 0; i< n - 1; i++)
	{
		int flag = 0;
		for (int j = 0; j< n - 1 - i; j++)
		{
			if (a[j] >a[j + 1])
			{
				swap(&a[j], &a[j + 1]);
				flag = 1;
			}
		}
		if (flag == 0)
		{
			break;
		}
	}
}

在這里我們稍加進(jìn)行了改進(jìn)，每進(jìn)行一趟冒泡排序的時(shí)候我們都用flag去判斷是否已經(jīng)有序，如果整個(gè)數(shù)組都沒(méi)有交換過(guò)那么就說(shuō)明這個(gè)數(shù)組是有序的那么直接退出循環(huán)即可。我們可以看到最外面那層循環(huán)為n-1，這是為什么？因?yàn)槿绻?0個(gè)數(shù)排序，我們進(jìn)行9趟冒泡排序就排好了9個(gè)數(shù)剩下一個(gè)數(shù)因?yàn)槟?個(gè)數(shù)的移動(dòng)自己就會(huì)排好，所以只需要n-1趟即可，在內(nèi)層循環(huán)中，我們每排好一個(gè)數(shù)就要減少一次循環(huán)的次數(shù)所以是n-1-i。下面我們來(lái)看一下冒泡排序的時(shí)間復(fù)雜度，按最壞的情況，要進(jìn)行n-1趟排序，每個(gè)數(shù)都要去比較一共n個(gè)數(shù)，所以冒泡排序的時(shí)間復(fù)雜度為O(n^2),空間復(fù)雜度為O（1）。那么冒泡排序穩(wěn)定嗎？答案是穩(wěn)定，因?yàn)槊芭菖判蛑挥星懊娴男∮诤竺娴牟沤粨Q是不影響相同數(shù)的相對(duì)順序的。

快速排序：

快速排序的核心內(nèi)容有三個(gè)版本，我們就都講解一遍，這三個(gè)版本分別是霍爾，挖坑，雙指針?lè)ā?/p>

注意：這里的三個(gè)版本只是單趟排序的思想不同，其他都一樣。

我們先來(lái)講解霍爾版本的。首先讓left指向數(shù)組的最左邊，讓right指向數(shù)組的最右邊，然后選左邊的作為Key，這個(gè)Key也可以是右邊，如果是左邊那么等會(huì)就讓右邊先走，如果是右邊那就要讓左邊先走，這樣可以保證最后Key的左邊為比K小的，Key的右邊為比K大的。

上圖就是一趟快速排序的過(guò)程，我們發(fā)現(xiàn)一趟結(jié)束后key左邊的都比key小，key右邊的都比key大，那么下一趟我們只需要在重復(fù)剛剛的步驟去排key左邊的區(qū)間和key右邊的區(qū)間，很多人問(wèn)為什么不排key了，打個(gè)比方 312 6 987?我們可以發(fā)現(xiàn)只需要排6左邊的和6右邊的這個(gè)序列就有序了。那么既然每次都要排序這個(gè)數(shù)組的左右區(qū)間那我們很自然的就想到了遞歸，在什么情況下左右就排好序了不需要再遞歸了呢？當(dāng)只有一個(gè)數(shù)的時(shí)候不需要再遞歸了因?yàn)橐粋€(gè)數(shù)就是有序的。下面我們就附上完整的代碼：

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int left = begin;
	int right = end;
	int key = left;
	while (left< right)
	{
		//左邊為K讓右邊先走，右邊找到小于K的停下
		while (left< right && a[right] >= a[key])
		{
			right--;
		}
		//右邊找到小后停下讓左邊走去找比K大的然后交換
		while (left< right && a[left]<= a[key])
		{
			left++;
		}
		swap(&a[left], &a[right]);
	}
	//當(dāng)left==right時(shí)兩個(gè)下標(biāo)相遇然后讓相遇點(diǎn)和key交換，然后相遇點(diǎn)變成新的K
	swap(&a[left], &a[key]);
	key = left;
	QuickSort(a, begin, key - 1);
	QuickSort(a, key + 1, end);
}

下面我們畫一下此代碼的遞歸展開(kāi)圖：

看不清的可以對(duì)照上圖看下面的圖：

通過(guò)遞歸展開(kāi)圖我們應(yīng)該可以清楚的理解快速排序是如何將一段亂序數(shù)字排成有序的，需要注意的點(diǎn)是每次右邊走的時(shí)候或者左邊走的時(shí)候循環(huán)條件內(nèi)必須加上left

挖坑法：

挖坑法的思想是讓一個(gè)變量去保存key值，然后我們假設(shè)左邊第一個(gè)位置為坑，當(dāng)然也可以右邊第一個(gè)位置為坑，但是一定要相反的方向先走。剛剛我們假設(shè)第一個(gè)位置為坑，然后我們讓右邊先走去找比key小的，找到后把這個(gè)位置的數(shù)據(jù)填入坑中，然后這個(gè)位置變成新的坑，再讓左邊走去找比K大的，找到后把這個(gè)位置的數(shù)放入新的坑中然后這個(gè)位置再變成坑，當(dāng)left==right的時(shí)候這個(gè)位置一定是坑，只需要將key放入這個(gè)位置即可。

如上圖所示就是挖坑法的思想，這個(gè)思想適合不太理解霍爾的那個(gè)方法的人。下面是挖坑法的代碼：

void QuickSort2(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int left = begin;
	int right = end;
	int key = a[left];
	int hole = left;
	while (left< right)
	{
		//左邊為坑讓右邊先走，右邊找到小于K的放到坑里然后讓自己變成新的坑
		while (left< right && a[right] >= key)
		{
			right--;
		}
		a[hole] = a[right];
		hole = right;
		//左邊走去找比K大的然后填入坑自己變成新的坑
		while (left< right && a[left]<= key)
		{
			left++;
		}
		a[hole] = a[left];
		hole = left;
	}
	//當(dāng)left==right時(shí)兩個(gè)下標(biāo)相遇相遇點(diǎn)就是坑，把key放到坑里
	a[hole] = key;
	QuickSort2(a, begin, hole - 1);
	QuickSort2(a, hole + 1, end);
}

我們可以看到與霍爾的版本差距并不是很大，主要在于單趟排序的不同，最后遞歸的時(shí)候都是去遞歸相遇點(diǎn)前面的區(qū)間和相遇點(diǎn)后面的區(qū)間。

雙指針?lè)ǎ?/p>

雙指針?lè)ㄆ鋵?shí)并不是指針只是兩個(gè)下標(biāo)，但是此方法是單趟排序中最為簡(jiǎn)單的，其本質(zhì)就是將大于key的數(shù)往后推。我們定義兩個(gè)下標(biāo)一個(gè)是prev?一個(gè)是cur，prev每次從數(shù)組最左邊開(kāi)始，cur為prev+1的位置，然后讓cur去找比Key小的數(shù)，當(dāng)找到后讓prev先++然后與cur位置的數(shù)據(jù)進(jìn)行交換，然后cur再開(kāi)始找比key小的，當(dāng)cur超過(guò)數(shù)組大小的時(shí)候循環(huán)結(jié)束。然后把prev位置和key進(jìn)行交換即可。以下為示意圖：

我們可以看到排完后key的左邊都是小于key的，key的右邊都是大于key的。

void QuickSort3(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int prev = begin;
	int cur = begin + 1;
	int key = begin;
	while (cur<= end)
	{
		//當(dāng)cur小于key并且cur和prev指向的不是同一個(gè)位置的時(shí)候就交換（因?yàn)橥粋€(gè)位置交換沒(méi)意義）
		if (a[cur]< a[key] && ++prev != cur)
		{
			swap(&a[cur], &a[prev]);
		}
		cur++;
	}
	//當(dāng)cur越界就把prev和key位置數(shù)據(jù)交換
	swap(&a[key], &a[prev]);
	QuickSort3(a, begin, prev - 1);
	QuickSort3(a, prev + 1, end);
}

我們從代碼就可以看出此方法的簡(jiǎn)潔，剛剛從示意圖中我們可以看到如果一開(kāi)始cur就是比key小的那么prev++后與cur在同一個(gè)位置是不需要交換的。if (a[cur]< a[key] && ++prev != cur)這串代碼的意思是一旦cur小于key為真就會(huì)繼續(xù)判斷++prev!=cur這個(gè)語(yǔ)句，因?yàn)槭乔爸?+只要cur小于key那么prev就會(huì)++往后走一步，即使++prev != cur這條語(yǔ)句為假不進(jìn)行交換prev也會(huì)++。

快排的三個(gè)單趟循環(huán)講完了下面我們?cè)賮?lái)講解一下如何改進(jìn)快速排序讓快速排序的效率更高。一共兩個(gè)方法，一個(gè)是小區(qū)間優(yōu)化的方法，另一個(gè)是三數(shù)取中的方法，這兩個(gè)方法可以同時(shí)放到快速排序中進(jìn)行優(yōu)化。

小區(qū)間優(yōu)化：

相信大家都知道，算法只有在數(shù)據(jù)量很大很大的時(shí)候才能明顯看出差距，當(dāng)我們要排序的數(shù)據(jù)量很小的時(shí)候我們不需要"殺雞用牛刀"直接用適應(yīng)性很強(qiáng)的插入排序去排這些小區(qū)間即可，為什么說(shuō)插入排序的適應(yīng)性很強(qiáng)呢？因?yàn)椴迦肱判蛟诖蠖鄶?shù)數(shù)據(jù)是有序的情況下排的會(huì)非常快，希爾排序就是根據(jù)這個(gè)來(lái)改進(jìn)的讓效率變得很高。那么我們直接上代碼：

void InsertSort(int* a, int n)
{
	for (int i = 0; i< n - 1; i++)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (a[end] >tmp)
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

void QuickSort3(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	if ((begin + end + 1)< 15)
	{
		InsertSort(a, begin + end + 1);
	}
	else
	{
		int prev = begin;
		int cur = begin + 1;
		int key = begin;
		while (cur<= end)
		{
			//當(dāng)cur小于key并且cur和prev指向的不是同一個(gè)位置的時(shí)候就交換（因?yàn)橥粋€(gè)位置交換沒(méi)意義）
			if (a[cur]< a[key] && ++prev != cur)
			{
				swap(&a[cur], &a[prev]);
			}
			cur++;
		}
		//當(dāng)cur越界就把prev和key位置數(shù)據(jù)交換
		swap(&a[key], &a[prev]);
		QuickSort3(a, begin, prev - 1);
		QuickSort3(a, prev + 1, end);
	}
}

為什么是begin+end+1呢？因?yàn)閎egin到end是閉區(qū)間比如10個(gè)數(shù)那么閉區(qū)間為0-9，所以還要加上1才是真實(shí)的數(shù)據(jù)個(gè)數(shù)，當(dāng)數(shù)組里的數(shù)據(jù)小于15的時(shí)候我們直接用插入排序即可。

三數(shù)取中：

三數(shù)取中的方法是優(yōu)化選key階段的，從數(shù)組的begin mid end三個(gè)數(shù)中選一個(gè)作為key，為什么這樣做會(huì)優(yōu)化呢？因?yàn)槲覀円揽繌臄?shù)組最左邊或者最右邊或者隨機(jī)選key都有可能選到大的或者最小的，我們的快速排序只有在每次選的key都是中間值的時(shí)候時(shí)間復(fù)雜度才為O(n*logn),如果每次選出的key都是最小的或者大的那么就意味著每次排序只排了左邊或者右邊一個(gè)數(shù)，每次只排一個(gè)的話時(shí)間復(fù)雜度其實(shí)為O(n^2)才對(duì)是，所以才有了三數(shù)取中這個(gè)方法，每次都能保證選的key是區(qū)間中的中值，這就符合快排的理想狀態(tài)了。為什么快排的理想狀態(tài)下的時(shí)間復(fù)雜度為n*logn看下圖：

我們不能發(fā)現(xiàn)理想狀態(tài)下不就是二叉樹(shù)嗎？二叉樹(shù)中我們當(dāng)時(shí)專門計(jì)算了向下調(diào)整的空間復(fù)雜度為,如下圖所示：

明白了快速排序的理想時(shí)間復(fù)雜度為O（NlogN）后我們就直接放代碼了：

int midi(int* a, int begin, int end)
{
	int mid = (begin + end) / 2;
	if (a[begin]< a[mid])
	{
		if (a[end] >a[mid])
		{
			return mid;
		}
		else if (a[begin] >a[end])
		{
			return begin;
		}
		else
		{
			return end;
		}
	}
	else
	{
		//begin>mid
		if (a[mid] >a[end])
		{
			return mid;
		}
		else if (a[begin] >a[end])
		{
			return end;
		}
		else
		{
			return begin;
		}
	}
}
void QuickSort3(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	if ((begin + end + 1)< 15)
	{
		InsertSort(a, begin + end + 1);
	}
	else
	{
		int mid = midi(a, begin, end);
		swap(&a[mid], &a[begin]);
		int prev = begin;
		int cur = begin + 1;
		int key = begin;
		while (cur<= end)
		{
			//當(dāng)cur小于key并且cur和prev指向的不是同一個(gè)位置的時(shí)候就交換（因?yàn)橥粋€(gè)位置交換沒(méi)意義）
			if (a[cur]< a[key] && ++prev != cur)
			{
				swap(&a[cur], &a[prev]);
			}
			cur++;
		}
		//當(dāng)cur越界就把prev和key位置數(shù)據(jù)交換
		swap(&a[key], &a[prev]);
		QuickSort3(a, begin, prev - 1);
		QuickSort3(a, prev + 1, end);
	}
}

我們可以看到三個(gè)數(shù)取中間值還是比較麻煩的，首先假設(shè)beginmid的時(shí)候中間值就是mid了，如果end

非遞歸版快速排序：

我們剛剛已經(jīng)講解過(guò)，快速排序的本質(zhì)在于每次找出一個(gè)key然后key的左區(qū)間都是比key小的，key的右區(qū)間都是比key大的，那么這個(gè)時(shí)候再去排左區(qū)間，既然是區(qū)間我們不妨可以想想其他的辦法來(lái)實(shí)現(xiàn)非遞歸過(guò)程，有聰明的小伙伴應(yīng)該也想到了吧，其實(shí)我們只需要把要排序的區(qū)間放入棧或者隊(duì)列中，然后去將每個(gè)區(qū)間排序完成即可。下面直接放代碼進(jìn)行講解。

#include#include#include 
typedef int StackDate;
typedef struct Stack
{
	StackDate* a;
	int top;
	int capcity;
}Stack;
void StackInit(Stack* ps)
{
	assert(ps);
	StackDate* tmp = (StackDate*)malloc(4 * sizeof(StackDate));
	if (tmp == NULL)
	{
		perror("malloc\n");
		exit(-1);
	}
	ps->a = tmp;
	ps->top = 0;
	ps->capcity = 4;
}


void StackDestroy(Stack* ps)
{
	assert(ps->a);
	free(ps->a);
	ps->a = NULL;
	ps->top = 0;
	ps->capcity = 0;
}


void StackPush(Stack* ps, StackDate x)
{
	assert(ps);
	if (ps->capcity == ps->top)
	{
		StackDate* tmp = (StackDate*)realloc(ps->a, ps->capcity * 2 * sizeof(StackDate));
		if (tmp == NULL)
		{
			perror("realloc\n");
			exit(-1);
		}
		ps->a = tmp;
		ps->capcity *= 2;
	}
	ps->a[ps->top] = x;
	ps->top++;
}

bool StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == 0;
}

void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->top >0);
	ps->top--;
}


StackDate StackTop(Stack* ps)
{
	assert(ps);
	assert(ps->top >0);
	return ps->a[ps->top - 1];
}
int _Qsort(int* a, int begin, int end)
{
	int left = begin;
	int right = end;
	int key = left;
	while (left< right)
	{
		//左邊為K讓右邊先走，右邊找到小于K的停下
		while (left< right && a[right] >= a[key])
		{
			right--;
		}
		//右邊找到小后停下讓左邊走去找比K大的然后交換
		while (left< right && a[left]<= a[key])
		{
			left++;
		}
		swap(&a[left], &a[right]);
	}
	//當(dāng)left==right時(shí)兩個(gè)下標(biāo)相遇然后讓相遇點(diǎn)和key交換，然后相遇點(diǎn)變成新的K
	swap(&a[left], &a[key]);
	key = left;
	return key;
}
void Qsort(int* a, int begin, int end)
{
	Stack sl;
	StackInit(&sl);
	StackPush(&sl, begin);
	StackPush(&sl, end);
	while (!StackEmpty(&sl))
	{
		int right = StackTop(&sl);
		StackPop(&sl);
		int left = StackTop(&sl);
		StackPop(&sl);
		int k = _Qsort(a, left, right);
		if (k + 1< right)
		{
			StackPush(&sl, k + 1);
			StackPush(&sl, right);
		}
		if (left< k - 1)
		{
			StackPush(&sl, left);
			StackPush(&sl, k-1);
		}
	}
    StackEmpty(&sl);
}

棧我們?cè)谥暗奈恼轮性敿?xì)講解過(guò)，我們就直接講如何用棧實(shí)現(xiàn)非遞歸的快速排序。首先創(chuàng)建一個(gè)棧，然后初始化，先將數(shù)組的第一個(gè)位置的下標(biāo)和數(shù)組的最后一個(gè)位置的下標(biāo)入棧，然后開(kāi)始進(jìn)入循環(huán)排序，由于棧是后進(jìn)先出所以先出棧的是右邊，我們用兩個(gè)變量去分別接受左右區(qū)間的下標(biāo)，當(dāng)左右區(qū)間都有值了就去排序，我們?cè)趩翁伺判虻暮瘮?shù)中讓其函數(shù)返回了key的下標(biāo)，通過(guò)key我們就可以分出左區(qū)間和右區(qū)間了，因?yàn)楹筮M(jìn)先出所以我們要是想先排序左區(qū)間的話就得先入右區(qū)間，入?yún)^(qū)間的時(shí)候要判斷，當(dāng)區(qū)間只有一個(gè)數(shù)的時(shí)候不需要排序所以不入棧，只有區(qū)間有兩個(gè)及兩個(gè)以上的數(shù)才入棧，只要棧不為空就會(huì)一直去排序直到完全有序，下面我們畫個(gè)圖演示一下。：

這樣我們就完成了非遞歸的快速排序，當(dāng)然用完棧后要記得把棧銷毀了避免內(nèi)存泄漏。快排的時(shí)間復(fù)雜度已經(jīng)說(shuō)過(guò)了是O（n*logn），那么空間復(fù)雜度是多少呢？我們按照遞歸版本來(lái)說(shuō)每次遞歸都需要用函數(shù)棧幀一共有l(wèi)ogn次，所以空間復(fù)雜度為O（logn），那么快速排序穩(wěn)定嗎？答案是不穩(wěn)定，從單趟排序我們就可以看出來(lái)key以及l(fā)eft right的多次互換一定會(huì)打亂相同的數(shù)的相對(duì)順序，所以快速排序是不穩(wěn)定的。

歸并排序：

歸并排序是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有 序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為二路歸并。?大概意思就是先一個(gè)數(shù)和一個(gè)數(shù)歸并，然后再兩個(gè)數(shù)兩個(gè)數(shù)進(jìn)行歸并，當(dāng)數(shù)組左半邊區(qū)間和右半邊區(qū)間都?xì)w并完成了就整體歸并。以下是代碼：

void _MergeSort(int* a, int begin, int end, int* tmp)
{
	if (begin >= end)
	{
		return;
	}
	int mid = (begin + end) / 2;
	//先歸并左半?yún)^(qū)間讓其有序，再歸并右半?yún)^(qū)間讓其有序，最后在整體歸并。
	_MergeSort(a, begin, mid, tmp);
	_MergeSort(a, mid+1, end, tmp);
	int begin1 = begin;
	int end1 = mid;
	int begin2 = mid + 1;
	int end2 = end;
	int i = begin;
	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++];
	}
	memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}
void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc:");
		exit(-1);
	}
	_MergeSort(a, 0, n - 1, tmp);
	free(tmp);
	tmp = NULL;
}

同樣先是采用遞歸的方法，我們需要開(kāi)辟一個(gè)數(shù)組，每次歸并完成的數(shù)都放在開(kāi)辟的數(shù)組中，然后每次一部分的歸并結(jié)束后就把開(kāi)辟的數(shù)組中的數(shù)復(fù)制到原來(lái)的數(shù)組中，開(kāi)辟的數(shù)組記得用完釋放掉。在遞歸的時(shí)候當(dāng)當(dāng)只有一個(gè)數(shù)的時(shí)候就不在遞歸直接去歸并即可，下面我們畫一個(gè)圖來(lái)講解一下是如何將一個(gè)數(shù)組歸并成有序的。

下面的圖是上面圖的右半部分，由于不能左右截圖所以只能分兩張。通過(guò)這張圖我們應(yīng)該能了解到歸并是如何進(jìn)行的，通過(guò)中值去歸并中值的左邊區(qū)間和右邊區(qū)間即使兩邊的個(gè)數(shù)不一樣也能正常歸并，每次歸并完兩個(gè)或者多個(gè)數(shù)的時(shí)候直接拷貝回原來(lái)的數(shù)組。我們可以看到歸并排序的內(nèi)核是將兩個(gè)小區(qū)間的數(shù)根據(jù)誰(shuí)大誰(shuí)小依次放入新的數(shù)組這樣就有序了，那么歸并排序該如何用非遞歸實(shí)現(xiàn)呢？既然是兩個(gè)區(qū)間的歸并那么我們不妨設(shè)置一個(gè)變量，當(dāng)這個(gè)變量為1的時(shí)候就是1個(gè)數(shù)和另一個(gè)數(shù)歸并，當(dāng)這個(gè)變量為2的時(shí)候就是2個(gè)數(shù)和另外兩個(gè)數(shù)歸并依次類推只要這個(gè)變量小于總數(shù)即可，有了這個(gè)思想那么我們就去實(shí)現(xiàn)一下。

非遞歸版歸并排序：

解決了區(qū)間下標(biāo)的問(wèn)題我們?cè)賮?lái)看一看這個(gè)下標(biāo)造成越界的情況：

一共10個(gè)數(shù)下標(biāo)到9但是我們可以發(fā)現(xiàn)有三種越界情況，第一種是end1 begin2 end2都越界了，第二種是begin2 end2越界了，第三種是end2越界了。那么這三種情況的越界我們?cè)撛鯓涌刂颇兀?

void MergeSortNonR(int* a, int n, int* tmp)
{
	int rangeN = 1;
	while (rangeN< n)
	{
		for (int j = 0; j< n; j += rangeN * 2)
		{
			int begin1 = j; int end1 = j+rangeN-1; 
			int begin2 = rangeN + j; int end2 = j+2*rangeN-1;
			if (end1 >= n)
			{
				end1 = n - 1;
				begin2 = n;
				end2 = n - 1;
			}
			else if (begin2 >= n)
			{
				begin2 = n;
				end2 = n - 1;
			}
			else if (end2 >= n)
			{
				end2 = n - 1;
			}
			int i = j;
			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++];
			}
		}
		memcpy(a, tmp, sizeof(int) * n);
		rangeN *= 2;
	}
}
void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc:");
		exit(-1);
	}
	//_MergeSort(a, 0, n - 1, tmp);
	MergeSortNonR(a, n, tmp);
	free(tmp);
	tmp = NULL;
}

以上是修正區(qū)間后的代碼。range一開(kāi)始為1當(dāng)range小于n就進(jìn)入循環(huán)，然后通過(guò)一個(gè)下標(biāo)去訪問(wèn)各個(gè)區(qū)間里的數(shù)，j每次跳過(guò)2*rangeN是為了在上兩個(gè)區(qū)間歸并完成后能跳到下一個(gè)要?dú)w并的第一個(gè)區(qū)間。比如1 2 3 4?中1 2歸并后下標(biāo)要跳到3讓3和4歸并。當(dāng)end1越界的時(shí)候我們要調(diào)整end1的區(qū)間合法并且要將begin2和end2修改為不能進(jìn)入歸并循環(huán)的大小，因?yàn)楫?dāng)end1越界就說(shuō)明begin2?end2都越界了這個(gè)時(shí)候不需要再和第二個(gè)區(qū)間歸并了，當(dāng)begin2?end2越界的時(shí)候同理不需要?dú)w并第二個(gè)區(qū)間所以直接修改這兩個(gè)變量的值讓其不進(jìn)入歸并循環(huán)。當(dāng)end2越界的時(shí)候就必須調(diào)整end2的區(qū)間，因?yàn)榈谝粋€(gè)區(qū)間是合法的，第二個(gè)區(qū)間部分是合法的只需要把越界的那部分去掉然后讓兩個(gè)區(qū)間歸并即可。等到for循環(huán)結(jié)束就意味著所有的數(shù)都已經(jīng)歸并完成了，這個(gè)時(shí)候直接將開(kāi)辟的數(shù)組拷貝到原先的數(shù)組就實(shí)現(xiàn)了非遞歸的歸并排序。當(dāng)然修改區(qū)間還有另外一種解決辦法，如下所示：

void MergeSortNonR2(int* a, int n, int* tmp)
{
	int rangeN = 1;
	while (rangeN< n)
	{
		for (int j = 0; j< n; j += rangeN * 2)
		{
			int begin1 = j; int end1 = j + rangeN - 1;
			int begin2 = rangeN + j; int end2 = j + 2 * rangeN - 1;
			if (end1 >= n)
			{
				break;
			}
			else if (begin2 >= n)
			{
				break;
			}
			else if (end2 >= n)
			{
				end2 = n - 1;
			}
			int i = j;
			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++];
			}
			memcpy(a+j, tmp+j, sizeof(int) * (end2-j+1));
		}
		rangeN *= 2;
	}
}

我們發(fā)現(xiàn)當(dāng)end1越界的時(shí)候說(shuō)明第二個(gè)區(qū)間肯定越界了這個(gè)時(shí)候就不歸并了直接break退出去，同理第二個(gè)區(qū)間越界了也是直接break即可。只有當(dāng)end2越界的時(shí)候需要考慮部分合法部分越界，只需要將越界的那部分刪除然后讓兩個(gè)區(qū)間進(jìn)行歸并即可。剛剛第一次我們是range每改變一次就把歸并后的數(shù)據(jù)拷貝到原數(shù)組，而這次我們是每一個(gè)小循環(huán)內(nèi)兩個(gè)區(qū)間歸并完就直接拷貝到原數(shù)組，唯一的區(qū)別在于部分拷貝需要加上開(kāi)始拷貝的下標(biāo)已經(jīng)大小是這部分區(qū)間的大小，因?yàn)槭情]區(qū)間所以要+1。舉個(gè)例子：當(dāng)range為1的時(shí)候，第一種是第一個(gè)數(shù)和第二個(gè)數(shù)歸并了，第三個(gè)數(shù)和第四個(gè)數(shù)歸并了依次到最后兩個(gè)數(shù)歸并完成然后整體在拷貝到原數(shù)組，range*2后變成兩兩歸并又重復(fù)剛才的步驟。第二種是第一個(gè)數(shù)和第二個(gè)數(shù)歸并了然后直接拷貝到原數(shù)組然后再進(jìn)行第三個(gè)數(shù)和第四個(gè)數(shù)歸并，然后又拷貝到原數(shù)組。相比起來(lái)的差別就是第二種拷貝的次數(shù)多于第一種。那么歸并排序的時(shí)間復(fù)雜度是多少呢？每次取中分為兩個(gè)區(qū)間是logn次，一共有n個(gè)數(shù)需要?dú)w并所以時(shí)間復(fù)雜度為O（n*logn），那么空間復(fù)雜度是多少呢？我們額外開(kāi)辟了n個(gè)int大小的空間所以空間復(fù)雜度為O（n）。歸并排序穩(wěn)定嗎？我們已經(jīng)說(shuō)了歸并的內(nèi)核就是將兩個(gè)區(qū)間內(nèi)小的數(shù)依次插入新的數(shù)組，只要第一個(gè)區(qū)間的元素小于或者等于第二個(gè)區(qū)間的元素就把第一個(gè)區(qū)間的元素放入tmp，這樣并不會(huì)改變相同數(shù)的相對(duì)順序所以是穩(wěn)定的。

以上就是排序的所有內(nèi)容了。

總結(jié)

排序中快速排序和歸并排序的難度不亞于二叉樹(shù)甚至比二叉樹(shù)更大。我們通過(guò)畫圖等方式可以看出只有直接插入排序?冒泡排序?歸并排序是穩(wěn)定的，并且時(shí)間復(fù)雜度最好的排序有希爾排序?堆排序?快速排序?歸并排序這四個(gè)。

你是否還在尋找穩(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)查看詳情吧

標(biāo)題名稱：美少女怒肝20天用C語(yǔ)言寫出的排序集合-創(chuàng)新互聯(lián)
URL標(biāo)題：http://chinadenli.net/article40/hjpeo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供軟件開(kāi)發(fā)、品牌網(wǎng)站建設(shè)、定制網(wǎng)站、面包屑導(dǎo)航、App設(shè)計(jì)、小程序開(kāi)發(fā)

廣告

聲明：本網(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í)需注明來(lái)源： 創(chuàng)新互聯(lián)