數(shù)據(jù)結(jié)構(gòu)——排序算法之快速排序

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

? 數(shù)據(jù)結(jié)構(gòu)——排序算法之快速排序,數(shù)據(jù)結(jié)構(gòu),算法,數(shù)據(jù)結(jié)構(gòu),排序算法,c語言

??個人主頁：日刷百題

系列專欄：〖C/C++小游戲〗〖Linux〗〖數(shù)據(jù)結(jié)構(gòu)〗?〖C語言〗

??歡迎各位→點贊??+收藏??+留言????

? 數(shù)據(jù)結(jié)構(gòu)——排序算法之快速排序,數(shù)據(jù)結(jié)構(gòu),算法,數(shù)據(jù)結(jié)構(gòu),排序算法,c語言

前言：

快速排序是Hoare于1962年提出的一種二叉樹結(jié)構(gòu)的交換排序方法。

基本思想：

任取待排序元素序列中的某元素作為基準(zhǔn)值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準(zhǔn)值，右子序列中所有元素均大于基準(zhǔn)值，然后最左右子序列重復(fù)該過程，直到所有元素都排列在相應(yīng)位置上為止。

遞歸實現(xiàn)方式常見有三種，區(qū)別于單趟思想，性能差別不大，下面我們看下快排遞歸實現(xiàn)。

一、快速排序的遞歸實現(xiàn)

1.1? ?Hoare排序

1.1.1??單趟目的

?左子序列中所有元素均小于基準(zhǔn)值key，右子序列中所有元素均大于基準(zhǔn)值key。

1.1.2? ?動圖解析

數(shù)據(jù)結(jié)構(gòu)——排序算法之快速排序,數(shù)據(jù)結(jié)構(gòu),算法,數(shù)據(jù)結(jié)構(gòu),排序算法,c語言

單趟思路：

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

該排序有一個需要注意的點是：必須左邊先走找小

因為左邊先走，必定相遇時位置對應(yīng)的值小于keyi位置值，保證最后這倆個位置交換，相遇位置即是keyi位置對應(yīng)值最終位置。

解析：

（1）右邊先走，假設(shè)left遇到right,最后相遇情況是right找到了小于keyi位置的值，left沒有找到大于keyi位置值，所以相遇位置值小于keyi位置值。

（2）右邊先走，假設(shè)right遇到left,最后相遇情況是left找到大，right找到小，left與right互換，left位置對應(yīng)值小于keyi位置值，right繼續(xù)找小，與left相遇，所以相遇位置值小于keyi位置值。

?1.1.3? 代碼實現(xiàn)

解析：

該代碼將單趟寫在子函數(shù)中，這樣使得整個代碼層次更加清晰，也便于理解?？梢园l(fā)現(xiàn)我們對單趟中keyi做了優(yōu)化，因為keyi的位置，是影響快速排序效率的重大因素。因此我們采用了三數(shù)取中的方法解決選keyi不合適的問題。即知道這組無序數(shù)列的首和尾后，我們只需要在首，中，尾這三個數(shù)據(jù)中，選擇一個排在中間的數(shù)據(jù)作為基準(zhǔn)值(keyi)，進(jìn)行快速排序，即可進(jìn)一步提高快速排序的效率。

后面2種單趟也做這樣的優(yōu)化，后面就不過多介紹。

//Hoare快排
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[begin] > a[mid])
			{
				return mid;
			}
			else
			{
				return begin;
			}
		}
	}
	else//(a[begin]<= a[end])
	{
		if (a[begin] > a[mid])
		{
			return begin;
		}
		else
		{
			if (a[end] > a[mid])
			{
				return mid;
			}
			else
			{
				return end;
			}
		}
	}
}
void swap(int* x, int* y)
{
	int z = *x;
	*x = *y;
	*y = z;
}
int  _QuickSort_Hoare(int* a, int begin, int end)
{
	int mid = GetMid(a,begin, end);
	swap(&a[begin], &a[mid]);
	int keyi = begin;
	int left = begin;
	int right = end;
	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]);
	return left;

}
void  QuickSort_Hoare(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int keyi= _QuickSort_Hoare(a, begin, end);//單趟
	//遞歸  [begin,keyi-1] keyi,[keyi+1,end]
	QuickSort_Hoare(a, begin, keyi - 1);
	QuickSort_Hoare(a, keyi+1, end);

}

1.2? 挖坑法?

1.2.1? 單趟目的

?左子序列中所有元素均小于基準(zhǔn)值key，右子序列中所有元素均大于基準(zhǔn)值key。

1.2.2? 動圖解析

單趟思路：

