=========================================================================

相關代碼gitee自取：

C語言學習日記: 加油努力 (gitee.com)

?=========================================================================

接上期：

【數(shù)據(jù)結構初階】九、排序的講解和實現(xiàn)（直接插入 \ 希爾 \ 直接選擇 \ 堆 \ 冒泡 -- C語言）-CSDN博客

?=========================================================================

? ? ? ? ? ? ? ? ? ? ?

常見排序算法的實現(xiàn)（續(xù)上期）

（詳細解釋在圖片的注釋中，代碼分文件放下一標題處）

? ? ? ? ? ? ? ? ?

三、交換排序

基本思想：

所謂交換，就是根據(jù)序列中兩個記錄鍵值的比較結果來交換這兩個記錄在序列中的位置

? ? ? ? ? ? ?

交換排序的特點

將鍵值較大的記錄向序列的尾部移動，鍵值較小的記錄向序列的前部移動

? ? ? ? ? ? ? ? ? ? ??

? ? ? ? ? ? ? ? ? ? ??

交換排序 -- 快速排序
? ? ? ? ? ? ? ? ? ? ?

該算法基本思想：

• 快速排序是Hoare(霍爾)于1962年提出的一種二叉樹結構的交換排序方法
  ? ? ? ? ? ? ? ? ?
• 其基本思想為：
  任取待排序元素序列中的某元素作為基準值（key值），
  按照該基準值（key值）將待排序集合分割成兩個子序列（子區(qū)間），
  左子序列（左子區(qū)間）中所有元素均小于基準值(key值)，
  右子序列（右子區(qū)間）中所有元素均大于基準值(key值)，
  然后當前左右子序列（子區(qū)間）再重復上述過程，
  直到所有元素都排列在相應位置上為止
  ? ? ? ? ? ? ? ? ? ?
• 上述為快速排序遞歸實現(xiàn)的主框架，可以發(fā)現(xiàn)其過程與二叉樹前序遍歷規(guī)則非常像，
  在寫遞歸框架時可參考二叉樹前序遍歷規(guī)則，
  后續(xù)只需分析如何按照基準值（key值）來對區(qū)間中數(shù)據(jù)進行劃分的方式即可
  ? ? ? ? ? ? ? ? ? ? ? ? ?
• 將區(qū)間按照基準值（key值）劃分為左右兩半部分的常見方式有：
  hoare版本（原始版本）快速排序? 、 挖坑法快速排序? 、前后指針版本快速排序
  ? ? ? ? ? ? ? ? ?

快速排序的特性總結：

• 快速排序整體的綜合性能和使用場景都是比較好的，所以才敢叫快速排序
  ? ? ? ? ? ? ? ??

• 該算法時間復雜度：O(N*logN)
  ? ? ? ? ? ? ? ? ? ?

• 該算法空間復雜度：O(logN)
  ? ? ? ? ? ? ? ? ? ? ?

• 該算法穩(wěn)定性：不穩(wěn)定
  ? ? ? ? ? ? ? ?

---------------------------------------------------------------------------------------------

? ? ? ? ? ? ? ? ? ? ? ?

GetMidi內(nèi)部函數(shù) -- 快速排序“三數(shù)取中”優(yōu)化函數(shù)

• 使用基準值(key值)進行快速排序時，以key值將當前數(shù)組劃分出兩個區(qū)間時，
  可能key值是最小值，會排在數(shù)組最左邊，
  那么實際就只會劃分出一個右區(qū)間，此時右區(qū)間新的key值如果又是最小值的話，
  那么又只會劃分出一個右區(qū)間，這樣多趟快速排序的效率并不高，
  所以要進行“三數(shù)取中”操作，取出一個不大不小的中間值下標并返回
  ? ? ? ? ? ? ? ??

• 有了當前區(qū)間的起始元素下標（left）和尾部元素下標（right），
  就可以獲得一個當前區(qū)間的中間元素下標（mid），
  比較判斷這三個下標對應值的大小，取出中間值下標并返回

圖示：

? ? ? ? ? ? ? ? ? ? ? ? ??

? ? ? ? ? ? ? ? ? ? ? ? ??
---------------------------------------------------------------------------------------------

? ? ? ? ? ? ? ? ? ? ? ?

PartSort1內(nèi)部函數(shù) --? 一趟冒泡排序?qū)崿F(xiàn)函數(shù)（hoare版本）

• 使用三數(shù)取中函數(shù)獲得一個相對而言的中間值下標，將中間值和left下標值調(diào)換，
  我們默認key值下標為left下標，即當前區(qū)間（數(shù)組）起始（最左邊）位置下標，
  ? ? ? ? ? ? ? ? ? ?
