常用的較優(yōu)排序之快速排序，堆排序，歸并排序-創(chuàng)新互聯(lián)

1、快速排序

創(chuàng)新互聯(lián)一直通過(guò)網(wǎng)站建設(shè)和網(wǎng)站營(yíng)銷(xiāo)幫助企業(yè)獲得更多客戶資源。 以"深度挖掘，量身打造，注重實(shí)效"的一站式服務(wù)，以網(wǎng)站設(shè)計(jì)、網(wǎng)站建設(shè)、移動(dòng)互聯(lián)產(chǎn)品、網(wǎng)絡(luò)營(yíng)銷(xiāo)推廣服務(wù)為核心業(yè)務(wù)。10余年網(wǎng)站制作的經(jīng)驗(yàn)，使用新網(wǎng)站建設(shè)技術(shù)，全新開(kāi)發(fā)出的標(biāo)準(zhǔn)網(wǎng)站，不但價(jià)格便宜而且實(shí)用、靈活，特別適合中小公司網(wǎng)站制作。網(wǎng)站管理系統(tǒng)簡(jiǎn)單易用，維護(hù)方便，您可以完全操作網(wǎng)站資料，是中小公司快速網(wǎng)站建設(shè)的選擇。

通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序?？梢杂眠f歸和非遞歸的方法分別實(shí)現(xiàn)。

  平均狀況下，排序n個(gè)項(xiàng)目要Ο(n log n)次比較。在最壞狀況下則需要Ο(n2)次比較，但這種狀況并不常見(jiàn)。事實(shí)上，快速排序通常明顯比其他Ο(n log n) 算法更快。

int _QuickSort(int* a,int left,int right,int key)
{
	while (left < right)
	{
		while (left < right&&a[left] <=a[key])
		{
			left++; //找出比a[key]大的下標(biāo)
		}
		while (left < right&&a[right] >=a[key])
		{
			right--; //找出比a[key]小的下標(biāo)
		}
		swap(a[left], a[right]);  //交換
	}
	if (a[left] > a[key])   //如果需要排序的序列都小于a[key]值	
		swap(a[left],a[key]);//把 key-1 當(dāng)邊界，如圖中當(dāng)?shù)诙蝍[key]為5時(shí)。
		return left;     
	}
	return key;
}

int _QuickSort2(int* a, int left, int right, int key)
{
	int cur = left;
	int prev = left - 1;
	while (cur <= right)
	{
		if (a[cur] <= a[key])
		{
			prev++;
			if(prev!=cur)
				swap(a[prev], a[cur]);
		}
		cur++;
	}
	swap(a[prev+1],a[key]);
	return prev+1;
}

void QuickSort(int* a, int left, int right)
{
	assert(a);
	if (left < right)
	{
		int mid = FindMid(a,left,right);//3位取中，把左邊右邊和中間的數(shù)比較，找出中間的數(shù)作為key
		swap(a[mid],a[right]);
		int key = right;
		int boundary=_QuickSort2(a,left,right-1,key);//一趟排序后找出邊界值
		//int boundary=_QuickSort(a,left,right-1,key);//有兩種方法找出邊界值
		QuickSort(a,left,boundary-1);
		QuickSort(a, boundary+1,right);
	}
} 
//非遞歸借用棧來(lái)完成
void NORQucikSort(int* a,int left,int right)
{
	stack<int> s1;
	s1.push(left);
	s1.push(right);
	while (!s1.empty())
	{
		int key = s1.top();
		int _right = s1.top();
		s1.pop();
		int _left = s1.top();
		s1.pop();
		if (_left >= _right)  
			continue;
		int boundary = _QuickSort(a, _left, _right - 1, key);
		//int boundary = _QuickSort2(a, _left, _right - 1, key);
		s1.push(boundary + 1); //先壓key右邊的序列
		s1.push(_right);

		s1.push(_left);
		s1.push(boundary-1);
	}
}
//優(yōu)化快速排序  三數(shù)取中
int FindMid(int* a, int left, int right)
{
	int mid = left + (right - left) / 2;
	if (a[left] > a[right])
	{
		if (a[left] < a[mid])
			return left;
		else if (a[mid]>a[right])
			return mid;
		return right;
	}
	else
	{
		if (a[left] > a[mid])
			return left;
		else if (a[mid] < a[right])
			return mid;
		return right;
	}
}

2、堆排序

堆排序的思想就是如果是升序排序，則建大堆，反之，則建最小堆。

建堆之后，從第一個(gè)數(shù)開(kāi)始和最后一個(gè)數(shù)交換，縮小堆的范圍（去除最后一個(gè)數(shù)），然后第一個(gè)數(shù)向下調(diào)整，則大的數(shù)已在最后。直到堆里只有一個(gè)數(shù)。

建堆過(guò)程就是從最后一個(gè)非葉子節(jié)點(diǎn)直到跟節(jié)點(diǎn)向下調(diào)整。假設(shè)我們現(xiàn)在要升序排序。即就是向下調(diào)整時(shí)，把小的交換到父節(jié)點(diǎn)。

堆排序的時(shí)間復(fù)雜度是O(N*lgN),空間復(fù)雜度是O(1)。

