快速排序(快排)(C語言實(shí)現(xiàn))-創(chuàng)新互聯(lián)

🔆歡迎來到我的【數(shù)據(jù)結(jié)構(gòu)】專欄🔆
  • 👋我是Brant_zero，一名學(xué)習(xí)C/C++的在讀大學(xué)生。
  • 🌏?我的博客主頁????????Brant_zero的主頁
  • 🙏🙏歡迎大家的關(guān)注，你們的關(guān)注是我創(chuàng)作的大動(dòng)力🙏🙏
🍁前言

本篇博客學(xué)習(xí)內(nèi)容是快速排序，快速排序有多種不同的版本和優(yōu)化，我們這次的目的就是將這些版本都搞明白，廢話不多說，我們開始。

創(chuàng)新互聯(lián)公司成立10年來，這條路我們正越走越好，積累了技術(shù)與客戶資源，形成了良好的口碑。為客戶提供做網(wǎng)站、網(wǎng)站建設(shè)、網(wǎng)站策劃、網(wǎng)頁設(shè)計(jì)、域名申請(qǐng)、網(wǎng)絡(luò)營(yíng)銷、VI設(shè)計(jì)、網(wǎng)站改版、漏洞修補(bǔ)等服務(wù)。網(wǎng)站是否美觀、功能強(qiáng)大、用戶體驗(yàn)好、性價(jià)比高、打開快等等，這些對(duì)于網(wǎng)站建設(shè)都非常重要，創(chuàng)新互聯(lián)公司通過對(duì)建站技術(shù)性的掌握、對(duì)創(chuàng)意設(shè)計(jì)的研究為客戶提供一站式互聯(lián)網(wǎng)解決方案，攜手廣大客戶，共同發(fā)展進(jìn)步。

? 篇幅較長(zhǎng)，建議配合目錄來瀏覽。

🍂目錄🍂

一、快排介紹與思想

二、hoare版本

2.1 單趟過程

2.2 多趟過程

2.3 多趟的實(shí)現(xiàn)

三、 挖坑法

四、 前后指針法

五、 快排的優(yōu)化

5.1 三數(shù)取中選key

5.2 小區(qū)間改造

六、 快速排序改非遞歸版本

一、快排介紹與思想
快速排序是C.R.A.Hoare于1962年提出的一種劃分交換排序。它采用了一種分治的策略，通常稱其為分治法。
基本思想：
  • 1．先從數(shù)列中取出一個(gè)數(shù)作為基準(zhǔn)數(shù)。
  • 2．分區(qū)過程，將比這個(gè)數(shù)大的數(shù)全放到它的右邊，小于或等于它的數(shù)全放到它的左邊。
  • 3．再對(duì)左右區(qū)間重復(fù)第二步，直到各區(qū)間只有一個(gè)數(shù)。
二、hoare版本 2.1 單趟過程

hoare版本即是最快速排序最原始的版本，我們先來看看下面的GIF來看看其單趟的交換過程。

在這里插入圖片描述

💡單趟過程：

  1. 首先記錄下keyi位置，然后left和right分別從數(shù)組兩端開始往中間走。
  2. right先開始向中間行動(dòng)，如果right處的值小于keyi處的值，則停止等待left走。
  3. left開始行動(dòng)，當(dāng)left找到可以keyi處小的值時(shí)，left和right處的值進(jìn)行交換。
  4. 當(dāng)兩個(gè)位置相遇時(shí)，將相遇位置的值與keyi處的值進(jìn)行交換，并將相遇的位置置為新的keyi。

我們來看看下面的代碼，然后來分析其中容易出現(xiàn)的錯(cuò)誤。

//單趟：
	//首先keyi記錄begin處的數(shù)據(jù)
	int keyi = begin;
	int left = begin;
	int right = end;
	//兩個(gè)指針開始往中間行動(dòng)
	while (left< right)
	{
		//right先行動(dòng)，一定要找到 大于 keyi位置的值
		while(left< right && a[right] >= a[keyi])
		{
			right--;
		}
		//left行動(dòng)，一定要找到 小于 keyi位置的值
		while (left< right && a[left]<= a[keyi])
		{
			left++;
		}
		//到達(dá)指定位置，進(jìn)行交換
		swap(&a[left], &a[right]);
	}
	//走完上面的步驟后，兩個(gè)下標(biāo)會(huì)相聚在一個(gè)位置
	//然后對(duì)這兩個(gè)位置的值進(jìn)行交換
	swap(&a[right], &a[keyi]);
	keyi = right;
	//[begin,keyi-1],keyi,[keyi+1],end

