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

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

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

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

重復上面過程，當cur走出數(shù)組時結束循環(huán)

最后我們再將prev上的值和關鍵位置上的值交換即可

這樣我們就完成了一次交換接下來我們進行左右區(qū)間的遞歸即可。 下面是相關代碼：

// 快速排序前后指針法
int PartSort(int* a, int left, int right)
{
	int keyi = left;
	int prev = left,cur = left + 1;
	while (cur<= right)
	{   
		//滿足前一個判斷，++prev,如果prev==cur不會進行交換
		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ū)間我們就能實現(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ù)組最后一個值的下標
	QuickSort1(a, 0, sizeof(a) / sizeof(a[0]) - 1);
	PrintArray(a, sizeof(a) / sizeof(a[0]));
}

二.快排優(yōu)化 1.三數(shù)取中，隨機取中

我們排序時可能遇到有序或接近有序的數(shù)組，我們一直選取第一個數(shù)作為關鍵值key,可能會造成我們選到的數(shù)是大的或是最小的，這樣成劃分區(qū)間次數(shù)接近n,這樣我們的快排此時的時間復雜度就是O（N^2）,為了避免這樣選到這樣數(shù)，我們可以進行三數(shù)取中，就是對我們要劃分的區(qū)間第一個數(shù)，最后一個數(shù)，和中間的數(shù)進行比較，選到一個中間的數(shù)即可。 當然我們也可以交給電腦，隨機進行取數(shù)，我們最后再交換到第一個位置上即可。

int GetMidIndexR(int* a, int left, int right)
{
    //三數(shù)取中 
    int mid = left + (right - left) / 2;

    // 三數(shù)取中  隨機選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)
	{   
		//滿足前一個判斷，++prev,如果prev==cur不會進行交換
		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)化 我們知道遞歸調的過程會建立一層層的棧幀，浪費空間和時間，我們可以將區(qū)間長度較小的直接用其他排序幫我們排好，我們就省去了很大一部分的遞歸調用。如果我們每次都平均劃分，數(shù)組長度為n,最后三層 2^(n-1)，2^(n-2)，2^(n-3)把他們加在一起就可以省去近70%的遞歸調用了。 一般來說小區(qū)間優(yōu)化使我們一般使用插入排序，進行數(shù)組長度小于15時進行插入排序。

下面就是我們進行優(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ù)取中  隨機選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)
	{   
		//滿足前一個判斷，++prev,如果prev==cur不會進行交換
		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ù)量較小時，避免大量的分區(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)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

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

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

廣告

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