• 使用while循環(huán)，
  讓較小值（較key小值）到數(shù)組左邊，較大值（較key大值）到數(shù)組右邊，
  先內(nèi)嵌第一個while循環(huán)，讓right從右往左找小于key值的元素下標，
  再內(nèi)嵌第二個while循環(huán)，讓left從左往右找大于key值的元素下標，
  分別找到比key小和比key大的值的下標后，將兩者的值進行調(diào)換
  ? ? ? ? ? ? ? ? ? ? ? ?
• while循環(huán)結束時，left == right，
  此時left(或right)下標就會是key值在數(shù)組中的真正下標，
  所以要將key值和此時left值(right值)進行交換
  ? ? ? ? ? ? ? ? ? ? ? ??
• 最后返回left（或right）下標，即此時key值的下標

圖示：

該函數(shù)執(zhí)行邏輯圖：

? ? ? ? ? ? ? ? ? ? ? ? ??

? ? ? ? ? ? ? ? ? ? ? ? ??
---------------------------------------------------------------------------------------------

? ? ? ? ? ? ? ? ? ? ? ?

PartSort2內(nèi)部函數(shù) --? 一趟冒泡排序?qū)崿F(xiàn)函數(shù)（挖坑法版本）

• 同樣使用三數(shù)取中函數(shù)獲得一個相對而言的中間值下標，將中間值和left下標值調(diào)換，
  我們默認key值下標為left下標，即當前區(qū)間（數(shù)組）起始（最左邊）位置下標，
  這次我們直接獲取key值，而不是其下標keyi
  ? ? ? ? ? ? ? ?
• 保存key值以后，在數(shù)組起始（最左邊）位置形成第一個"坑"
  （獲取或調(diào)整一個元素值后，將該元素值下標處定義為"坑"）
  ? ? ? ? ? ? ? ? ? ?
• 之后大體思路和hoare版本類似，
  只是在right找到"較小值"后，就直接將其放入上次定義的"坑"中，
  再在"較小值"下標處形成新的"坑"；
  在left找到"較大值"后，也直接將其放入上次定義的"坑"中，
  再在"較小值"下標處形成新的"坑"
  ? ? ? ? ? ? ? ? ? ? ? ?
• right 和 left 依次完成"挖坑填坑"后，
  最終會有一個空的"坑"，該"坑"即key值真正的下標位置，
  所以最后將key值放入"坑"中
  ? ? ? ? ? ? ? ? ? ? ? ??
• 最后返回最終的"坑位"下標，即此時key值的下標

圖示：

該函數(shù)執(zhí)行邏輯圖：

? ? ? ? ? ? ? ? ? ? ? ? ??

? ? ? ? ? ? ? ? ? ? ? ? ??
---------------------------------------------------------------------------------------------

? ? ? ? ? ? ? ? ? ? ? ?

PartSort3內(nèi)部函數(shù) --? 一趟冒泡排序?qū)崿F(xiàn)函數(shù)（前后指針版本）

• 使用三數(shù)取中函數(shù)獲得一個相對而言的中間值下標，將中間值和left下標值調(diào)換
  我們默認key值下標為left下標，即當前區(qū)間（數(shù)組）起始（最左邊）位置下標，
  ? ? ? ? ? ? ? ? ? ?
• 然后創(chuàng)建兩個指針--prev（前指針）和?cur（后指針），
  prev一開始指向起始位置，cur一開始指向prev后一位
  ? ? ? ? ? ? ? ? ? ? ? ?
• 使用while循環(huán)進行“推箱子”：
  當cur后指針還小于等于right下標時就繼續(xù)“推箱子”，
  cur指針從左往右找“較小值”，無論是否找到cur都++，
  如果cur指針找到了“較小值”，那么就++prev前指針，
  這時prev不等于cur的話，就交換兩指針值
  【把一段大于key的區(qū)間（“較大值”區(qū)間），類似推箱子般往右推，
  同時將較小值甩到左邊（"較小值"區(qū)間）去】
  ? ? ? ? ? ? ? ? ? ? ? ??
• right出界“推完箱子”后，while循環(huán)結束，
  此時prev下標就是key值下標，所以將key值放入該位置
  ? ? ? ? ? ? ? ? ? ??
• 最后返回key值位置，即此時prev指針的位置

圖示：

該函數(shù)執(zhí)行邏輯圖：

? ? ? ? ? ? ? ? ? ? ? ? ??

? ? ? ? ? ? ? ? ? ? ? ? ??
---------------------------------------------------------------------------------------------

? ? ? ? ? ? ? ? ? ? ? ?

QuickSort函數(shù) -- 快速排序（遞歸版本）