💡易錯(cuò)點(diǎn)：

  1. 如果keyi記錄的最左邊的數(shù)據(jù)，則要讓right指針先行動(dòng)，因?yàn)檫@樣一定能要保證相遇的地方比keyi處的值要小。相遇位置就是R停下來的位置，好的情況是right處的值比keiy處的小，最壞的情況就是right走到了keyi的位置，那此時(shí)交換也壞沒有影響。
  2. 找值時(shí)，left或right處的值一定要比keyi處的小(大)，等于也不行，如果出現(xiàn)以下這種情況會(huì)死循環(huán)。
  3. 在left和right往中間找值時(shí)要判斷l(xiāng)eft
2.2 多趟過程

當(dāng)上面的單趟走完后，我們會(huì)發(fā)現(xiàn)，keyi左邊的全是小于a[keyi]的，右邊全是大于a[keyi]的。

那我們一直重復(fù)這個(gè)單趟的排序，就可以實(shí)現(xiàn)對(duì)整個(gè)數(shù)組的排序了，這典型是一個(gè)遞歸分治的思想。

💡基本思路：

  1. 將keyi分為兩邊，分別進(jìn)行遞歸，類似二叉樹的前序遍歷。
  2. 劃分為[begin,keyi-1],? keyi,? ?[keyi+1,end].
  3. 遞歸結(jié)束條件：當(dāng)begin == end? 或者是 數(shù)組錯(cuò)誤(begin>end)時(shí)，則為結(jié)束條件。
2.3 多趟的實(shí)現(xiàn)
void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	//一趟的實(shí)現(xiàn)
	int left = begin;
	int right = end;
	int keyi = left;
	while (left< right)
	{
		//右邊開始行動(dòng)   一定要加上等于，因?yàn)榭焖倥判蛘业氖且欢ū人〉闹?		while (left< right && a[keyi]<= a[right])
		{
			right--;
		}
		//左邊開始行動(dòng)
		while (left< right &&   a[left]<= a[keyi])
		{
			left++;
		}
		swap(&a[left], &a[right]);

	}
	swap(&(a[keyi]), &(a[right]));
	keyi = right;
	//[begin,keyi-1] keyi [keyi+1,end]
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi+1, end);
}

效果檢驗(yàn)：

三、 挖坑法

想必仍有人對(duì)hoare版本中，為什么左邊置為keyi右邊就要先走無法理解，這里有人就想出了一種新的快排版本，雖然算法思路一樣，但是更有利于理解。

其次，這兩種辦法單趟走出來的結(jié)果不同，這就導(dǎo)致一些題目上對(duì)于快排單趟的結(jié)果不同，所以我們來理解一下這種挖坑法的算法思想。

我們先來看看下面的動(dòng)畫：

💡算法思路：

  1. 將begin處的值放到key中，將其置為坑位(pit)，然后right開始行動(dòng)找值補(bǔ)坑。
  2. right找到比key小的值后將值放入坑位，然后將此處置為新的坑。
  3. left也行動(dòng)開始找值補(bǔ)坑，找到比key大的值將其放入坑位，置為新的坑。
  4. 當(dāng)left與right相遇的時(shí)候，將key放入到坑位中。
  5. 然后進(jìn)行[begin,piti-1],? piti,? ?[piti+1,end] 的遞歸分治。

因?yàn)橛辛薶oare版本的實(shí)現(xiàn)，所以這里就不多贅述了，上面的算法思路已經(jīng)將過程表述的很清楚了。

//快排  挖坑法
void QuickSort_dig(int* a, int begin, int end)
{
	if (begin >= end)
		return;
	//一趟的實(shí)現(xiàn)
	int key = a[begin];
	int piti = begin;
	int left = begin;
	int right = end;
		while (left< right)
		{
			while (left< right && a[right] >= key)
			{
				right--;
			}
			a[piti] = a[right];
			piti = right;
			while (left< right && a[left]<= key)
			{
				left++;
			}
			a[piti] = a[left];
			piti = left;
		}
		//補(bǔ)坑
		a[piti] = key;
	//[begin, piti - 1] piti [piti + 1, end]
	QuickSort_dig(a, begin, piti - 1);
	QuickSort_dig(a, piti + 1, end);
}

效果檢驗(yàn)：

四、 前后指針法

前后指針法相比于hoare和挖坑法，不論是算法思路還是實(shí)現(xiàn)過程都有很大提升，也是主流的一種寫法，這里我們一樣來看看單趟的過程吧。

💡算法思路：

  1. cur位于begin+1的位置，prev位于begin位置，keyi先存放begin處的值。
  2. cur不斷往前+1,直到cur >= end時(shí)停止循環(huán)。
  3. 如果cur處的值小于key處的值，并且prev+1 != cur，則與prev處的值進(jìn)行交換。
  4. 當(dāng)循環(huán)結(jié)束時(shí)，將prev處的值與keyi的值相交換，并將其置為新的keyi位置。

