??個人主頁： Quitecoder

??專欄：數(shù)據(jù)結(jié)構(gòu)與算法

上篇文章我們詳細(xì)講解了遞歸版本的快速排序，本篇我們來探究非遞歸實現(xiàn)快速排序和歸并排序

1.非遞歸實現(xiàn)快速排序

快速排序的非遞歸實現(xiàn)主要依賴于棧（stack）來模擬遞歸過程中的函數(shù)調(diào)用棧。遞歸版本的快速排序通過遞歸調(diào)用自身來處理子數(shù)組，而非遞歸版本則通過手動管理一個棧來跟蹤接下來需要排序的子數(shù)組的邊界

那么怎樣通過棧來實現(xiàn)排序的過程呢？

思路如下：

使用棧實現(xiàn)快速排序是對遞歸版本的模擬。在遞歸的快速排序中，函數(shù)調(diào)用棧隱式地保存了每次遞歸調(diào)用的狀態(tài)。但是在非遞歸的實現(xiàn)中，你需要顯式地使用一個輔助棧來保存子數(shù)組的邊界

以下是具體步驟和棧的操作過程：

1. 初始化輔助棧：
   創(chuàng)建一個空棧。棧用于保存每個待排序子數(shù)組的起始索引(begin)和結(jié)束索引(end)。

2. 開始排序：
   將整個數(shù)組的起始和結(jié)束索引作為一對入棧。這對應(yīng)于最初的排序問題。

3. 迭代處理：
   在棧非空時，重復(fù)下面的步驟：

   • 彈出一對索引（即棧頂元素）來指定當(dāng)前要處理的子數(shù)組。
   • 選擇子數(shù)組的一個元素作為樞軸（pivot）進行分區(qū)（可以是第一個元素，也可以通過其他方法選擇，下面我們還是用三數(shù)取中）。
   • 進行分區(qū)操作，這會將子數(shù)組劃分為比樞軸小的左側(cè)部分和比樞軸大的右側(cè)部分，同時確定樞軸元素的最終位置。

4. 處理子數(shù)組：
   分區(qū)操作完成后，如果樞軸元素左側(cè)的子數(shù)組（如果存在）有超過一個元素，則將其起始和結(jié)束索引作為一對入棧。同樣，如果右側(cè)的子數(shù)組（如果存在）也有超過一個元素，也將其索引入棧

5. 循環(huán)：
   繼續(xù)迭代該過程，直到棧為空，此時所有的子數(shù)組都已經(jīng)被正確排序。

所以主要思路就兩個：

1. 分區(qū)
2. 單趟排序

1.1 提取單趟排序

我們上篇文章講到遞歸排序的多種方法，這里我們可以取其中的一種提取出單趟排序：

int Getmidi(int* a, int begin, int end)
{
	int midi = (begin + end) / 2;
	if (a[begin] < a[midi])
	{
		if (a[midi] < a[end])
			return midi;
		else if (a[begin] > a[end])
			return begin;
		else
			return end;
	}
	else
	{
		if (a[midi] > a[end])
			return midi;
		else if (a[end] < a[begin])
			return end;
		else
			return begin;
	}
}
void QuickSortHole(int* arr, int begin, int end) {
	if (begin >= end) {
		return;
	}
	int midi = Getmidi(arr, begin, end);
	Swap(&arr[midi], &arr[begin]);

	int key = arr[begin]; 
	int left = begin;
	int right = end;

	while (left < right) {
		while (left < right && arr[right] >= key) {
			right--;
		}
		arr[left] = arr[right];

		while (left < right && arr[left] <= key) {
			left++;
		}
		arr[right] = arr[left];
	}

	arr[left] = key; 
	QuickSortHole(arr, begin, left - 1);
	QuickSortHole(arr, left + 1, end);
}

接下來完成單趟排序函數(shù)：

int singlePassQuickSort(int* arr, int begin, int end) 
{
	if (begin >= end) {
		return;
	}

	// 選擇樞軸元素
	int midi = Getmidi(arr, begin, end);
	Swap(&arr[midi], &arr[begin]);

	int key = arr[begin];  // 挖第一個坑
	int left = begin;  // 初始化左指針
	int right = end;   // 初始化右指針

	// 進行分區(qū)操作
	while (left < right) {
		// 從右向左找小于key的元素，放到左邊的坑中
		while (left < right && arr[right] >= key) {
			right--;
		}
		arr[left] = arr[right];

		// 從左向右找大于key的元素，放到右邊的坑中
		while (left < right && arr[left] <= key) {
			left++;
		}
		arr[right] = arr[left];
	}

	// 將樞軸元素放入最后的坑中
	arr[left] = key;

	
	// 函數(shù)可以返回樞軸元素的位置，若需要進一步的迭代過程
	return left;
}