• 因為后面會對數(shù)組進行遞歸操作（遞歸快速排序），
  所以要先設置遞歸結束條件：
  因為后面遞歸時會用到指定的數(shù)組起始和尾部元素下標，
  在遞歸執(zhí)行到后面時，會出現(xiàn)數(shù)組范圍不合理的情況，
  類似左邊元素下標會大于右邊元素下標的區(qū)間或[0,0]區(qū)間……
  所以當出現(xiàn)這種情況時就可以返回遞歸結果了
  ? ? ? ? ? ? ? ? ? ? ? ??
• 小區(qū)間優(yōu)化 -- 小區(qū)間不再進行遞歸分割排序，降低遞歸次數(shù)：
  為了進一步提高快速排序效率，
  在遞歸分割過程中，區(qū)間比較小了以后，最好不再進行遞歸分割排序，
  因為滿二叉樹（快速排序遞歸過程類似滿二叉樹）倒數(shù)三層中會有80%的節(jié)點
  所以當區(qū)間比較小后，這些小區(qū)間會有80%的遞歸操作，
  對這么多小區(qū)間進行遞歸不劃算，
  所以當數(shù)組區(qū)間遞歸成小區(qū)間（類似只有10個元素）后，
  可以使用直接插入排序代替遞歸進行排序，
  對只有10個元素的數(shù)組進行直接插入排序效率高而且省去了80%的遞歸操作
  ? ? ? ? ? ? ? ? ? ? ? ??
• 對元素大于10的數(shù)組（大區(qū)間）進行快速排序（遞歸進行）：
  調(diào)用上面寫的三種單趟快速排序函數(shù)的其中一種，并接收返回的key值下標，
  此時當前區(qū)間就被分成了左右兩個區(qū)間，
  對左右兩個區(qū)間分別進行遞歸操作
  ? ? ? ? ? ? ? ? ? ?
• 對元素小于等于10的數(shù)組（小區(qū)間）進行直接插入排序

圖示：

該函數(shù)執(zhí)行邏輯圖：

該函數(shù)測試（hoare版本）：

該函數(shù)測試（挖坑法版本）：

該函數(shù)測試（前后指針版本）：

? ? ? ? ? ? ? ? ? ? ? ? ??

? ? ? ? ? ? ? ? ? ? ? ? ??
---------------------------------------------------------------------------------------------

? ? ? ? ? ? ? ? ? ? ? ?

QuickSortNonR函數(shù) -- 快速排序（非遞歸版本）

• 快速排序非遞歸版本思路--借助棧（“后進先出”）完成：
  先完成一趟快速排序操作，匹配完成key值的排序，
  然后將key值右邊的區(qū)間（大于key值區(qū)間）下標范圍先放入棧中，
  再將key值左邊的區(qū)間（小于key值區(qū)間）下標范圍放入棧中，
  因為棧的“后進先出”特性，會先使用左區(qū)間范圍，再使用右區(qū)間范圍，
  在棧中先取出左區(qū)間后，對該區(qū)間執(zhí)行一趟快速排序操作，
  然后匹配完成左區(qū)間key值的排序，該key值又分割出兩個當前左右區(qū)間，
  同樣在棧中先存放當前右區(qū)間，再存放當前左區(qū)間，
  然后再取出當前左區(qū)間來進行一趟快速排序，重復執(zhí)行此操作……（類似遞歸）
  到最后當區(qū)間范圍縮小到無意義范圍[0,0]或不合理范圍[2,1]時，
  就不將這類區(qū)間入棧了，繼續(xù)取當前棧中的有效區(qū)間重復上面的操作……
  （該過程不使用遞歸進行操作，但是實際執(zhí)行過程跟遞歸相同）
  ? ? ? ? ? ? ? ? ? ? ?
• 使用數(shù)據(jù)結構中的棧完成非遞歸快排的好處：
  使用遞歸進行快速排序的話，遞歸操作是在操作系統(tǒng)中的棧空間進行的，
  在Linux（32位）下的?？臻g只有8M，如果遞歸深度太深，
  ?？臻g就容易爆，導致棧溢出
  而使用數(shù)據(jù)結構中的棧完成非遞歸快排的話，棧是在操作系統(tǒng)中的堆空間進行的，
  在Linux（32位）下的堆空間有2G+，大概率不會存在堆溢出的情況

先導入之前寫的棧實現(xiàn)：

圖示：

該函數(shù)測試：

? ? ? ? ?

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

? ? ? ? ? ? ?

對應代碼（續(xù)上期）

Sort.h -- 排序頭文件

//快速排序函數(shù)（遞歸版本）：
//第一個參數(shù)：接收要排序的數(shù)組首元素地址（a）
//第二個參數(shù)：接收該數(shù)組起始位置下標（0）
//第二個參數(shù)：接收該數(shù)組尾部位置下標（數(shù)組元素個數(shù)-1）
void QuickSort(int* a, int begin, int end);