（1）將begin處的值放到key中，將其置為坑位(pit)
（2）right找到比key小的值后將值放入坑位，然后將此處置為新的坑。
? (3)? left找到比key大的值后將值放入坑位，然后將此處置為新的坑。
? (4）當(dāng)left與right相遇的時候，將key放入到坑位中。

?1.2.3? 代碼實現(xiàn)?

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[begin] > a[mid])
			{
				return mid;
			}
			else
			{
				return begin;
			}
		}
	}
	else//(a[begin]<= a[end])
	{
		if (a[begin] > a[mid])
		{
			return begin;
		}
		else
		{
			if (a[end] > a[mid])
			{
				return mid;
			}
			else
			{
				return end;
			}
		}
	}
}
void swap(int* x, int* y)
{
	int z = *x;
	*x = *y;
	*y = z;
}
int  _QuickSort_Pit(int* a, int begin, int end)
{
	int mid = GetMid(a, begin, end);
	swap(&a[begin], &a[mid]);
	int pit = begin;
	int  key = a[begin];
	int left = begin;
	int right = end;
	while (left < right)
	{
		while (left < right && a[right] >= key)
		{
			right--;
		}
		a[pit] = a[right];
		pit = right;
		while(left < right&& a[left] <= key)
		{
			left++;
		}
		a[pit] = a[left];
		pit = left;
	}
	a[left] = key;
	return left;

}
void  QuickSort_Pit(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int keyi = _QuickSort_Pit(a, begin, end);
	//[begin,keyi-1],keyi,[keyi+1,end]
	QuickSort_Pit(a, begin, keyi - 1);
	QuickSort_Pit(a, keyi + 1, end);

}

1.3 雙指針法

1.3.1? 單趟目的

?左子序列中所有元素均小于基準(zhǔn)值key，右子序列中所有元素均大于基準(zhǔn)值key。

1.3.2? 動圖解析

單趟思路：

(1)cur位于begin+1的位置，prev位于begin位置，keyi先存放begin處的值。
(2)如果cur處的值大于key處的值，cur++.
(3)如果cur處的值小于等于key處的值，cur處的值，則與prev+1處的值進(jìn)行交換。
(4)當(dāng)循環(huán)結(jié)束時，將prev處的值與keyi的值相交換，返回prev

1.3.3??代碼實現(xiàn)

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[begin] > a[mid])
		{
			return mid;
		}
		else
		{
			return begin;
		}
	}
}
else//(a[begin]<= a[end])
{
	if (a[begin] > a[mid])
	{
		return begin;
	}
	else
	{
		if (a[end] > a[mid])
		{
			return mid;
		}
		else
		{
			return end;
		}
	}
}
}
void swap(int* x, int* y)
{
	int z = *x;
	*x = *y;
	*y = z;
}
int  _QuickSort_Pointer(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])
		{
			cur++;
		}
		else
		{
			prev++;
			swap(&a[prev], &a[cur]);
			cur++;

		}
	}
	swap(&a[key], &a[prev]);
	return prev;

}
void  QuickSort_Pointer(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int keyi = _QuickSort_Pointer(a, begin, end);
	//[begin,keyi-1],keyi,[keyi+1,end]
	QuickSort_Pointer(a, begin, keyi - 1);
	QuickSort_Pointer(a, keyi + 1, end);

}

二、快速排序的優(yōu)化

2.1??三數(shù)取中法選key

這個方法提升效率比較顯著，上面已經(jīng)排序均用該方法優(yōu)化。

2.2??遞歸到小的子區(qū)間，使用插入排序

由于快速排序是遞歸進(jìn)行的，當(dāng)遞歸到最后三層時，此時數(shù)組中的值其實已經(jīng)接近有序，而且這段區(qū)間再遞歸會極大占用棧(函數(shù)棧幀開辟的地方)的空間,最后三層的遞歸次數(shù)占總遞歸次數(shù)的百分之90，所以在區(qū)間數(shù)據(jù)量小于10，我們就不進(jìn)行遞歸快速排序了，轉(zhuǎn)而使用插入排序。

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[begin] > a[mid])
		{
			return mid;
		}
		else
		{
			return begin;
		}
	}
}
else//(a[begin]<= a[end])
{
	if (a[begin] > a[mid])
	{
		return begin;
	}
	else
	{
		if (a[end] > a[mid])
		{
			return mid;
		}
		else
		{
			return end;
		}
	}
}
}
void swap(int* x, int* y)
{
	int z = *x;
	*x = *y;
	*y = z;
}
int  _QuickSort_Pointer(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])
		{
			cur++;
		}
		else
		{
			prev++;
			swap(&a[prev], &a[cur]);
			cur++;

		}
	}
	swap(&a[key], &a[prev]);
	return prev;

}
void  QuickSort_Pointer(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	if(end-begin+1>10)
{
int keyi = _QuickSort_Pointer(a, begin, end);
	//[begin,keyi-1],keyi,[keyi+1,end]
	QuickSort_Pointer(a, begin, keyi - 1);
	QuickSort_Pointer(a, keyi + 1, end);
}
else
{
InsertSort(a + begin, end - begin + 1);
}

}