代碼實(shí)現(xiàn)：

void QuickSort_Pointer(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	//數(shù)據(jù)區(qū)間大與10，進(jìn)行快速排序
    int prev = begin;
	int cur = begin + 1;
	int keyi = begin;
	//三數(shù)取中后對(duì)keyi位置的值進(jìn)行交換
	int mid = GetMid(a, begin, end);
	swap(&a[mid], &a[keyi]);
	while (cur<= end)
	{
		//cur一直往前走，如果碰到小于并且prev++不等于cur則交換，
		//因?yàn)槿绻鹥rev+1 == cur 則會(huì)發(fā)生自己與自己交換的情況
		if (a[cur]< a[keyi] && ((++prev) != cur))
		{
			swap(&a[cur], &a[prev]);
		}
		cur++;
	}
	swap(&a[prev], &a[keyi]);
	keyi = prev;
	//開始進(jìn)行遞歸
	QuickSort_Pointer(a, begin, keyi - 1);
	QuickSort_Pointer(a, keyi + 1, end);
}

注意點(diǎn)：

  1. 在遍歷的過程中，cur是不斷向前的，只是cur處的值小于keyi處的值時(shí)，才需要進(jìn)行交換判斷一下。
  2. 在cur位置處的值小于keyi處的值時(shí)，要進(jìn)行判斷prev++是否等于cur，如果等于，那么會(huì)出現(xiàn)自己與自己交換的情況。如果相等，則不進(jìn)行交換。
五、 快排的優(yōu)化 5.1 三數(shù)取中選key

在實(shí)現(xiàn)了快速排序之后，我們發(fā)現(xiàn)，keyi的位置，是影響快速排序效率的重大因素。因此有人采用了三數(shù)取中的方法解決選keyi不合適的問題。

三數(shù)取中

即知道這組無序數(shù)列的首和尾后，我們只需要在首，中，尾這三個(gè)數(shù)據(jù)中，選擇一個(gè)排在中間的數(shù)據(jù)作為基準(zhǔn)值(keyi)，進(jìn)行快速排序，即可進(jìn)一步提高快速排序的效率。

//三數(shù)取中
int GetMid(int *a,int begin, int end)
{
	int mid = (begin + end) / 2;
	if (a[begin] >a[end])
	{
		if (a[end] >a[mid])
			return end;
		else if (a[mid] >a[begin])
			return begin;
		else
			return mid;
	}
	else
	{
		if (a[end]< a[mid])
			return end;
		else if (a[end]< a[begin])
			return begin;
		else
			return mid;
	}
}

這樣，中間值的下標(biāo)就被返回過來了，然后我們將這個(gè)位置換為新的keyi，就可以了。

5.2 小區(qū)間改造

由于快速排序是遞歸進(jìn)行的，當(dāng)遞歸到最后幾層時(shí)，此時(shí)數(shù)組中的值其實(shí)已經(jīng)接近有序，而且這段區(qū)間再遞歸會(huì)極大占用棧(函數(shù)棧幀開辟的地方)的空間,

接下來，我們對(duì)其進(jìn)行優(yōu)化，如果區(qū)間數(shù)據(jù)量小于10，我們就不進(jìn)行遞歸快速排序了，轉(zhuǎn)而使用插入排序。

我們來看看使用了小區(qū)間改造優(yōu)化和三數(shù)取中優(yōu)化后的快排。

void QuickSort_Pointer(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	//數(shù)據(jù)區(qū)間大與10，進(jìn)行快速排序
	if (end - begin >10)
	{
		int prev = begin;
		int cur = begin + 1;
		int keyi = begin;
		//三數(shù)取中后對(duì)keyi位置的值進(jìn)行交換
		int mid = GetMid(a, begin, end);
		swap(&a[mid], &a[keyi]);
		while (cur<= end)
		{
			if (a[cur]< a[keyi] && ((++prev) != cur))
			{
				swap(&a[cur], &a[prev]);
			}
			cur++;
		}
		swap(&a[prev], &a[keyi]);
		keyi = prev;
		//開始進(jìn)行遞歸
		QuickSort_Pointer(a, begin, keyi - 1);
		QuickSort_Pointer(a, keyi + 1, end);
	}
	else
	{
		//左閉右閉
		InsertSort(a, end - begin + 1);
		InsertSort(a + begin, end - begin + 1);
	}

}

