目錄

??概念:

??實現(xiàn):

?1.hoare

?2.挖坑法

?3.雙指針法

??快速排序遞歸實現(xiàn)

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

??概念:

??????????通過一趟排序將要排序的數(shù)據分割成獨立的兩部分，其中一部分的所有數(shù)據比另一部分的所有數(shù)據要小，再按這種方法對這兩部分數(shù)據分別進行快速排序，整個排序過程可以遞歸進行，使整個數(shù)據變成有序序列。?

??排序過程:

1.在數(shù)組中確定一個關鍵值

2.將小于關鍵值的數(shù)排到其左邊,將大于關鍵值的數(shù)排到其右邊,此時關鍵數(shù)在數(shù)組中的位置就排好了

3.在左邊的數(shù)據和右邊的數(shù)據分別找一個關鍵值,通過排序使小于關鍵值的數(shù)排到其左邊,大于關鍵值的數(shù)排到其右邊...

4.重復上述操作,可以通過遞歸與非遞歸實現(xiàn)

快速排序的關鍵是寫好步驟二的單趟排序,實現(xiàn)這個功能有三種版本

1. hoare
2. 挖坑法
3. 雙指針法

??實現(xiàn):

?1.hoare

????????將數(shù)組第一個元素定位關鍵值,定義begin和end指針,先讓end從后往前找到比關鍵值小的數(shù),begin從前往后找比關鍵值大的數(shù),然后交換兩數(shù),直到 begin==end,再讓關鍵值和begin所指的元素交換,最后返回關鍵值所在位置,便于后續(xù)進行遞歸或非遞歸操作(一定要先從后往前找小,原因下文解釋)

動態(tài)展示:

void swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

//hoare
int PartSort1(int* a, int begin, int end)
{
	int left = begin, right = end;
	int keyi = begin;
	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[left], &a[keyi]);
	return left;
}

?2.挖坑法

????????首先將關鍵值定為數(shù)組第一個元素,并將坑位定為begin,先讓end從后往前找到比關鍵值小的數(shù),將這個數(shù)放到坑位,并更新坑位,再讓begin從前往后找比關鍵值大的數(shù),將這個數(shù)放到坑位,并更新坑位,直到 begin==end,再讓關鍵值和坑位的元素交換,最后返回關鍵值所在位置

//挖坑法
int PartSort2(int* a, int begin, int end)
{
	int mid = GetMid(a, begin, end);
	swap(&a[begin], &a[mid]);

	int key = a[begin];
	int hole = begin;
	while (begin < end)
	{
		//右邊找小,填入坑內,更新坑位
		while (begin<end && a[end]>=key)
		{
			--end;
		}
		a[hole] = a[end];
		hole = end;
		//左邊找大,填入坑內,更新坑位
		while (begin<end && a[begin]<=key)
		{
			++begin;
		}
		a[hole] = a[begin];
		hole = begin;
	}
	a[hole] = key;
	return hole;
}

?3.雙指針法

????????將數(shù)組第一個元素定為關鍵值,定義兩個指針prev和cur,先讓prev指向數(shù)組的第一個元素,cur指向prev的下一個元素,cur的作用是找比關鍵值小的元素,若cur所指元素不小于關鍵值則cur++,直到cur所值元素小于關鍵值,此時,prev和cur之間的元素都是大于關鍵值的元素,若prev+1不是cur的話就可以讓prev++所指元素與cur所指元素交換了,直到cur指向數(shù)組的最后一個元素

這里可能會有人出現(xiàn)問題:

1.為什么要判斷 prev++!=cur

[解釋]:如果prev+1為cur的話,那交換prev++和cur所指元素那就是一個元素之間的交換了,沒有意義

2.為什么要交換prev++所指元素

[解釋]:因為prev和cur之間的元素都為大于關鍵值的元素,prev++就可以讓prev指向大于關鍵值的元素,而cur所指的是小于關鍵值的元素,這樣一交換小的數(shù)就去前面了,大的數(shù)就去后面了

//雙指針法
int PartSort3(int* a, int begin, int end)
{
	int mid = GetMid(a, begin, end);
	swap(&a[begin], &a[mid]);

	int key = begin;
	int prev = begin;
	int cur = prev + 1;
	while (cur <= end)
	{
		if (a[cur] < a[key] && ++prev != cur)
		{
			swap(&a[prev], &a[cur]);
		}
		cur++;
	}
	swap(&a[prev], &a[key]);
	return prev;
}

??快速排序遞歸實現(xiàn)

?小優(yōu)化:

????????上述三個方法都是快速排序的單趟排序,但是上述排序還有一個小缺陷,因為三個方法都是固定第一個元素為關鍵值的,如果數(shù)組為有序的,那么從后往前找小就要遍歷整個數(shù)組,效率會很小,所以通常會再寫一個找中間值的函數(shù):在數(shù)組開頭結尾和中間三個數(shù)中找出一個大小在中間的數(shù),并讓這個數(shù)和數(shù)組第一個數(shù)交換,這樣就會減少上述情況的發(fā)生