//快速排序函數(shù)（非遞歸版本）：
//第一個參數(shù)：接收要排序的數(shù)組首元素地址（a）
//第二個參數(shù)：接收該數(shù)組起始位置下標（0）
//第二個參數(shù)：接收該數(shù)組尾部位置下標（數(shù)組元素個數(shù)-1）
void QuickSortNonR(int* a, int begin, int end);

? ? ? ? ? ??文章來源地址http://www.zghlxwxcb.cn/news/detail-715256.html

? ? ? ? ? ??

---------------------------------------------------------------------------------------------

? ? ? ? ? ??

Sort.c -- 排序函數(shù)實現(xiàn)文件

//三數(shù)取中（內(nèi)部函數(shù)）：
//第一個參數(shù)：接收要排序的數(shù)組首元素地址（a）
//第二個參數(shù)：數(shù)組最左邊（起始）元素下標 -- key值
//第三個參數(shù)：數(shù)組最右邊（尾部）元素下標
//返回中間值的下標
int GetMidi(int* a, int left, int right)
{
	//通過left(左下標)和right(右下標)獲得mid(中下標)：
	int mid = (left + right) / 2;

	//	left	mid 	right
	if (a[left] < a[mid])
		//"左下標值" < "中下標值"
	{
		if (a[mid] < a[right])
			//又有："中下標值" < "右下標值"
		{
			return mid; //mid就是三數(shù)中的中間值下標
		}
		else if (a[left] > a[right])
			//又有："左下標值" > "右下標值"
		{
			return left; //left就是三數(shù)中的中間值下標
		}
		else
			//其它情況：
		{
			return right; //right就是三數(shù)中的中間值下標
		}
	}
	else
		//a[left] > a[mid]
		//"左下標值" > "中下標值"
	{
		if (a[mid] > a[right])
			//又有："中下標值" > "右下標值"
		{
			return mid; //mid就是三數(shù)中的中間值下標
		}
		else if (a[left] < a[right])
			//又有："左下標值" < "右下標值"
		{
			return left; //left就是三數(shù)中的中間值下標
		}
		else
			//其它情況：
		{
			return right; //right就是三數(shù)中的中間值下標
		}
	}
}



//一趟快速排序（內(nèi)部函數(shù)）-- 方法一hoare版本（細節(jié)較多）：
//第一個參數(shù)：接收要排序的數(shù)組首元素地址（a）
//第二個參數(shù)：數(shù)組最左邊（起始）元素下標 -- key值
//第三個參數(shù)：數(shù)組最右邊（尾部）元素下標
//返回排序后key值下標
int PartSort1(int* a, int left, int right)
{
	//使用三數(shù)取中函數(shù)獲得一個相對而言的中間值下標：
	int midi = GetMidi(a, left, right);
	//將中間值和數(shù)組起始元素進行交換：
	Swap(&a[left], &a[midi]);

	//定義快速排序的key值下標，
	//默認key值下標為數(shù)組最左邊（起始）下標 -- 0：
	//（通過三數(shù)取中后的left值在排序后會在數(shù)組相對中間位置）
	//（這有助于提高快速排序的效率 -- 因為后面遞歸的操作）
	int keyi = left;

	//使用while循環(huán)，
	//將數(shù)組右邊的較小值移至數(shù)組左邊，
	//將數(shù)組左邊的較大值移至數(shù)組右邊：
	while (left < right)
		/*
		* 只要left下標還小于right下標，
		* 說明中間可能還有元素需要被調(diào)整。
		*/
	{
		//先讓right從右往左找小于key值的元素下標：
		/*
		因為是升序，大值應該在右邊，
		所以從右往左找較小值，之后移至數(shù)組左邊
		*/
		while (left < right && a[right] >= a[keyi])
			//left < right，保證right不越界
			//而且right元素還大于等于key值：
		{
			//那就說明還不是較小值，
			//right往左移一位：
			--right;
			//直到調(diào)整到比key小的元素下標為止
		}

		//找到右邊的較小值后，再找左邊的較大值,
		//讓left從左往右找大于key值的元素下標：
		/*
		因為是升序，小值應該在左邊，
		所以從左往右找較大值，之后移至數(shù)組右邊
		*/
		while (left < right && a[left] <= a[keyi])
			//left < right，保證left不越界
			//而且left元素還小于等于key值：
		{
			//那就說明還不是較大值，
			//left往右移一位：
			++left;
			//直到調(diào)整到比key大的元素下標為止
		}

		//分別找到比key小和比key大的值后，
		//將兩者的值進行調(diào)換：
		//（讓較小值到數(shù)組左邊，較大值到數(shù)組右邊）
		Swap(&a[left], &a[right]);
	}

	//key值左邊的較小值和右邊的較大值排好后，
	//while循環(huán)結束時，left == right，
	//此時left(或right)下標就會是key值在數(shù)組中的真正下標，
	//所以要將key值和此時left值(right值)進行交換：
	/*
	* 外層while循環(huán)結束后，是right先往左邊走，left再往右邊走，
	* 較大值都在right后 且 left位置一定會在小于key值的元素上，
	* 所以此時可以將key值和left值(right值)進行交換，找到key真正位置
	*/
	Swap(&a[keyi], &a[left]);

	return left;
	//返回left（或right）下標，即此時key值的下標
	//此時key的左邊（較小值）和右邊（較大值）還是無序的
}
//單趟快速排序的時間復雜度：O(N)