💡注意點(diǎn)：

  1. 插入排序之后兩個(gè)參數(shù)，一個(gè)是數(shù)據(jù)集合的起點(diǎn)地址，第二個(gè)是數(shù)據(jù)量。
  2. 使用插入排序時(shí)，我們要傳入待排序數(shù)據(jù)集合的其實(shí)地址，即a+begin，如果傳入的是a，那排序的永遠(yuǎn)都是數(shù)組a的前n個(gè)區(qū)間。
  3. 插入排序傳入的是數(shù)據(jù)個(gè)數(shù)，所以我們要將end-begin加上1之后才傳入?？焖倥判蛑衑nd、begin都是閉區(qū)間(即數(shù)組下標(biāo))。
六、 快速排序改非遞歸版本

因?yàn)楹瘮?shù)棧幀是在棧(非數(shù)據(jù)結(jié)構(gòu)上的棧)上開辟的，所以容易出現(xiàn)棧溢出的情況，為了解決這個(gè)問題，我們除了上面兩種優(yōu)化，還可以將快速排序改為非遞歸版本，這樣空間的開辟就在堆上了，堆上的空間比棧要多上許多。

為了實(shí)現(xiàn)快速排序的非遞歸版本，我們要借助我們以前實(shí)現(xiàn)的棧，來模擬非遞歸。

💡實(shí)現(xiàn)思路：

  1. 入棧一定要保證先入左再入右。
  2. 取兩次棧頂?shù)脑?，然后進(jìn)行單趟排序。
  3. 劃分為[left , keyi - 1] keyi [ keyi +? 1 , right ] 進(jìn)行右、左入棧。
  4. 循環(huán)2、3步驟直到棧為空。
int PartSort(int * a, int begin, int end)
{
	int prev = begin;
	int cur = begin + 1;
	int keyi = begin;
	int mid = GetMid(a, begin, end);
	swap(&a[mid], &a[keyi]);
	while (cur<= end)
	{
		if (a[cur]< a[keyi] && ((++prev) != cur))
		{
			swap(&a[cur], &a[prev]);
		}
		cur++;
	}
	swap(&a[prev], &a[keyi]);
	return prev;
}
void QuickSortNonR(int* a, int begin, int end)
{
	ST st;
	StackInit(&st);
	//先入右 再入左
	StackPush(&st, end);
	StackPush(&st, begin);
	while (!StackEmpty(&st))
	{
		//那出棧 則是先出左再出右
		int left = StackTop(&st);
		StackPop(&st);
		int right = StackTop(&st);
		StackPop(&st);
		int keyi = PartSort(a, left, right);
		//[left, keyi - 1] keyi[keyi + 1, right];
		//棧里面的區(qū)間  都會(huì)進(jìn)行單趟排序分割

		if (keyi + 1< right)//說明至少還有兩個(gè)數(shù)據(jù)
		{
			//入右然后入左
			//才能保證取出時(shí) 順序不變
			StackPush(&st, right);
			StackPush(&st, keyi + 1);
		}
		//如果小于，說明至少還有兩個(gè)元素 待排序
		if (left< keyi - 1)
		{
			//入右然后入左
			StackPush(&st, keyi - 1);
			StackPush(&st, left);
		}
	}
	StackDestory(&st);
}

效果演示：

總結(jié)

本篇介紹了hoare法、挖坑法、前后指針法，以及兩種快排的優(yōu)化方式和非遞歸版本，還是非常有難度的，檢驗(yàn)大家實(shí)現(xiàn)的時(shí)候多看看動(dòng)圖，然后自己嘗試寫一下單趟的過程，再結(jié)合博客的內(nèi)容理解快排遞歸的思路。這篇的內(nèi)容相對(duì)硬核，光看是很難理解的，尤其是接觸hoare版本和非遞歸版本，希望大家動(dòng)手配合調(diào)試、畫圖來實(shí)現(xiàn)。

好的，本篇博客到此就結(jié)束了，下篇博客會(huì)更新歸并排序的相關(guān)內(nèi)容，希望大家持續(xù)關(guān)注，可以的話點(diǎn)個(gè)免費(fèi)的贊或者關(guān)注一下啊，你們反饋是我更新大的動(dòng)力。

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

分享文章：快速排序(快排)(C語言實(shí)現(xiàn))-創(chuàng)新互聯(lián)
網(wǎng)站路徑：http://muchs.cn/article2/dpdhic.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站制作、品牌網(wǎng)站設(shè)計(jì)、網(wǎng)站策劃、網(wǎng)站排名、面包屑導(dǎo)航、營(yíng)銷型網(wǎng)站建設(shè)

廣告

聲明：本網(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)

網(wǎng)站托管運(yùn)營(yíng)