int GetMid(int* a, int begin, int end)
{
	int mid = (begin + end) / 2;
	if (a[begin] > a[mid])
	{
		if (a[mid] > a[end])
			return mid;
		else if (a[end] > a[begin])
			return end;
		else
			return begin;
	}
	else
	{
		if (a[begin] > a[end])
			return begin;
		else if (a[end] > a[mid])
			return mid;
		else
			return end;
	}
}


void swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

//hoare
int PartSort1(int* a, int begin, int end)
{
	int mid = GetMid(a, begin, end);
	swap(&a[begin], &a[mid]);

	int left = begin, right = end;
	int keyi = begin;
	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[left], &a[keyi]);
	return left;
}

//挖坑法
int PartSort2(int* a, int begin, int end)
{
	int mid = GetMid(a, begin, end);
	swap(&a[begin], &a[mid]);

	int key = a[begin];
	int hole = begin;
	while (begin < end)
	{
		//右邊找小,填入坑內,更新坑位
		while (begin<end && a[end]>=key)
		{
			--end;
		}
		a[hole] = a[end];
		hole = end;
		//左邊找大,填入坑內,更新坑位
		while (begin<end && a[begin]<=key)
		{
			++begin;
		}
		a[hole] = a[begin];
		hole = begin;
	}
	a[hole] = key;
	return hole;
}
//雙指針法
int PartSort3(int* a, int begin, int end)
{
	int mid = GetMid(a, begin, end);
	swap(&a[begin], &a[mid]);

	int key = begin;
	int prev = begin;
	int cur = prev + 1;
	while (cur <= end)
	{
		if (a[cur] < a[key] && ++prev != cur)
		{
			swap(&a[prev], &a[cur]);
		}
		cur++;
	}
	swap(&a[prev], &a[key]);
	return prev;
}
void QuickSort(int* a, int begin,int end)
{
	if (begin >= end)
		return;
    
    //三種方法任選其一即可
	int keyi = PartSort3(a, begin, end);
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

補充:

為什么開始一定要右邊找小,并且為什么left和right相遇那個點一定小于關鍵值呢?

[解釋]:

????????L遇到R有兩種情況

• R遇到L: R從右往左找小,一直沒找到小,直到遇到L,而L的點的值小于關鍵值(因為此時L的值是和上一輪R找的小的值)
• L遇到R:R先從右找小,找到小停下來,L從左往右找打大沒有找到遇到R,相遇點的值小于關鍵值

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

????????快速排序的遞歸實現(xiàn),無非就是通過調用函數(shù)對數(shù)組的不同區(qū)間進行排序,而非遞歸我們也可以用棧實現(xiàn),不是遞歸勝似遞歸.

實現(xiàn)思路:
1.創(chuàng)建一個棧,將數(shù)組的右邊界下標和左邊界下標依次入棧

2.循環(huán)彈出數(shù)組的左右邊界下標,并對該區(qū)間進行單趟排序,確定關鍵值的下標,分為左右兩個區(qū)間

3.若左區(qū)間元素個數(shù)大于一個,將左區(qū)間右邊界下標和左邊界下標依次入棧,右區(qū)間同理

4.重復操作步驟2 3直到棧為空

例如待排序數(shù)組為:

第一步:將右邊界下標和左邊界下標7和0入棧

第二步:將邊界值彈出,將0給到begin,7給到end,進行單趟排序(單趟排序采用挖坑法)

排序完后,key將數(shù)組分為了左右兩個區(qū)間,讓右區(qū)間邊界7和5入棧,左邊界3和0入棧

第三步:取出0? 3并對此區(qū)間單趟排序

此時,關鍵值又把區(qū)間分為了兩個區(qū)間,右區(qū)間只有一個值,沒必要入棧排序,只需要將左區(qū)間邊界1 0入棧

再彈出0 1,對此區(qū)間單趟排序,此時左區(qū)間無元素,有區(qū)間只有一個元素,這樣數(shù)組左邊就全部排序完成了,再次出棧的話就該排序5和7的區(qū)間了,和左邊類似

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

void QuickSortNonR(int* a, int begin, int end)
{
	ST s;
	STInit(&s);
	STPush(&s,end);
	STPush(&s,begin);

	while (!STEmpty(&s))
	{
		int left = STTop(&s);
		STPop(&s);
		int right = STTop(&s);
		STPop(&s);

		int key = PartSort1(a, left, right);

		if (left < key - 1)
		{
			STPush(&s, key - 1);
			STPush(&s, left);
		}

		if (right > key + 1)
		{
			STPush(&s, right);
			STPush(&s, key+1);
		}
	}
	STDestroy(&s);
}

到了這里，關于[C/C++]排序算法 快速排序 (遞歸與非遞歸)的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！