void AdjustDown(int *a,int size,int parent)   //向下對(duì)齊
{
	int child = parent * 2 + 1;           //把左孩子的下標(biāo)給child
	while (child < size)        //保證向下對(duì)齊直到child超出范圍
	{
		if (child + 1 < size&&a[child + 1] > a[child])  //當(dāng)右孩子>左孩子時(shí),child變?yōu)橛液⒆酉聵?biāo)
		{
			child++;
		}
		if (a[parent] < a[child])
		{
			swap(a[parent],a[child]);
			parent = child;               
			child = parent * 2 + 1;       
		}
		else
		{
			break;
		}
	}
}

void HeapSort(int *a, int size)
{
	assert(a);
	for (int i = (size - 2) / 2; i >= 0; i--)
	{
		AdjustDown(a,size,i);         //從圖中下標(biāo)為4的非葉子節(jié)點(diǎn)開(kāi)始，進(jìn)行向下對(duì)齊
	}
	for (int i = size - 1; i > 0; i--)
	{
		swap(a[0],a[i]);  //把大堆中的第一個(gè)元素和最后一個(gè)元素交換，此時(shí)最后一個(gè)元素大
		AdjustDown(a,i,0);//把剩余的元素建成大堆
	}
}

3、歸并排序

 歸并排序時(shí)的時(shí)間復(fù)雜度為O（nlgn) 其主要思想是分治法(divide and conquer)，分就是要將n個(gè)元素的序列劃分為兩個(gè)序列，再分為4個(gè)序列，直到每個(gè)序列只有一個(gè)數(shù)，然后合并兩個(gè)有效序列為一個(gè)有效序列，直到整個(gè)序列為有序序列。

歸并排序的時(shí)間復(fù)雜度O(N*lgN),空間復(fù)雜度是O(N)。

遞歸實(shí)現(xiàn)：

void MergeSort(int *a, int size)
{
	assert(a);
	int *tmp = new int[size];
	int left = 0, right = size - 1;
	_MergeSort(a,tmp,left,right);
}
void _MergeSort(int* a, int* tmp, int left, int right)
{
	if (left < right)
	{
		int mid = left + (right - left) / 2;//取中間下標(biāo)
		_MergeSort(a,tmp,left,mid);       //遞歸進(jìn)行
		_MergeSort(a, tmp, mid+1, right);  //直到遞歸到左右序列只有一個(gè)元素
		Combine(a,tmp,left,mid,mid+1,right);//2個(gè)有序序列合并成一個(gè)
		memcpy(a+left,tmp,(right-left+1)*sizeof(int));//把有序序列拷給原數(shù)組
	}
}
void Combine(int* a, int* tmp, int begin1, int end1,int begin2, int end2)
{
	int index = 0;
	while (begin1 <= end1&&begin2 <= end2)
	{
		while (a[begin1] <= a[begin2]&&begin1<=end1)
		{
			tmp[index++] = a[begin1];
			begin1++;
		}
		while (a[begin1] > a[begin2] && begin2 <= end2)
		{
			tmp[index++] = a[begin2];
			begin2++;
		}
	}
	while (begin1 <= end1)
	{
		tmp[index++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[index++] = a[begin2++];
	}
}

而遞歸排序的非遞歸實(shí)現(xiàn)，則采取相反的思路，先把整個(gè)數(shù)組分成n個(gè)序列，每次兩個(gè)序列合并。每?jī)蓚€(gè)序列有序后，合4個(gè)序列，以此類(lèi)推。

void MergeSort2(int *a, int size)
{
	assert(a);
	int gap = 0;
	int *temp = new int[size];
	int count = 0;
	//gap指begin1和end1每次的差值 所差次數(shù)依次為，0,1,3,7（2^n-1）
	while (gap < size)
	{
		int begin1 = 0, end1 = gap, begin2 = end1 + 1, end2 = begin2 + gap;
		for (; end2 < size; begin1=end2+1,end1=begin1+gap,begin2=end1+1,end2=begin2+gap)
		{
			Combine(a,temp,begin1,end1,begin2,end2);
			memcpy(a+begin1,temp,(end2-begin1+1)*sizeof(int));
		}
		if (begin2 < size)
		{
			end2 = size - 1;
			Combine(a, temp, begin1, end1, begin2, size-1);
			memcpy(a + begin1, temp, (end2 - begin1 + 1)*sizeof(int));
		}
		count++;
		gap=pow(2,count)-1;
	}

}

創(chuàng)新互聯(lián)www.cdcxhl.cn，專(zhuān)業(yè)提供香港、美國(guó)云服務(wù)器，動(dòng)態(tài)BGP最優(yōu)骨干路由自動(dòng)選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證， 機(jī)房獨(dú)有T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確進(jìn)行流量調(diào)度，確保服務(wù)器高可用性。佳節(jié)活動(dòng)現(xiàn)已開(kāi)啟，新人活動(dòng)云服務(wù)器買(mǎi)多久送多久。

分享文章：常用的較優(yōu)排序之快速排序，堆排序，歸并排序-創(chuàng)新互聯(lián)
當(dāng)前地址：http://muchs.cn/article42/dpcchc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供自適應(yīng)網(wǎng)站、小程序開(kāi)發(fā)、ChatGPT、云服務(wù)器、品牌網(wǎng)站制作、軟件開(kāi)發(fā)

廣告

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