【數(shù)據(jù)結(jié)構(gòu)】-快速排序的四種方法實現(xiàn)以及優(yōu)化

這篇具有很好參考價值的文章主要介紹了【數(shù)據(jù)結(jié)構(gòu)】-快速排序的四種方法實現(xiàn)以及優(yōu)化。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

作者：小樹苗渴望變成參天大樹
作者宣言：認真寫好每一篇博客
作者gitee:gitee

如果你喜歡作者的文章，就給作者點點關(guān) 注吧！

前言

今天講一種不一樣的排序，聽名字就知道這個排序不拐彎抹角的，我們來看看它又多快速，并且快速排序的前三種方法都是遞歸思想，最后一種是非遞歸，我們就來重點介紹著集中方法來實現(xiàn)快排（以升序為例）

一、hoare法（左右指針法）

快速排序是Hoare于1962年提出的一種二叉樹結(jié)構(gòu)的交換排序方法，其基本思想為：任取待排序元素序列中的某元素作為基準值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準值，右子序列中所有元素均大于基準值，然后最左右子序列重復(fù)該過程，直到所有元素都排列在相應(yīng)位置上為止。

我們來看看動圖，再來畫圖詳細給大家介紹一下：

我們選擇一個keyi,保持不動，a[keyi]作為關(guān)鍵字，一趟排序下來這個關(guān)鍵字左邊的值都比它小，右邊的值都比它大，說明這個關(guān)鍵字來到了它最終來到的地方

通過左右指針將小的數(shù)跳到關(guān)鍵字的左邊，大的數(shù)跳到關(guān)鍵字的右邊，這個圖表示的一趟排序接下來看看畫圖分析
快速排序優(yōu)化,數(shù)據(jù)結(jié)構(gòu)初階,數(shù)據(jù)結(jié)構(gòu),算法,排序算法

通過這個圖，我們看到要注意的兩個細節(jié)，一個是找大找小的左右判斷，不能錯過了，而是判斷條件要不要加等于號，把這兩個細節(jié)掌握號，單趟就掌握好了，我們來看看單趟排序的代碼吧：

int partsort1(int* a, int left, int right)
{
	int keyi = left;
	while (left < right)
	{
		while (left<right && a[right]>=a[keyi])//找小
		{
			right--;
		}
		while (left < right && a[left] <= a[keyi])//找大
		{
			left++;
		}
		swap(&a[left], &a[right]);//交換
	}
	swap(&a[keyi], &a[left]);//結(jié)束后，把keyi位置的值和左邊的值交換
	keyi = left;//改變keyi的位置
}

看單趟排序結(jié)果：
快速排序優(yōu)化,數(shù)據(jù)結(jié)構(gòu)初階,數(shù)據(jù)結(jié)構(gòu),算法,排序算法
相信大家看到這里對于函數(shù)體里面的內(nèi)容已經(jīng)了解了，但是為什么我的函數(shù)設(shè)計要帶返回值呢？？

原因是我再前言就講過，快排的前三種都是遞歸的方法，思想都是一樣的，就是單趟排序的思想不一樣，因為一趟排序之后，關(guān)鍵字會跳到它最終的位置，下一趟排序，它就不需要參加排序，只需要把它左邊區(qū)間和右邊你區(qū)間進行排序，返回這個關(guān)鍵字的下標，目的是方便遞歸時找到左右區(qū)間的范圍

我們來看圖：
快速排序優(yōu)化,數(shù)據(jù)結(jié)構(gòu)初階,數(shù)據(jù)結(jié)構(gòu),算法,排序算法
我們來看完整的快排：

void quicksort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int keyi = partsort1(a, left, right);
	quicksort(a, left, keyi - 1);//對關(guān)鍵字左區(qū)間排序
	quicksort(a, keyi+1, right);//對關(guān)鍵字右區(qū)間排序
}

相比較而言，這里的遞歸還沒有二叉樹那些遞歸難理解，主要理解單趟排序的思想，就行了，接下來的兩種方法只需要修改partsort函數(shù)體里面的內(nèi)容就行了，我們開始介紹下面兩種思想

二、挖坑法

挖坑法是后面的牛人覺得hoare的方法有點難理解，又想出來的一種新的方法，思想是，把數(shù)組的最左邊和最右邊先當成一個坑，把這個坑的數(shù)據(jù)先保存起來，這樣有數(shù)過來就直接放到這個坑位里面，不怕原數(shù)據(jù)被覆蓋了，這個數(shù)就變成新的坑位，采取的還是左邊找大，右邊找小，找到就放到坑位里面，同時找到的位置變成新的坑位
我們先來看看動圖演示：

快速排序優(yōu)化,數(shù)據(jù)結(jié)構(gòu)初階,數(shù)據(jù)結(jié)構(gòu),算法,排序算法
我們再來看看圖解：

通過這個圖，我們要注意結(jié)束條件和找大找小條件都是和第一種一樣的那我們來看看這個單趟排序的代碼時怎樣的：