//一趟快速排序（內(nèi)部函數(shù)）-- 方法二挖坑法：
//第一個參數(shù)：接收要排序的數(shù)組首元素地址（a）
//第二個參數(shù)：數(shù)組最左邊（起始）元素下標 -- key值
//第三個參數(shù)：數(shù)組最右邊（尾部）元素下標
//返回排序后key值下標
int PartSort2(int* a, int left, int right)
{
	//使用三數(shù)取中函數(shù)獲得一個相對而言的中間值下標：
	int midi = GetMidi(a, left, right);
	//將中間值和數(shù)組起始元素進行交換：
	Swap(&a[left], &a[midi]);

	//此時left下標元素就是中間值：
	int key = a[left]; //直接獲取key值(存放中間值)
	
	//保存key值以后，在數(shù)組起始（最左邊）位置形成第一個"坑"：
	int hole = left; //只留"坑"的下標（左邊的"坑"）

	//使用while循環(huán)進行快排過程：
	while (left < right)
		/*
		* 只要left下標還小于right下標，
		* 說明中間可能還有元素需要被調(diào)整。
		*/
	{
		//讓right從右往左走，找比key小的元素下標，
		while (left < right && a[right] >= key)
			//left < right，保證right不越界
			//而且right元素還大于等于key值：
		{
			//那就說明還不是較小值，
			//right往左移一位：
			--right;
			//直到調(diào)整到比key小的元素下標為止
		}

		//找到對應下標后填到左邊的"坑"，
		a[hole] = a[right];
		//在此時right下標處形成新的"坑"：
		hole = right; //右邊的"坑"（下標）


		//讓left從左往右走，找比key大的元素下標，
		while (left < right && a[left] <= key)
			//left < right，保證left不越界
			//而且left元素還小于等于key值：
		{
			//那就說明還不是較大值，
			//left往右移一位：
			++left;
			//直到調(diào)整到比key大的元素下標為止
		}

		//找到對應下標后填到右邊的"坑"，
		a[hole] = a[left];
		//在此時left下標處形成新的"坑"：
		hole = left; //再次形成左邊的"坑"（下標）
	}

	//left和right在“坑”下標處相遇后，while循環(huán)結束，
	//此時“坑”下標就是key值對應下標，
	//所以最后將key值放到“坑”下標處：
	a[hole] = key;

	//返回當前key值“坑”下標：
	return hole;
}



//一趟快速排序（內(nèi)部函數(shù)）-- 方法三前后指針版本：
//第一個參數(shù)：接收要排序的數(shù)組首元素地址（a）
//第二個參數(shù)：數(shù)組最左邊（起始）元素下標 -- key值
//第三個參數(shù)：數(shù)組最右邊（尾部）元素下標
//返回排序后key值下標
int PartSort3(int* a, int left, int right)
{
/*
* 思路（類似推箱子）：
* 創(chuàng)建兩個指針--prev（前指針）和cur（后指針）
* prev一開始指向起始位置，cur一開始指向prev后一位
* 
* cur：
* 1、++cur從左往右開始“找小(比key小)”，
	 找到后++prev,再交換prev和cur指向的值
*	 cur未找到較小值的話，cur單獨++，prev不動 
* 
* prev有兩種情況：
* 1、在cur還沒遇到比key大的值的時候，prev緊跟著cur
* 2、在cur遇到比key大的值的時候，cur單獨++，
*  	 prev會在比key大的一組值的前面(數(shù)組左邊)
* 
* 【本質(zhì)：把一段大于key的區(qū)間（較大值區(qū)間），類似推箱子般往右推，
*   同時將較小值甩到左邊（較小值區(qū)間）去】
*/
	//使用三數(shù)取中函數(shù)獲得一個相對而言的中間值下標：
	int midi = GetMidi(a, left, right);
	//將中間值和數(shù)組起始元素進行交換：
	Swap(&a[left], &a[midi]);

	//定義key值（“中間值”）下標：
	int keyi = left; //默認當前數(shù)組起始位置下標

	//先定義prev指針：
	int prev = left; //從當前數(shù)組起始位置開始

	//再定義cur指針：
	int cur = prev + 1; //指向prev的后一位

	//使用while循環(huán)循環(huán)進行"推箱子"：
	while (cur <= right)
		/*
		* cur==right時，還要再指向一次，
		* 讓cur指針出界，出界時prev指針的位置才是key值位置
		*/
	{
		//如果cur從左往右走后找到了“較小值”：
		if (a[cur] < a[keyi] && ++prev != cur)
			/*
			*			++prev != cur  
			* 每次“推箱子”時，先++prev，
			* 且不等于cur，如果等于cur的話會導致自己跟自己交換，
			* 這操作沒有意義，所以直接進行下次“推箱子”操作
			*/
		{
			//再交換當前兩指針值：
			Swap(&a[prev], &a[cur]);
		}

		//無論cur是否找到“較小值”，cur指針都需要進行++：
		++cur; //++往后（右）走
	}
	/*
	* 把一段大于key的區(qū)間（較大值區(qū)間），類似推箱子般往右推，
	* 同時將較小值甩到左邊（較小值區(qū)間）去
	*/

	//right出界“推完箱子”后，while循環(huán)結束，
	//此時prev下標就是key值下標，
	//所以將key值放入該位置：
	Swap(&a[prev], &a[keyi]);
	
	//最后返回key值位置 -- prev ：
	return prev;
}