三、快速排序的非遞歸實現(xiàn)

遞歸改為非遞歸，一般2種方法：

1、遞歸轉(zhuǎn)化為非遞歸可以寫成循環(huán)，比如斐波那契數(shù)列

2、遞歸轉(zhuǎn)化為非遞歸可以寫成棧，比如現(xiàn)在的快排

遞歸使用的空間是棧空間，所以容易出現(xiàn)棧溢出的情況，我們將快速排序改為非遞歸版本，這樣空間的開辟就在堆上了，這樣也就解決了這個問題。

快速排序的非遞歸與遞歸思想相同，非遞歸使用棧來模擬遞歸的實現(xiàn)，思路如下：

（1）入棧一定要保證先入左再入右。
（2）取出兩次棧頂?shù)脑?，然后進(jìn)行單趟排序

（3）將區(qū)間分為[left , keyi - 1] ，keyi ，[ keyi + ?1 , right ] 進(jìn)行右、左入棧。若區(qū)間不存在或為1個值則不入棧。
（4）循環(huán)2、3步驟直到棧為空。
?

代碼實現(xiàn)：

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[begin] > a[mid])
		{
			return mid;
		}
		else
		{
			return begin;
		}
	}
}
else//(a[begin]<= a[end])
{
	if (a[begin] > a[mid])
	{
		return begin;
	}
	else
	{
		if (a[end] > a[mid])
		{
			return mid;
		}
		else
		{
			return end;
		}
	}
}
}
void swap(int* x, int* y)
{
	int z = *x;
	*x = *y;
	*y = z;
}
int  _QuickSort_Pointer(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])
		{
			cur++;
		}
		else
		{
			prev++;
			swap(&a[prev], &a[cur]);
			cur++;

		}
	}
	swap(&a[key], &a[prev]);
	return prev;

}

typedef int DateType;
typedef struct Stack
{
    DateType* a;
    int top;
    int capacity;
}Stack;
//初始化和銷毀棧
void InitStack(Stack* ps)
{
    assert(ps);
    ps->a = NULL;
    ps->top = ps->capacity = 0;
}
void DestoryStack(Stack* ps)
{
    assert(ps);
    free(ps->a);
    ps->a = NULL;
    ps->top = 0;
    ps->capacity = 0;
}

//出棧和入棧
void StackPush(Stack* ps, DateType x)
{
    assert(ps);
    if (ps->top == ps->capacity)
    {
        int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
        DateType* tmp = (DateType*)realloc(ps->a, sizeof(DateType) * newcapacity);
        if (tmp == NULL)
        {
            perror("realloc fail:");
            return;
        }
        ps->a = tmp;
        ps->capacity = newcapacity;
    }
    ps->a[ps->top] = x;
    ps->top++;
}
void StackPop(Stack* ps)
{
    assert(ps);
    assert(ps->top > 0);
    ps->top--;
}

//棧的有效個數(shù)和棧頂元素
int StackSize(Stack* ps)
{
    assert(ps);
    return ps->top;
}
DateType StackTop(Stack* ps)
{
    assert(ps);
    assert(ps->top > 0);
    return   ps->a[ps->top - 1];
}
//判空
bool IsEmptyStack(Stack* ps)
{
    assert(ps);
    return ps->top == 0;
}
void  QuickSort_Non_r(int* a, int begin, int end)
{
    Stack tmp;
    InitStack(&tmp);
    StackPush(&tmp,end);
    StackPush(&tmp, begin);
    while (!IsEmptyStack(&tmp))
    {
        int left = StackTop(&tmp);
        StackPop(&tmp);
        int right = StackTop(&tmp);
        StackPop(&tmp);


        int keyi = _QuickSort_Pointer(a, left, right);
        if (keyi+1 <right)
        {
            StackPush(&tmp,right);
            StackPush(&tmp,keyi+1);

        }
        if (left < keyi - 1)
        {
            StackPush(&tmp, keyi-1);
            StackPush(&tmp,left);
        }
   }

    DestoryStack(&tmp);



}

?總結(jié)：本篇文章總結(jié)了快速排序的遞歸及非遞歸倆大種方式。

希望大家閱讀完可以有所收獲，同時也感謝各位鐵汁們的支持。文章有任何問題可以在評論區(qū)留言，百題一定會認(rèn)真閱讀！文章來源地址http://www.zghlxwxcb.cn/news/detail-810292.html

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