int partsort2(int* a, int left, int right)
{
	int key = a[left];//將坑位的關(guān)鍵字保存起來
	int pivot = left;//定義一個坑位下標
	while (left < right)
	{
		while (left < right && a[right] >= key)//找小
		{
			right--;
		}
		a[pivot] = a[right];//把找到小的數(shù)放到左坑
		pivot = right;
		while (left < right && a[left] <= key)//找大
		{
			left++;
		}
		a[pivot] = a[left];//把找到大的數(shù)放到右坑
		pivot = left;
	}
	a[pivot] = key;//把保存的關(guān)鍵字放到最后的坑位
	pivot = left;
	return pivot;
}

我們來看看單趟運行結(jié)果：
快速排序優(yōu)化,數(shù)據(jù)結(jié)構(gòu)初階,數(shù)據(jù)結(jié)構(gòu),算法,排序算法

和我們畫的圖解結(jié)果一樣，這兩種單趟的大思想都是把大的數(shù)快速跳到右邊，比較小的跳到左邊，關(guān)鍵字跳到它最終要出現(xiàn)的位置，最后都是通過遞歸再對左右區(qū)間進行排序

我們來看最終的快速排序：

void quicksort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int keyi = partsort2(a, left, right);//就改了一下這個函數(shù)體，其余和之前一樣
	quicksort(a, left, keyi - 1);
	quicksort(a, keyi+1, right);
}

相信大家看到這里對于挖坑法應(yīng)該理解，希望大家下來可以取嘗試理解一下，接下來我將講解另一種方法，前后指針法

三、前后指針法

這個方法相比較而言比前面兩種更好，而且不容易出錯，那我就來介紹一下這種方法，思想是：通過一個cur指針來找小，找到把prev指針+1把值進行交換，大的數(shù)跳到前面，小的數(shù)跳到后面，+1找到的是大的數(shù)，因為是cur跳過的數(shù)，所以是大的數(shù)，然后重復(fù)上面的步驟，知道cur結(jié)束，最后把keyi的值和prev的值進行交換
我們來看看動圖演示：
快速排序優(yōu)化,數(shù)據(jù)結(jié)構(gòu)初階,數(shù)據(jù)結(jié)構(gòu),算法,排序算法
接下來看看圖解：

這個方法理解了就很好理解，一定要多畫圖，接下來我們看一下單趟排序的代碼：

int partsort3(int* a, int left, int right)
{
	int prev = left;
	int cur = left + 1;
	int keyi = left;
	while (cur <= right)//結(jié)束條件
	{
		if (a[cur] < a[keyi])//找到小
		{
			++prev;//就++prev
			swap(&a[prev], &a[cur]);//兩者交換
		}
		cur++;//cur一直都需要++
	}
	swap(&a[prev], &a[keyi]);//循環(huán)結(jié)束
	keyi = prev;
	return keyi;
}

這個方法的好處就在于些的時候不容易出錯，就一趟遍歷即可，前兩種方法在條件判斷的時候容易出錯，我們來看看這個方法的完整快排代碼：

void quicksort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int keyi = partsort3(a, left, right);
	quicksort(a, left, keyi - 1);
	quicksort(a, keyi+1, right);
}

希望這三種方法你可以學(xué)會，接下來我要將這三種方法還可以進行優(yōu)化。

四、優(yōu)化版本

快速排序優(yōu)化,數(shù)據(jù)結(jié)構(gòu)初階,數(shù)據(jù)結(jié)構(gòu),算法,排序算法

我們遞歸的思想大致是這樣的，每增加一行的遞歸就會選出兩倍的關(guān)鍵字到最終的位置，但是在有序的情況，我們看看會怎么樣

快速排序優(yōu)化,數(shù)據(jù)結(jié)構(gòu)初階,數(shù)據(jù)結(jié)構(gòu),算法,排序算法

這樣看來快排在有序的時間效率最低，那我們就把它弄成不有序，有兩種方法，一個是隨機數(shù)法，一個是三數(shù)取中

4.1隨機數(shù)

一、我們來看看隨機數(shù)，隨便取一個a[keyi]然后和左邊交換，在進行排序，來看代碼：

void quicksort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int mid = left+rand() % (right - left + 1);
	if (mid != left)
	{
		swap(&a[left], &a[mid]);
	}
	int keyi = partsort3(a, left, right);
	quicksort(a, left, keyi - 1);
	quicksort(a, keyi+1, right);
}

為什么要加一個left，防止是遞歸右區(qū)間的時候。

4.2三數(shù)取中

我們再來看看三數(shù)取中，意思是在三個數(shù)中選出中間那個數(shù)，我們來看看代碼：

