美少女怒肝20天用C語言寫出的排序集合-創(chuàng)新互聯(lián)

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

文章目錄

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

---

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

---

一、常見的排序算法

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

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

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

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

歸并排序：歸并排序

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

力扣鏈接：力扣

接下來我們就開始實現(xiàn)這些排序，首先是直接插入排序：

---

如上圖所示就是直接插入的單趟排序，而完整的排序只需要讓end從要排序的數(shù)組的第一個數(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án)條件中i

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

希爾排序：

希爾排序與插入排序的區(qū)別在于希爾排序會先進(jìn)行預(yù)排序，我們從上面的直接排序可以看出當(dāng)一個序列大部分是有序的時候用直接排序會非?？?，因為在不需要移動的時候我們直接break跳出循環(huán)了，那么這個時候預(yù)排序的優(yōu)勢就體現(xiàn)出來了，通過預(yù)排序?qū)⒁粋€序列中大部分?jǐn)?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;
		}
	}
}

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

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

選擇排序：

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

代碼如下：

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

堆排序：

堆排序我們在前面的文章中詳細(xì)的講解了，這里就大致說一下即可。堆排序升序要建大堆，因為大堆堆頂元素是大的，每次將堆頂元素和最后一個元素交換，這樣大的數(shù)就到了最后一個，然后從堆頂元素開始向下調(diào)整，調(diào)整后的堆頂元素就變成了堆中第二大的元素，然后讓總數(shù)--這樣下一次交換就是倒數(shù)第二個位置堆頂元素交換，就排好了大和第二大的數(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ì)的介紹堆，所以有不懂的可以去看看前面的文章，這里我們講解了一下思路就跳過了。那么堆排序的時間復(fù)雜度為多少呢？由于堆本質(zhì)上是完全二叉樹，二叉樹的高度為2^0~2^h-1，通過計算可得時間復(fù)雜度為O（N*logN）,并沒有額外開辟空間所以空間復(fù)雜度為O（1），那么穩(wěn)定嗎？答案是不穩(wěn)定，因為堆排序每次都要向下調(diào)整在調(diào)整的過程中就會打亂相同數(shù)的相對順序，所以不穩(wěn)定。

冒泡排序：

冒泡排序相信對每個人來說都不陌生，這里我們就直接上代碼了。

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)行一趟冒泡排序的時候我們都用flag去判斷是否已經(jīng)有序，如果整個數(shù)組都沒有交換過那么就說明這個數(shù)組是有序的那么直接退出循環(huán)即可。我們可以看到最外面那層循環(huán)為n-1，這是為什么？因為如果有10個數(shù)排序，我們進(jìn)行9趟冒泡排序就排好了9個數(shù)剩下一個數(shù)因為那9個數(shù)的移動自己就會排好，所以只需要n-1趟即可，在內(nèi)層循環(huán)中，我們每排好一個數(shù)就要減少一次循環(huán)的次數(shù)所以是n-1-i。下面我們來看一下冒泡排序的時間復(fù)雜度，按最壞的情況，要進(jìn)行n-1趟排序，每個數(shù)都要去比較一共n個數(shù)，所以冒泡排序的時間復(fù)雜度為O(n^2),空間復(fù)雜度為O（1）。那么冒泡排序穩(wěn)定嗎？答案是穩(wěn)定，因為冒泡排序只有前面的小于后面的才交換是不影響相同數(shù)的相對順序的。

快速排序：

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

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

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

上圖就是一趟快速排序的過程，我們發(fā)現(xiàn)一趟結(jié)束后key左邊的都比key小，key右邊的都比key大，那么下一趟我們只需要在重復(fù)剛剛的步驟去排key左邊的區(qū)間和key右邊的區(qū)間，很多人問為什么不排key了，打個比方 312 6 987?我們可以發(fā)現(xiàn)只需要排6左邊的和6右邊的這個序列就有序了。那么既然每次都要排序這個數(shù)組的左右區(qū)間那我們很自然的就想到了遞歸，在什么情況下左右就排好序了不需要再遞歸了呢？當(dāng)只有一個數(shù)的時候不需要再遞歸了因為一個數(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時兩個下標(biāo)相遇然后讓相遇點和key交換，然后相遇點變成新的K
	swap(&a[left], &a[key]);
	key = left;
	QuickSort(a, begin, key - 1);
	QuickSort(a, key + 1, end);
}

