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

一.快排實(shí)現(xiàn) 二.快排優(yōu)化 ? ? 1.三數(shù)取中，隨機(jī)取中 ? ? ?2..小區(qū)間優(yōu)化

成都創(chuàng)新互聯(lián)成立以來不斷整合自身及行業(yè)資源、不斷突破觀念以使企業(yè)策略得到完善和成熟，建立了一套“以技術(shù)為基點(diǎn)，以客戶需求中心、市場為導(dǎo)向”的快速反應(yīng)體系。對公司的主營項(xiàng)目，如中高端企業(yè)網(wǎng)站企劃 / 設(shè)計(jì)、行業(yè) / 企業(yè)門戶設(shè)計(jì)推廣、行業(yè)門戶平臺運(yùn)營、成都App定制開發(fā)、手機(jī)網(wǎng)站制作、微信網(wǎng)站制作、軟件開發(fā)、成都多線機(jī)房等實(shí)行標(biāo)準(zhǔn)化操作，讓客戶可以直觀的預(yù)知到從成都創(chuàng)新互聯(lián)可以獲得的服務(wù)效果。一.快排實(shí)現(xiàn) 快排的一趟目的，將一個(gè)數(shù)的移動到，左邊都比他小，右邊都比他大，這個(gè)數(shù)也相當(dāng)于到了自己最終要到的位置。這樣就能形成兩部分，再進(jìn)行遞歸左右區(qū)間，選數(shù)放到合適位置，這樣就達(dá)到排序的目的了。 一趟排序的實(shí)現(xiàn)我們可以采用前后指針法達(dá)到目的 定義變量prev,cur和基準(zhǔn)key，關(guān)鍵位置keyi

如果cur位置上的值小于key，我們先++prev,如果++prev后 prev==cur 我們就++cur,不交換； ++prev后不等于cur,我們要交換prev和cur位置的值，再++cur，這樣我們就避免了原地交換。

如果cur位置上的值大于key,我們就只++cur?

重復(fù)上面過程，當(dāng)cur走出數(shù)組時(shí)結(jié)束循環(huán)

最后我們再將prev上的值和關(guān)鍵位置上的值交換即可

這樣我們就完成了一次交換接下來我們進(jìn)行左右區(qū)間的遞歸即可。 下面是相關(guān)代碼：
// 快速排序前后指針法
int PartSort(int* a, int left, int right)
{
	int keyi = left;
	int prev = left,cur = left + 1;
	while (cur<= right)
	{   
		//滿足前一個(gè)判斷，++prev,如果prev==cur不會進(jìn)行交換
		if (a[cur]< a[keyi] && ++prev != cur)
		{
			Swap(&a[cur], &a[prev]);
		}
		cur++;
	}
	Swap(&a[prev], &a[keyi]);
	keyi = prev;
	return keyi;
}

void QuickSort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int keyi = PartSort3(a, left, right);
    //不斷的選key,劃分區(qū)間我們就能實(shí)現(xiàn)排序的目的
	//[left,keyi-1] keyi [key+1,right]
	QuickSort(a, left, keyi-1);
	QuickSort(a, keyi + 1, right);
}
void testQuickSort()
{
	int a[] = { 9, 1, 2, 4, 7, 8, 6, 3, 5 };
    //注意我們要傳數(shù)組最后一個(gè)值的下標(biāo)
	QuickSort1(a, 0, sizeof(a) / sizeof(a[0]) - 1);
	PrintArray(a, sizeof(a) / sizeof(a[0]));
}
二.快排優(yōu)化 1.三數(shù)取中，隨機(jī)取中

