1、快速排序

創新互聯一直通過網站建設和網站營銷幫助企業獲得更多客戶資源。 以"深度挖掘，量身打造，注重實效"的一站式服務，以網站設計、網站建設、移動互聯產品、網絡營銷推廣服務為核心業務。10余年網站制作的經驗，使用新網站建設技術，全新開發出的標準網站，不但價格便宜而且實用、靈活，特別適合中小公司網站制作。網站管理系統簡單易用，維護方便，您可以完全操作網站資料，是中小公司快速網站建設的選擇。

通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序。可以用遞歸和非遞歸的方法分別實現。

  平均狀況下，排序n個項目要Ο(n log n)次比較。在最壞狀況下則需要Ο(n2)次比較，但這種狀況并不常見。事實上，快速排序通常明顯比其他Ο(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]大的下標
		}
		while (left < right&&a[right] >=a[key])
		{
			right--; //找出比a[key]小的下標
		}
		swap(a[left], a[right]);  //交換
	}
	if (a[left] > a[key])   //如果需要排序的序列都小于a[key]值	
		swap(a[left],a[key]);//把 key-1 當邊界，如圖中當第二次a[key]為5時。
		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位取中，把左邊右邊和中間的數比較，找出中間的數作為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);
	}
} 
//非遞歸借用棧來完成
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);
	}
}
//優化快速排序  三數取中
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、堆排序

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

建堆之后，從第一個數開始和最后一個數交換，縮小堆的范圍（去除最后一個數），然后第一個數向下調整，則大的數已在最后。直到堆里只有一個數。

建堆過程就是從最后一個非葉子節點直到跟節點向下調整。假設我們現在要升序排序。即就是向下調整時，把小的交換到父節點。

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

void AdjustDown(int *a,int size,int parent)   //向下對齊
{
	int child = parent * 2 + 1;           //把左孩子的下標給child
	while (child < size)        //保證向下對齊直到child超出范圍
	{
		if (child + 1 < size&&a[child + 1] > a[child])  //當右孩子>左孩子時,child變為右孩子下標
		{
			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);         //從圖中下標為4的非葉子節點開始，進行向下對齊
	}
	for (int i = size - 1; i > 0; i--)
	{
		swap(a[0],a[i]);  //把大堆中的第一個元素和最后一個元素交換，此時最后一個元素大
		AdjustDown(a,i,0);//把剩余的元素建成大堆
	}
}

3、歸并排序

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

歸并排序的時間復雜度O(N*lgN),空間復雜度是O(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;//取中間下標
		_MergeSort(a,tmp,left,mid);       //遞歸進行
		_MergeSort(a, tmp, mid+1, right);  //直到遞歸到左右序列只有一個元素
		Combine(a,tmp,left,mid,mid+1,right);//2個有序序列合并成一個
		memcpy(a+left,tmp,(right-left+1)*sizeof(int));//把有序序列拷給原數組
	}
}
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++];
	}
}

而遞歸排序的非遞歸實現，則采取相反的思路，先把整個數組分成n個序列，每次兩個序列合并。每兩個序列有序后，合4個序列，以此類推。

void MergeSort2(int *a, int size)
{
	assert(a);
	int gap = 0;
	int *temp = new int[size];
	int count = 0;
	//gap指begin1和end1每次的差值 所差次數依次為，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;
	}

}

創新互聯www.cdcxhl.cn，專業提供香港、美國云服務器，動態BGP最優骨干路由自動選擇，持續穩定高效的網絡助力業務部署。公司持有工信部辦法的idc、isp許可證， 機房獨有T級流量清洗系統配攻擊溯源，準確進行流量調度，確保服務器高可用性。佳節活動現已開啟，新人活動云服務器買多久送多久。

分享文章：常用的較優排序之快速排序，堆排序，歸并排序-創新互聯
當前地址：http://www.yijiale78.com/article42/dpcchc.html

成都網站建設公司_創新互聯，為您提供自適應網站、小程序開發、ChatGPT、云服務器、品牌網站制作、軟件開發

廣告

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