下面我們畫一下此代碼的遞歸展開圖：

看不清的可以對照上圖看下面的圖：

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

挖坑法：

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

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

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時兩個下標(biāo)相遇相遇點就是坑，把key放到坑里
	a[hole] = key;
	QuickSort2(a, begin, hole - 1);
	QuickSort2(a, hole + 1, end);
}

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

雙指針法：

雙指針法其實并不是指針只是兩個下標(biāo)，但是此方法是單趟排序中最為簡單的，其本質(zhì)就是將大于key的數(shù)往后推。我們定義兩個下標(biāo)一個是prev?一個是cur，prev每次從數(shù)組最左邊開始，cur為prev+1的位置，然后讓cur去找比Key小的數(shù)，當(dāng)找到后讓prev先++然后與cur位置的數(shù)據(jù)進(jìn)行交換，然后cur再開始找比key小的，當(dāng)cur超過數(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指向的不是同一個位置的時候就交換（因為同一個位置交換沒意義）
		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);
}

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

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

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

相信大家都知道，算法只有在數(shù)據(jù)量很大很大的時候才能明顯看出差距，當(dāng)我們要排序的數(shù)據(jù)量很小的時候我們不需要"殺雞用牛刀"直接用適應(yīng)性很強(qiáng)的插入排序去排這些小區(qū)間即可，為什么說插入排序的適應(yīng)性很強(qiáng)呢？因為插入排序在大多數(shù)數(shù)據(jù)是有序的情況下排的會非?？?，希爾排序就是根據(jù)這個來改進(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指向的不是同一個位置的時候就交換（因為同一個位置交換沒意義）
			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呢？因為begin到end是閉區(qū)間比如10個數(shù)那么閉區(qū)間為0-9，所以還要加上1才是真實的數(shù)據(jù)個數(shù)，當(dāng)數(shù)組里的數(shù)據(jù)小于15的時候我們直接用插入排序即可。

三數(shù)取中：

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

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

明白了快速排序的理想時間復(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指向的不是同一個位置的時候就交換（因為同一個位置交換沒意義）
			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);
	}
}

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

非遞歸版快速排序：

我們剛剛已經(jīng)講解過，快速排序的本質(zhì)在于每次找出一個key然后key的左區(qū)間都是比key小的，key的右區(qū)間都是比key大的，那么這個時候再去排左區(qū)間，既然是區(qū)間我們不妨可以想想其他的辦法來實現(xiàn)非遞歸過程，有聰明的小伙伴應(yīng)該也想到了吧，其實我們只需要把要排序的區(qū)間放入?；蛘哧犃兄校缓笕⒚總€區(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時兩個下標(biāo)相遇然后讓相遇點和key交換，然后相遇點變成新的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);
}

棧我們在之前的文章中詳細(xì)講解過，我們就直接講如何用棧實現(xiàn)非遞歸的快速排序。首先創(chuàng)建一個棧，然后初始化，先將數(shù)組的第一個位置的下標(biāo)和數(shù)組的最后一個位置的下標(biāo)入棧，然后開始進(jìn)入循環(huán)排序，由于棧是后進(jìn)先出所以先出棧的是右邊，我們用兩個變量去分別接受左右區(qū)間的下標(biāo)，當(dāng)左右區(qū)間都有值了就去排序，我們在單趟排序的函數(shù)中讓其函數(shù)返回了key的下標(biāo)，通過key我們就可以分出左區(qū)間和右區(qū)間了，因為后進(jìn)先出所以我們要是想先排序左區(qū)間的話就得先入右區(qū)間，入?yún)^(qū)間的時候要判斷，當(dāng)區(qū)間只有一個數(shù)的時候不需要排序所以不入棧，只有區(qū)間有兩個及兩個以上的數(shù)才入棧，只要棧不為空就會一直去排序直到完全有序，下面我們畫個圖演示一下。：

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

歸并排序：