1.2 用棧實現(xiàn)的具體思路

以下面這串?dāng)?shù)組為例：

首先建立一個棧，將整個數(shù)組的起始和結(jié)束索引作為一對入棧

彈出一對索引（即棧頂元素）來指定當(dāng)前要處理的子數(shù)組：這里即彈出0 9索引
找到樞軸6進行一次單趟排序：

針對這個數(shù)組：

6 3 4 9 5 8 7 2 1 10

我們使用“三數(shù)取中”法選擇樞軸。起始位置的元素為6，結(jié)束位置的元素為10，中間位置的元素為5。在這三個元素中，6為中間大小的值，因此選擇6作為樞軸。因為樞軸已經(jīng)在第一個位置，我們可以直接開始單趟排序。

現(xiàn)在，開始單趟排序：

1. 樞軸值為6。
2. 從右向左掃描，找到第一個小于6的數(shù)1。
3. 從左向右掃描，找到第一個大于6的數(shù)9。
4. 交換這兩個元素。
5. 繼續(xù)進行上述步驟，直到左右指針相遇。

經(jīng)過單趟排序后：

6 3 4 1 5 2 7 8 9 10

接下來需要將樞軸6放置到合適的位置。我們知道，最終左指針和右指針會停在第一個大于或等于樞軸值6的位置。在這個例子中，左右指針會停在7上。現(xiàn)在我們將6與左指針指向的位置的數(shù)交換：

5 3 4 1 2 6 7 8 9 10

現(xiàn)在樞軸值6處于正確的位置，其左側(cè)所有的元素都小于或等于6，右側(cè)所有的元素都大于或等于6。

分區(qū)操作完成后，如果樞軸元素左側(cè)的子數(shù)組（如果存在）有超過一個元素，則將其起始和結(jié)束索引作為一對入棧。同樣，如果右側(cè)的子數(shù)組（如果存在）也有超過一個元素，也將其索引入棧

我們接下來完成這個入棧過程：讓兩個子數(shù)組的索引入棧

接著取0 4索引進行單趟排序并不斷分區(qū)，分割的索引繼續(xù)壓棧，繼續(xù)迭代該過程，直到棧為空，此時所有的子數(shù)組都已經(jīng)被正確排序

1.3 代碼實現(xiàn)

這里我們調(diào)用之前的棧的代碼，基本聲明如下：

typedef int STDataType;


typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST; 

void StackInit(ST* ps);
// 入棧
void StackPush(ST* ps, STDataType x);
// 出棧
void StackPop(ST* ps);
// 獲取棧頂元素
STDataType StackTop(ST* ps);
// 獲取棧中有效元素個數(shù)
int StackSize(ST* ps);
// 檢測棧是否為空，如果為空返回非零結(jié)果，如果不為空返回0 
bool StackEmpty(ST* ps);
// 銷毀棧
void StackDestroy(ST* ps);

我們接下來完成排序代碼，首先建棧，初始化，并完成第一個壓棧過程：

ST s;
StackInit(&s);
StackPush(&s, end);
StackPush(&s, begin);

實現(xiàn)一次單趟排序：

int left = StackTop(&s);
StackPop(&s);

int right = StackTop(&s);
StackPop(&s);

int keyi = singlePassQuickSort(a, left, right);

注意這里我們先壓入end，那么我們先出的就是begin，用left首先獲取begin，再pop掉獲取end

接著判斷keyi左右是否還有子數(shù)組

if (left < keyi - 1)
{
	StackPush(&s, keyi - 1);
	StackPush(&s, left);
}
if (keyi + 1<right)
{
	StackPush(&s, right);
	StackPush(&s, keyi+1);
}

將此過程不斷循環(huán)即為整個過程，總代碼如下：

void Quicksortst(int* a, int begin, int end)
{
	ST s;
	StackInit(&s);
	StackPush(&s, end);
	StackPush(&s, begin);

	while (!StackEmpty(&s))
	{
		int left = StackTop(&s);
		StackPop(&s);

		int right = StackTop(&s);
		StackPop(&s);

		int keyi = singlePassQuickSort(a, left, right);
		if (left < keyi - 1)
		{
			StackPush(&s, keyi - 1);
			StackPush(&s, left);
		}
		if (keyi + 1<right)
		{
			StackPush(&s, right);
			StackPush(&s, keyi+1);
		}
	}
	StackDestroy(&s);
}

這里思想跟遞歸其實是差不多的，也是一次取一組進行排序，遞歸尋找每個區(qū)間

2.歸并排序