//快速排序函數(shù)（遞歸版本）：
//第一個參數(shù)：接收要排序的數(shù)組首元素地址（a）
//第二個參數(shù)：接收該數(shù)組起始位置下標（0）
//第二個參數(shù)：接收該數(shù)組尾部位置下標（數(shù)組元素個數(shù)-1）
void QuickSort(int* a, int begin, int end)
{
	/*
	* 因為后面會對數(shù)組進行遞歸操作（遞歸快速排序），
	* 所以要先設置遞歸結束條件：
	* 因為后面遞歸時會用到指定的數(shù)組起始和尾部元素下標，
	* 在遞歸執(zhí)行到后面時，會出現(xiàn)數(shù)組范圍不合理的情況，
	* 類似左邊元素下標會大于右邊元素下標或[0,0]區(qū)間……
	* 所以當出現(xiàn)這種情況時就可以返回遞歸結果了：
	*/
	if (begin >= end)
		//數(shù)組起始位置下標 >= 數(shù)組尾部位置下標：
	{
		//是不合理的數(shù)組范圍:
		return; //直接返回上層遞歸
	}

	/*
	* 小區(qū)間優(yōu)化 -- 小區(qū)間不再進行遞歸分割排序，降低遞歸次數(shù)：
	* 為了進一步提高快速排序效率，
	* 在遞歸分割過程中，區(qū)間比較小了以后，最好不再進行遞歸分割排序，
	* 因為滿二叉樹（快速排序遞歸過程類似滿二叉樹）倒數(shù)三層中會有80%的節(jié)點
	* 所以當區(qū)間比較小后，這些小區(qū)間會有80%的遞歸操作，
	* 對這么多小區(qū)間進行遞歸不劃算，
	* 所以當數(shù)組區(qū)間遞歸成小區(qū)間（類似只有10個元素）后，
	* 可以使用直接插入排序代替遞歸進行排序，
	* 對只有10個元素的數(shù)組進行直接插入排序效率高而且省去了80%的遞歸操作
	*/

	//對元素大于10的數(shù)組（大區(qū)間）進行快速排序（遞歸進行）：
	//“滿二叉樹倒數(shù)三層前的節(jié)點”（“20%的節(jié)點”）
	if ((end - begin + 1) > 10)
		//區(qū)間尾下標 - 區(qū)間首下標 + 1 = 區(qū)間元素個數(shù)
	{
		//調(diào)用單趟快速排序函數(shù)并接收返回的key值下標:
		//int keyi = PartSort1(a, begin, end); //方法一 -- hoare版本
		//int keyi = PartSort2(a, begin, end); //方法二 -- 挖坑法
		int keyi = PartSort3(a, begin, end); //方法三 -- 前后指針版本

		/*
		* 調(diào)用函數(shù)進行一趟快速排序后，此時數(shù)組下標可表示為：
		* [begin, keyi-1] keyi [keyi+1, end]
		* 經(jīng)過一趟排序，此時key的左邊（較小值）和右邊（較大值）還是無序的
		* key的左邊（較小值）下標區(qū)間：[begin, keyi-1]
		* key的右邊（較大值）下標區(qū)間：[keyi+1, end]
		* 所以接下來要就這兩個區(qū)間進行排序：
		*/

		/*
		* 可以把下標區(qū)間： [begin, keyi-1] keyi [keyi+1, end]
		* 看成類似二叉樹的結構：
		*				keyi -- "根"
		*		[begin, keyi-1] -- “左子樹”
		*		[keyi+1, end] -- “右子樹”
		* 所以可以使用類似樹中類似遞歸的操作完成排序：
		*/

		//對“左子樹”進行遞歸快速排序：
		QuickSort(a, begin, keyi - 1); //[begin, keyi-1] -- “左子樹”

		//對“右子樹”進行遞歸快速排序：
		QuickSort(a, keyi + 1, end); //[keyi+1, end] -- “右子樹”
	}
	else
		//對元素小于等于10的數(shù)組（小區(qū)間）進行直接插入排序：
		//“滿二叉樹的倒數(shù)三層節(jié)點”（“80%的節(jié)點”）
	{
		//調(diào)用直接插入排序?qū)f歸后的“小區(qū)間”進行排序：
		InsertSort(a + begin, end - begin + 1);
		//被快速排序的遞歸操作分割后的“小區(qū)間”首元素下標：a + begin
		//被快速排序的遞歸操作分割后的“小區(qū)間”元素個數(shù)：end - begin + 1
	}
}
/*
* 快速排序時間復雜度（三數(shù)取中前）：
* 最好的情況(key值總排在靠中間的位置) -- O(N*logN)
* 最壞的情況(數(shù)組有序，key值總排在靠起始位置) -- O(N^2)
* 
* 快速排序時間復雜度（三數(shù)取中后）：
* 最好的情況(數(shù)組有序，key值總排在靠中間位置) -- O(N*logN)
* 最壞的情況 -- 在三數(shù)取中操作后幾乎不會有最壞的情況
*/