歸并排序是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法的一個非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有 序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。?大概意思就是先一個數(shù)和一個數(shù)歸并，然后再兩個數(shù)兩個數(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;
}

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

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

非遞歸版歸并排序：

解決了區(qū)間下標(biāo)的問題我們再來看一看這個下標(biāo)造成越界的情況：

一共10個數(shù)下標(biāo)到9但是我們可以發(fā)現(xiàn)有三種越界情況，第一種是end1 begin2 end2都越界了，第二種是begin2 end2越界了，第三種是end2越界了。那么這三種情況的越界我們該怎樣控制呢？?

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一開始為1當(dāng)range小于n就進(jìn)入循環(huán)，然后通過一個下標(biāo)去訪問各個區(qū)間里的數(shù)，j每次跳過2*rangeN是為了在上兩個區(qū)間歸并完成后能跳到下一個要歸并的第一個區(qū)間。比如1 2 3 4?中1 2歸并后下標(biāo)要跳到3讓3和4歸并。當(dāng)end1越界的時候我們要調(diào)整end1的區(qū)間合法并且要將begin2和end2修改為不能進(jìn)入歸并循環(huán)的大小，因為當(dāng)end1越界就說明begin2?end2都越界了這個時候不需要再和第二個區(qū)間歸并了，當(dāng)begin2?end2越界的時候同理不需要歸并第二個區(qū)間所以直接修改這兩個變量的值讓其不進(jìn)入歸并循環(huán)。當(dāng)end2越界的時候就必須調(diào)整end2的區(qū)間，因為第一個區(qū)間是合法的，第二個區(qū)間部分是合法的只需要把越界的那部分去掉然后讓兩個區(qū)間歸并即可。等到for循環(huán)結(jié)束就意味著所有的數(shù)都已經(jīng)歸并完成了，這個時候直接將開辟的數(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越界的時候說明第二個區(qū)間肯定越界了這個時候就不歸并了直接break退出去，同理第二個區(qū)間越界了也是直接break即可。只有當(dāng)end2越界的時候需要考慮部分合法部分越界，只需要將越界的那部分刪除然后讓兩個區(qū)間進(jìn)行歸并即可。剛剛第一次我們是range每改變一次就把歸并后的數(shù)據(jù)拷貝到原數(shù)組，而這次我們是每一個小循環(huán)內(nèi)兩個區(qū)間歸并完就直接拷貝到原數(shù)組，唯一的區(qū)別在于部分拷貝需要加上開始拷貝的下標(biāo)已經(jīng)大小是這部分區(qū)間的大小，因為是閉區(qū)間所以要+1。舉個例子：當(dāng)range為1的時候，第一種是第一個數(shù)和第二個數(shù)歸并了，第三個數(shù)和第四個數(shù)歸并了依次到最后兩個數(shù)歸并完成然后整體在拷貝到原數(shù)組，range*2后變成兩兩歸并又重復(fù)剛才的步驟。第二種是第一個數(shù)和第二個數(shù)歸并了然后直接拷貝到原數(shù)組然后再進(jìn)行第三個數(shù)和第四個數(shù)歸并，然后又拷貝到原數(shù)組。相比起來的差別就是第二種拷貝的次數(shù)多于第一種。那么歸并排序的時間復(fù)雜度是多少呢？每次取中分為兩個區(qū)間是logn次，一共有n個數(shù)需要歸并所以時間復(fù)雜度為O（n*logn），那么空間復(fù)雜度是多少呢？我們額外開辟了n個int大小的空間所以空間復(fù)雜度為O（n）。歸并排序穩(wěn)定嗎？我們已經(jīng)說了歸并的內(nèi)核就是將兩個區(qū)間內(nèi)小的數(shù)依次插入新的數(shù)組，只要第一個區(qū)間的元素小于或者等于第二個區(qū)間的元素就把第一個區(qū)間的元素放入tmp，這樣并不會改變相同數(shù)的相對順序所以是穩(wěn)定的。

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

總結(jié)

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

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

網(wǎng)站題目：美少女怒肝20天用C語言寫出的排序集合-創(chuàng)新互聯(lián)
URL鏈接：http://www.jiaotiyi.com/article/hjpeo.html