我們排序時(shí)可能遇到有序或接近有序的數(shù)組，我們一直選取第一個(gè)數(shù)作為關(guān)鍵值key,可能會造成我們選到的數(shù)是大的或是最小的，這樣成劃分區(qū)間次數(shù)接近n,這樣我們的快排此時(shí)的時(shí)間復(fù)雜度就是O（N^2）,為了避免這樣選到這樣數(shù)，我們可以進(jìn)行三數(shù)取中，就是對我們要劃分的區(qū)間第一個(gè)數(shù)，最后一個(gè)數(shù)，和中間的數(shù)進(jìn)行比較，選到一個(gè)中間的數(shù)即可。 當(dāng)然我們也可以交給電腦，隨機(jī)進(jìn)行取數(shù)，我們最后再交換到第一個(gè)位置上即可。
int GetMidIndexR(int* a, int left, int right)
{
    //三數(shù)取中 
    int mid = left + (right - left) / 2;

    // 三數(shù)取中  隨機(jī)選key 
	//int mid = left + rand() % (right - left);

	if (a[mid] >a[left])
	{
		if (a[right] >a[mid])
		{
			return mid;
		}
		else if (a[left] >a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else
	{
		if (a[mid] >a[right])
		{
			return mid;
		}
		else if (a[right] >a[left])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}
// 快速排序前后指針法
int PartSort3(int* a, int left, int right)
{
	int index = GetMidIndex(a, left, right);
	Swap(&a[index], &a[left]);

	int keyi = left;
	int prev = left,cur = left + 1;
	while (cur<= right)
	{   
		//滿足前一個(gè)判斷，++prev,如果prev==cur不會進(jìn)行交換
		if (a[cur]< a[keyi] && ++prev != cur)
		{
			Swap(&a[cur], &a[prev]);
		}
		cur++;
	}
	Swap(&a[prev], &a[keyi]);
	keyi = prev;
	return keyi;
}
2.小區(qū)間優(yōu)化 我們知道遞歸調(diào)的過程會建立一層層的棧幀，浪費(fèi)空間和時(shí)間，我們可以將區(qū)間長度較小的直接用其他排序幫我們排好，我們就省去了很大一部分的遞歸調(diào)用。如果我們每次都平均劃分，數(shù)組長度為n,最后三層 2^(n-1)，2^(n-2)，2^(n-3)把他們加在一起就可以省去近70%的遞歸調(diào)用了。 一般來說小區(qū)間優(yōu)化使我們一般使用插入排序，進(jìn)行數(shù)組長度小于15時(shí)進(jìn)行插入排序。

下面就是我們進(jìn)行優(yōu)化過的代碼：

// 插入排序
void InsertSort(int* a, int n)
{   
	for (int i = 0; i< n - 1; i++)
	{
		int end = i;
		int tmp = a[end+1];
		while (end >= 0)
		{
			if (a[end] >tmp)
			{
				a[end+1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
	
}
int GetMidIndexR(int* a, int left, int right)
{
    //三數(shù)取中 
    int mid = left + (right - left) / 2;

    // 三數(shù)取中  隨機(jī)選key 
	//int mid = left + rand() % (right - left);

	if (a[mid] >a[left])
	{
		if (a[right] >a[mid])
		{
			return mid;
		}
		else if (a[left] >a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else
	{
		if (a[mid] >a[right])
		{
			return mid;
		}
		else if (a[right] >a[left])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}
// 快速排序前后指針法
int PartSort(int* a, int left, int right)
{
	int index = GetMidIndex(a, left, right);
	Swap(&a[index], &a[left]);

	int keyi = left;
	int prev = left,cur = left + 1;
	while (cur<= right)
	{   
		//滿足前一個(gè)判斷，++prev,如果prev==cur不會進(jìn)行交換
		if (a[cur]< a[keyi] && ++prev != cur)
		{
			Swap(&a[cur], &a[prev]);
		}
		cur++;
	}
	Swap(&a[prev], &a[keyi]);
	keyi = prev;
	return keyi;
}
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	//小區(qū)間優(yōu)化    區(qū)間數(shù)量較小時(shí)，避免大量的分區(qū)間
	if ((right - left + 1)< 15)
	{
		InsertSort(a+left, right - left + 1);
	}
	else
	{
		int keyi = PartSort(a, left, right);
		//[left,keyi-1] keyi [key+1,right]
		QuickSort(a, left, keyi-1);
		QuickSort(a, keyi + 1, right);
	}
}
最后感謝觀看！

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

當(dāng)前題目：快速排序（C語言實(shí)現(xiàn)）-創(chuàng)新互聯(lián)
轉(zhuǎn)載來源：http://bm7419.com/article42/ggchc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供動態(tài)網(wǎng)站、自適應(yīng)網(wǎng)站、微信公眾號、搜索引擎優(yōu)化、網(wǎng)站改版、App設(shè)計(jì)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)

營銷型網(wǎng)站建設(shè)