//快速排序函數(shù)（非遞歸版本）：
//第一個參數(shù)：接收要排序的數(shù)組首元素地址（a）
//第二個參數(shù)：接收該數(shù)組起始位置下標（0）
//第二個參數(shù)：接收該數(shù)組尾部位置下標（數(shù)組元素個數(shù)-1）
void QuickSortNonR(int* a, int begin, int end)
{
	/*
	*		將快速排序改成非遞歸版本思路--借助棧完成：
	* 先完成一趟快速排序操作，匹配完成key值的排序，
	* 然后將key值右邊的區(qū)間（大于key值區(qū)間）下標范圍先放入棧中，
	* 再將key值左邊的區(qū)間（小于key值區(qū)間）下標范圍放入棧中，
	* 因為棧的“后進先出”特性，會先使用左區(qū)間范圍，再使用右區(qū)間范圍，
	* 在棧中先取出左區(qū)間后，對該區(qū)間執(zhí)行一趟快速排序操作，
	* 然后匹配完成左區(qū)間key值的排序，該key值又分割出兩個當前左右區(qū)間，
	* 同樣在棧中先存放當前右區(qū)間，再存放當前左區(qū)間，
	* 然后再取出當前左區(qū)間來進行一趟快速排序，重復執(zhí)行此操作……（類似遞歸）
	* 到最后當區(qū)間范圍縮小到無意義范圍[0,0]或不合理范圍[2,1]時，
	* 就不將這類區(qū)間入棧了，繼續(xù)取當前棧中的有效區(qū)間重復上面的操作……
	* （該過程不使用遞歸進行操作，但是實際執(zhí)行過程跟遞歸相同）
	*/

	/*
	*		使用數(shù)據(jù)結構中的棧完成非遞歸快排的好處：
	* 使用遞歸進行快速排序的話，遞歸操作是在操作系統(tǒng)中的棧空間進行的，
	* 在Linux（32位）下的?？臻g只有8M，如果遞歸深度太深，
	* ?？臻g就容易爆，導致棧溢出
	* 
	* 而使用數(shù)據(jù)結構中的棧完成非遞歸快排的話，棧是在操作系統(tǒng)中的堆空間進行的，
	* 在Linux（32位）下的堆空間有2G+，大概率不會存在堆溢出的情況
	*/

	//先創(chuàng)建一個棧類型變量：
	ST st;
	
	//對其進行初始化：
	STInit(&st);

	/*
	* 我們要在棧中存放一個區(qū)間，即兩個整數(shù)，
	* 可以將棧中存放的數(shù)據(jù)改為區(qū)間類型：[begin, end]，
	* 而我們之前寫的棧的每個元素是存放一個整數(shù)的，
	* 所以要將一個區(qū)間分兩次放入棧中，
	* 先一次存放end(區(qū)間右范圍)，后一次存放begin(區(qū)間左范圍)，
	* 之后要連續(xù)取兩次棧中的元素，即左右范圍，構成一個區(qū)間
	*/

	//先存放數(shù)組（未進行排序前的整個數(shù)組）區(qū)間的右范圍：
	STPush(&st, end);

	//后存放數(shù)組區(qū)間的左范圍：
	STPush(&st, begin);

	/*
	* 之后使用while循環(huán)，只要棧中還有元素，
	* 就說明還有區(qū)間要進行快排，
	* while循環(huán)中，先獲取完整數(shù)組的區(qū)間(分兩次存放)
	* 對其進行一趟快速排序，分割出左右區(qū)間，
	* 再將左右區(qū)間放入棧中，然后重新循環(huán)，
	* （注意“后進先出”，先放右區(qū)間，之后會先取到左區(qū)間）
	* 再獲取左區(qū)間或右區(qū)間，進行一趟快速排序，
	* 就這樣循環(huán)下去，直到棧元素為空為止
	* （和遞歸過程類似）
	*/

	//如果當前棧中還有元素不為空：
	while (STEmpty(&st) != true)
	{
		//這里要連續(xù)取兩次棧頂元素，即一個區(qū)間的兩個范圍：

		//因為“后進先出”，所以會先獲取“后進的”左范圍：
		int left = STTop(&st); //獲得棧頂元素
		//獲取后進行出棧：
		STPop(&st);
			
		//再獲取“先進的”右范圍：
		int right = STTop(&st);
		//獲取后進行出棧：
		STPop(&st);

		//獲得一個區(qū)間范圍后，進行一趟快速排序：
		int keyi = PartSort1(a, left, right); 
		//存放排好序的key值下標

		/*
		*			  這時的區(qū)間：
		* [left,keyi-1]  keyi  [keyi+1, right]
		* 此時左區(qū)間：[left,keyi-1]
		* 此時右區(qū)間：[keyi+1, right]
		* 之后要在棧中放入快排后分割出的左右區(qū)間
		* 往棧中放入左右區(qū)間時，要判斷該區(qū)間左右范圍是否合理
		*/

		//先在棧中放入當前右區(qū)間（“先進會后出(取)”）：
		if (keyi+1 < right)
			//只有當前區(qū)間的左范圍小于右范圍才是有效且有意義的范圍
		{
			//和前面一樣先放入（右）區(qū)間的右范圍：
			STPush(&st, right);

			//再在棧中放入（右）區(qū)間的左范圍：
			STPush(&st, keyi+1);

			//之后要“后取”當前右區(qū)間的時候，
			//會先取其左范圍，再取其右范圍
		}

		//再在棧中放入當前左區(qū)間（“后進會先出(取)”）：
		if (left < keyi-1)
			//只有當前區(qū)間的左范圍小于右范圍才是有效且有意義的范圍
		{
			//和前面一樣先放入（左）區(qū)間的右范圍：
			STPush(&st, keyi-1);

			//再在棧中放入（左）區(qū)間的左范圍：
			STPush(&st, left);

			//之后要“先取”當前左區(qū)間的時候，
			//會先取其左范圍，再取其右范圍
		}
	}
	  
	//最后銷毀棧：
	STDestroy(&st);
}