int GetMid(int* a, int left, int right)
{
	int mid = (right - left) / 2;
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])//left mid right
		{
			return mid;
		}
		else if (a[right] < a[left])//right left mid
		{
			return left;
		}
		else
		{
			return right;//left  right mid 
		}
	}
	else//a[left] >= a[mid]
	{
		if (a[right] > a[left])//mid left right
		{
			return left;
		}
		else if (a[mid] > a[right]) //right mid left
		{
			return mid;
		}
		else
		{
			return right;//mid right left
		}
	}
}

也是選出來和最左邊的數(shù)交換一下，但整體而言三叔取中用到比較多，因為隨機數(shù)選出來的可能剛好是最小的keyi，這樣和沒選沒啥區(qū)別，而三數(shù)取中保證選出來的keyi不是最小的

這里我就不在給大家測試性能了，如果大家感興趣可以取我的這篇測排序性能博客調(diào)用我的函數(shù)去測試，對于快排盡量數(shù)據(jù)搞多些，效果明顯，也可以和其他排序進行對比

對于優(yōu)化其實還有一種方法就是小區(qū)間優(yōu)化，對于數(shù)據(jù)量不是那么大的時候不需要使用遞歸來做，我們可以使用直接插入排序來做，具體為什么我就不做介紹了，大家了解一下就好了，反正越到最后遞歸的次數(shù)越多，浪費的時間就多，用直接插入排序節(jié)省一點時間，像希爾排序還要分組沒必要和選擇排序最好最壞情況一樣的，直接插入排序在有序的時候比較好，所以選擇了直接插入排序：

我們來看看怎么寫的：

void quicksort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int mid = GetMid(a, left, right);

	int keyi = partsort3(a, left, right);
	if (keyi - 1 - left > 10)
	{
		quicksort(a, left, keyi - 1);
		quicksort(a, keyi + 1, right);
	}
	else
	{
		insertsort(a + left, keyi - 1 - left + 1);//a+left是左區(qū)間起始位置，keyi - 1 - left + 1元素個數(shù)
	}
	if ((right - keyi - 1) > 10)
	{
		quicksort(a, left, keyi - 1);
		quicksort(a, keyi + 1, right);
	}
	else
	{
		insertsort(a + keyi + 1, right - keyi - 1 + 1);// a + keyi + 1是右區(qū)間起始位置，right-keyi-1+1元素個數(shù)
	}
}

這差不多是最好效率的快排排序了，大家可以把優(yōu)化的和不優(yōu)化的都測測看看性能是不是提高了，接下來我們來講非遞歸的快排了。

五、非遞歸版本

我們遞歸的本質(zhì)是，開辟先的函數(shù)空間，主要保存的左右區(qū)間的下標，我們可以通過棧來實現(xiàn)，分別把左右區(qū)間入棧，然后在進行單趟排序，調(diào)用之前的方法，然后再左右區(qū)間入棧
來看看圖解：
快速排序優(yōu)化,數(shù)據(jù)結(jié)構(gòu)初階,數(shù)據(jù)結(jié)構(gòu),算法,排序算法
大家跟著我的步驟走，我·采用的單趟排序是hoare法，我們來看代碼：

void QuickSortNonR(int* a, int left, int right)
{
	stack ST;
	STackInit(&ST);
	if (left >= right)
		return;
	StackPush(&ST, right);//先入右
	StackPush(&ST,left);//再入左
	while (!StackEmpty(&ST))
	{
		int left = StackTop(&ST);//出左
		StackPop(&ST);
		int right = StackTop(&ST);出右
		StackPop(&ST);
		int keyi = partsort1(a, left, right);//前三種方法都可以
		if (keyi - 1 - left >=1)
		{
			StackPush(&ST, keyi - 1);//左區(qū)間右邊入
			StackPush(&ST, left);//左區(qū)間左邊入
		}
		if (right - keyi - 1 >= 1)
		{
			StackPush(&ST, right);//右區(qū)間右邊入
			StackPush(&ST, keyi+1);//右區(qū)間左邊入
		}
	}
}

這個方法我們要先導(dǎo)入一個之前寫過的棧，再之前的博客有介紹過，然后就利用棧的特性來實現(xiàn)快排的非遞歸，大家一定要多畫畫圖。希望我這個圖解能給大家解答困惑

四、總結(jié)

今天加的內(nèi)容非常的多，大家一定要多消化消化，其實快速排序是選擇排序家族，冒泡也是選擇家族的一種，因為冒泡比較簡單，我就沒有和快排一起介紹了，希望大家可以知道，今天的，關(guān)于時間復(fù)雜度我可能再后期的博客會更新，把前面集中博客進行對比的介紹，到時候歡迎大家過來支持一下，今天的知識就先分享到這里了，我們下篇再見
快速排序優(yōu)化,數(shù)據(jù)結(jié)構(gòu)初階,數(shù)據(jù)結(jié)構(gòu),算法,排序算法文章來源地址http://www.zghlxwxcb.cn/news/detail-778201.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】-快速排序的四種方法實現(xiàn)以及優(yōu)化的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！