假如我們已經(jīng)有了兩個已經(jīng)排序好的數(shù)組，我們?nèi)绾巫屗麄儾橐粋€有序的數(shù)組呢？

我們的做法就是用兩個索引進行比較，然后插入一個新的數(shù)組完成排序，這就是歸并排序的基礎(chǔ)思路

那如果左右不是兩個排序好的數(shù)組呢？

下面是歸并排序的算法步驟：

1. 遞歸分解數(shù)組：如果數(shù)組的長度大于1，首先將數(shù)組分解成兩個部分。通常這是通過將數(shù)組從中間切分為大致相等的兩個子數(shù)組

2. 遞歸排序子數(shù)組：遞歸地對這兩個子數(shù)組進行歸并排序，直到每個子數(shù)組只包含一個元素或為空，這意味著它自然已經(jīng)排序好

3. 合并排序好的子數(shù)組：將兩個排序好的子數(shù)組合并成一個排序好的數(shù)組。這通常通過設(shè)置兩個指針分別指向兩個子數(shù)組的開始，比較它們指向的元素，并將較小的元素放入一個新的數(shù)組中，然后移動指針。重復(fù)此過程，直到所有元素都被合并進新數(shù)組

所以我們得需要遞歸來實現(xiàn)這一過程，首先聲明函數(shù)并建造新的數(shù)組：

void MergeSort(int* a, int n)
{
	int* tmp =(int *) malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}
	free(tmp);
}

由于我們不能每次開辟一遍數(shù)組，我們這里就需要一個子函數(shù)來完成遞歸過程：

void _MergrSort(int* a, int begin, int end, int* tmp)；

首先，不斷遞歸將數(shù)組分解：

int mid = (begin + end) / 2;

if (begin >= end)
{
	return;
}
_MergrSort(a, begin, mid, tmp);
_MergrSort(a, mid+1, end, tmp);

接著獲取分解的兩個數(shù)組的各自的首端到尾端的索引：

int begin1 = begin, end1 = mid;
int begin2 = mid + 1, end2 = end;

令要插入到數(shù)組tmp的起點為begin處：

int begin1 = begin, end1 = mid;
int begin2 = mid + 1, end2 = end;
int i = begin;

接下來遍歷兩個數(shù)組，無論誰先走完都跳出循環(huán)

while (begin1 <= end1 && begin2 <= end2)
{
	if (a[begin1] < a[begin2])
	{
		tmp[i] = a[begin1];
		i++;
		begin1++;
	}
	else
	{
		tmp[i] = a[begin2];
		i++;
		begin2++;
	}
}

這時會有一方?jīng)]有遍歷完，按照順序插入到新數(shù)組中即可

while (begin1 <= end1)
{
	tmp[i] = a[begin1];
	begin1++;
	i++;
}
while (begin2<= end2)
{
	tmp[i] = a[begin2];
	begin2++;
	i++;
}

插入到新數(shù)組后，我們拷貝到原數(shù)組中即完成了一次排序

	memcpy(a+begin,tmp+begin,sizeof(int )*(end-begin+1));

完整代碼如下：

void _MergrSort(int* a, int begin, int end, int* tmp)
{
	int mid = (begin + end) / 2;

	if (begin >= end)
	{
		return;
	}
	_MergrSort(a, begin, mid, tmp);
	_MergrSort(a, mid+1, end, tmp);
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int i = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			tmp[i] = a[begin1];
			i++;
			begin1++;
		}
		else
		{
			tmp[i] = a[begin2];
			i++;
			begin2++;
		}
	}
	while (begin1 <= end1)
	{
		tmp[i] = a[begin1];
		begin1++;
		i++;
	}
	while (begin2<= end2)
	{
		tmp[i] = a[begin2];
		begin2++;
		i++;
	}
	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 fail");
		return;
	}
	_MergrSort(a, 0, n - 1, tmp);
	free(tmp);
}

• 排序好的左半部分和右半部分接著被合并。為此，使用了兩個游標(biāo)begin1和begin2，它們分別指向兩個子數(shù)組的起始位置，然后比較兩個子數(shù)組當(dāng)前元素，將較小的元素拷貝到tmp數(shù)組中。這個過程繼續(xù)直到兩個子數(shù)組都被完全合并
• 在所有元素都被合并到tmp數(shù)組之后，使用memcpy將排序好的部分拷貝回原數(shù)組a。這個地方注意memcpy的第三個參數(shù)，它是sizeof(int)*(end - begin + 1)，表示拷貝的總大小，單位是字節(jié)
• begin和end變量在這里表示待排序和合并的數(shù)組部分的起止索引

本節(jié)內(nèi)容到此結(jié)束！感謝大家閱讀！文章來源地址http://www.zghlxwxcb.cn/news/detail-842982.html

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