? ? ? ? ? ??

? ? ? ? ? ??

---------------------------------------------------------------------------------------------

? ? ? ? ? ??

Test.c -- 排序測試文件

//快速排序（遞歸版本）方法測試：
void QSTest()
{
	//創(chuàng)建要進行插入排序的數(shù)組：
	int a[] = { 9,1,2,5,7,4,8,6,3,5 };

	//調(diào)用快速排序（遞歸版本）進行排序：
	QuickSort(a, 0, (sizeof(a)/sizeof(int))-1);
	//(sizeof(a)/sizeof(int))-1  --  元素個數(shù)-1==尾元素下標

	//使用自定義打印函數(shù)打印排序后數(shù)組：
	printf("使用快速排序(遞歸版本)后的數(shù)組:> ");
	PrintArray(a, sizeof(a) / sizeof(int));
}


//快速排序（非遞歸版本）方法測試：
void QSNRTest()
{
	//創(chuàng)建要進行插入排序的數(shù)組：
	int a[] = { 9,1,2,5,7,4,8,6,3,5 };

	//調(diào)用快速排序（非遞歸版本）進行排序：
	QuickSortNonR(a, 0, (sizeof(a) / sizeof(int)) - 1);
	//(sizeof(a)/sizeof(int))-1  --  元素個數(shù)-1==尾元素下標

	//使用自定義打印函數(shù)打印排序后數(shù)組：
	printf("使用快速排序（非遞歸版本）后的數(shù)組:> ");
	PrintArray(a, sizeof(a) / sizeof(int));
}

int main()
{
	//ISTest();
	//SSTest();
	//BSTest();
	//SlSTest();
	//QSTest();
	QSNRTest();

	return 0;
}

到了這里，關于【數(shù)據(jù)結構初階】十、快速排序(比較排序)講解和實現(xiàn)（三種遞歸快排版本 + 非遞歸快排版本 -- C語言實現(xiàn)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！