国产 无码 综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

  1. Toy模板網(wǎng)首頁
  2. >Toy博客

【數(shù)據(jù)結(jié)構(gòu)】排序合集(萬字詳解)

2年前作者：Dio夾心小面包分類：Toy博客閱讀(20)違法舉報

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

前言

排序，以字面意思來說就是通過特定的算法將一組或多組無序或者接近有序的數(shù)據(jù)，以升序或者降序的方式重新進行排序組合；

[7,4,2,9,8,6,5,1,3];

以升序的方式進行排序最終為:

[1,2,3,4,5,6,7,8,9];

排序算法就是如何使得數(shù)據(jù)按照要求排列的方法；
排序的算法多種多樣，基本的排序算法共有八種，分別為：

冒泡排序 選擇排序 插入排序 希爾排序 歸并排序 快速排序 堆排序 計數(shù)排序

插入排序

插入排序作為排序中較為簡單和經(jīng)典的排序，插入排序的思維可以看作為一個打牌中摸牌順牌的階段一樣；
假設(shè)手里的牌都是順序的，摸下一張牌與之前的牌一張一張進行比較，設(shè)這張牌為n，將n與之前順序的牌進行比較，當遇到比它小的牌的時候即將該牌放到此處；
【數(shù)據(jù)結(jié)構(gòu)】排序合集(萬字詳解),數(shù)據(jù)結(jié)構(gòu),算法,數(shù)據(jù)結(jié)構(gòu),排序算法,算法

設(shè)[0,end]區(qū)間為有序，cur為end后的下一個數(shù)據(jù)，將該數(shù)據(jù)進行保存，若是遇到比cur大的數(shù)據(jù)則挪動數(shù)據(jù)，將cur放至比cur小的數(shù)據(jù)之前，若是cur比end位置大則不需要進行上步操作，若是cur比[0,end]區(qū)間內(nèi)的任意數(shù)據(jù)都小，那就挪動數(shù)據(jù)，將cur放置0處，同時++end；

【數(shù)據(jù)結(jié)構(gòu)】排序合集(萬字詳解),數(shù)據(jù)結(jié)構(gòu),算法,數(shù)據(jù)結(jié)構(gò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;
	}
}

時間復(fù)雜度：
插入排序的時間復(fù)雜度有兩種情況：

  • 當數(shù)據(jù)為有序的情況下，只需要遍歷n-1次，為最優(yōu)的情況，時間復(fù)雜度為O(N)；
  • 當數(shù)據(jù)為逆序的情況時，為最壞的情況，最需要遍歷1+2+3+4+…+N-1次，時間復(fù)雜度為O(N2)；

空間復(fù)雜度：

  • 插入排序的空間復(fù)雜度為常數(shù)階O(1)；

穩(wěn)定性

  • 穩(wěn)定

希爾排序

希爾排序是在以插入排序為前提下進行的一種優(yōu)化的排序，由于插入排序不太擅長排序逆序的情況，所以一位叫做Donald L. Shell的大佬對該排序進行了改進；
希爾排序又被稱為" 縮小增量排序 "，即在插入排序之前進行預(yù)排序；

設(shè)gap，將間隔為gap的數(shù)據(jù)分為一組，共分為gap組；
gap沒有具體的規(guī)范，但是一般而言gap可以跟數(shù)據(jù)量有關(guān)系；
將每組數(shù)據(jù)利用插入排序的方法進行一次預(yù)排序，當預(yù)排序結(jié)束時，數(shù)據(jù)并沒有完全有序，但是較為接近有序；

【數(shù)據(jù)結(jié)構(gòu)】排序合集(萬字詳解),數(shù)據(jù)結(jié)構(gòu),算法,數(shù)據(jù)結(jié)構(gòu),排序算法,算法
當然，根據(jù)數(shù)據(jù)量的變化，預(yù)排序可以進行不止一次；
再預(yù)排序過后即可進行插入排序；

void ShellSort(int* a, int n)
{	
	/*
	* gap根據(jù)數(shù)據(jù)個數(shù)進行變化
	* 故初始值賦值數(shù)據(jù)個數(shù)
	*/
	int gap = n;

	while(gap>1){
		/*
		* 控制gap使其不停進行變化
		* 當gap為1時則為最后一次排序，也是直接插入排序
		*/
		gap = gap / 3 + 1;
		for (int i = 0; i < n - gap; i++) {//n-gap防止越界
			/*
			* 直接插入排序的思路
			*/
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0) {
				if (a[end] > tmp) {
					a[end + gap] = a[end];
					end-=gap;
				}
				else break;
			}
			a[end + gap] = tmp;
		}
	}
}

時間復(fù)雜度

  • 希爾排序的時間復(fù)雜度為O(N3/2)，相對于直接插入排序的最壞情況O(N2)來說要快一些；

空間復(fù)雜度

  • 希爾排序的空間復(fù)雜度也為O(1);

穩(wěn)定性

  • 不穩(wěn)定

選擇排序

選擇排序的思路為雙指針：
設(shè)begin為0，cur為begin+1，cur遍歷一遍數(shù)據(jù)，找到最小或者最大的那個數(shù)據(jù)并將該位置保存，最后與begin所在的數(shù)據(jù)進行交換;
交換過后begin++；
【數(shù)據(jù)結(jié)構(gòu)】排序合集(萬字詳解),數(shù)據(jù)結(jié)構(gòu),算法,數(shù)據(jù)結(jié)構(gòu),排序算法,算法
為了使排序不那么繁瑣可以使用begin與end兩個指針記錄頭尾，cur指針從前往后分別找到最小和最大的數(shù)據(jù)并保存位置，最小的數(shù)據(jù)與begin交換，最大的數(shù)據(jù)與end進行交換，交換過后++begin與–end從而控制區(qū)間；

void SelectSort(int*a ,int n)
{
	int begin = 0, end = n - 1;
	//[begin,end]左閉右閉區(qū)間
	while (begin < end) {
		int min = begin, max = begin;
		for (int i = begin + 1; i <= end; i++) {
			
			if (a[i] < a[min]) {
				min = i;
			}
			if (a[i] > a[max]) {
				max = i;
			}
		}
		swap(&a[begin], &a[min]);
		if (begin == max) {
			max = min;
		}
		swap(&a[max], &a[end]);
		++begin, --end;
	}
}

時間復(fù)雜度

  • 當數(shù)據(jù)為完全順序的情況下，不需要進行交換，則時間復(fù)雜度為O(N);
  • 若是數(shù)據(jù)為逆序的情況下則為最壞的情況，交換次數(shù)即為O(N-1)次；

空間復(fù)雜度

  • 選擇排序的空間復(fù)雜度為常數(shù)階O(1);

穩(wěn)定性

  • 不穩(wěn)定

堆排序

堆排序是基于堆而做的一種排序,同時堆排序也算是選擇排序中的一種排序;
既然是基于堆的排序,首先數(shù)據(jù)必須為一個堆(升序建大堆,降序建小堆),而所給的每組數(shù)據(jù)中是堆的可能性并不大;
所以再進行排序之前應(yīng)該先進行建堆,建堆的同時分為向上調(diào)整建堆與向下調(diào)整建堆;

堆排的思路為將頭尾數(shù)據(jù)進行交換再進行向下調(diào)整,故向下調(diào)整是必須具有的一個,同時基于向下調(diào)整建堆的時間復(fù)雜度(O(N))優(yōu)于向上調(diào)整建堆(O(N*logN)),故在這里只需要寫一個向下調(diào)整算法就能實現(xiàn)堆排序;

【數(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),算法,數(shù)據(jù)結(jié)構(gòu),排序算法,算法

void AdjustDown(int*a,int parent,int n)//parent==0 n == 6
{
	int child = parent * 2 + 1;//1
	while(child<n) {//child<6
		if (child + 1<n&& a[child + 1] > a[child]) {
			child++;
		}
		if (a[child] > a[parent]) {
			swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else break;
	}
}
void HeatSort(int* a, int n)//n==7
{
	/*建堆*/
	
	for (int i = (n-2)/2; i >= 0; i--) {
		AdjustDown(a, i, n);
	}

	int end = n - 1;
	while (end>0) {
		swap(&a[0], &a[end]); //交換頭尾
		AdjustDown(a, 0,end);//傳值傳的是個數(shù)
		end--;
	}
}

時間復(fù)雜度

  • 堆排是在堆中進行選書,相對傳統(tǒng)的選擇排序來說效率快了很多,時間復(fù)雜度為O(N*logN);

空間復(fù)雜度

  • 堆排的空間復(fù)雜度為常數(shù)階O(1);

穩(wěn)定性

  • 不穩(wěn)定

快速排序

快速排序是一個相對來說應(yīng)用最廣泛的一種排序算法,它一開始為一名英國計算機科學(xué)家霍爾于1960年所發(fā)明;
流行的原因是這個排序算法實現(xiàn)簡單,且適用于不同的數(shù)據(jù),同時相對于排序算法中的其他算法要快得多;
快速排序的基本思想為一種左右分治的思想,就如二叉樹相同,將問題分為兩個子問題進行解決;

基本思想為:

任取待排元素序列中的其中一個元素作為key值基準值;
按照待排序的區(qū)間分為兩個序列,key值左邊的數(shù)據(jù)均小于key,key值右邊的數(shù)據(jù)均大于key;
再進行不斷分治,最終將對應(yīng)順序的數(shù)據(jù)排列再相應(yīng)位置即結(jié)束;

hoare原生版本

這個版本的也是最初的版本
其單次排序的思想即為:

選取數(shù)據(jù)中最左邊的數(shù)據(jù)作為基準值key,保存該數(shù)據(jù)的下標keyi方便數(shù)據(jù)與key進行比較;
設(shè)左右兩個指針left與right,left為keyi+1,right為最后一個數(shù)據(jù)的下標;
left從前往后遍歷,right從后往前進行遍歷,left找比key大的數(shù)據(jù),right找比eky小的數(shù)據(jù);
當left找到相應(yīng)的數(shù)據(jù)同時right也找到相應(yīng)的數(shù)據(jù)時,將兩個數(shù)據(jù)進行交換;
交換過后再繼續(xù)遍歷;
當left與right相遇時,則停止遍歷,同時將相遇位置的值與key進行交換;
同時,在遍歷時若是需要左右指針都在中間位置停止,那必須保證key在左邊時右指針先往前遍歷,key若是在最右邊選數(shù)則需要左邊指針先進行遍歷

【數(shù)據(jù)結(jié)構(gòu)】排序合集(萬字詳解),數(shù)據(jù)結(jié)構(gòu),算法,數(shù)據(jù)結(jié)構(gòu),排序算法,算法

[單次排序示意圖] 
//單次排序
int PartSort(int* a, int left, int right)
{
	int keyi = left;
	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;
}

當?shù)谝淮闻判蜻^后,將要以前序遍歷的方式進行分治;
區(qū)間將會以[begin,keyi-1]keyi[keyi+1,end]進行劃分;
根據(jù)該思維進行遞歸;

void QuitSort(int* a, int begin, int end)
{
	if (begin>=end) {
		return;
	} 
	int kiey = PartSort(a, begin, end);
	QuitSort(a, begin, kiey-1);
	QuitSort(a, kiey+1, end);
}
遞歸的結(jié)束條件即為該組數(shù)據(jù)中只存在一個數(shù)或是該段區(qū)間不存在;

挖坑法

挖坑法的思路與hoare原生版本的思路大體相同:

思路即為在開始前記住最左邊的基準值key的值并將其保存,左右指針同時往中間進行遍歷
左邊找比基準值key大的值,右邊找小的值,與hoare相同,key在左邊時右指針先進行遍歷;
當最左邊key值被保存之后,key所在的位置即形成一個坑;
當右指針找到相應(yīng)的值時則將右指針的值給給這個坑,此時left所在的位置,也就是key的位置的坑被填;
同時right指針所在的位置又新生成一個坑,left指針再從后往前遍歷找到對應(yīng)位置進行填補,如此反復(fù);
當兩個指針相遇或者相交時,所在的位置必定是一個坑,此時再把key值填入次坑;

【數(shù)據(jù)結(jié)構(gòu)】排序合集(萬字詳解),數(shù)據(jù)結(jié)構(gòu),算法,數(shù)據(jù)結(jié)構(gòu),排序算法,算法

[單次排序示意圖] 
//單次排序
int PartSort(int* a, int left, int right)
{
	
	int key = a[left];
	int hole = left;
	while (left < right) {
		while (left < right&&a[right] >= key)
			right--;

		a[hole] = a[right];
		hole = right;

		while (left < right&&a[left ] <= key)
			left++;
		a[hole] = a[left];
		hole = left;
	}
	a[hole] = key;
	return hole;
}

其遞歸的思路都一致;

前后指針法

前后指針,顧名思義即為前后兩個指針進行遍歷;
其思路為:

設(shè)指針keyi,指針prev與指針cur,用cur指針進行遍歷,當cur所在位置小于基準值key值時,
prev指針先++,而后將cur指針所在的數(shù)據(jù)與prev所在的數(shù)據(jù)進行交換;
當cur大于right時,則停止遍歷,將此時prev所在位置的值與key值進行交換;
此時key值左邊的數(shù)小于key,右邊則大于key;

【數(shù)據(jù)結(jié)構(gòu)】排序合集(萬字詳解),數(shù)據(jù)結(jié)構(gòu),算法,數(shù)據(jù)結(jié)構(gòu),排序算法,算法

[單次排序示意圖] 
//單趟排序
int PartSort(int* a, int left, int right)
{

	int keyi = left;
	int prev = left;
	int cur = left + 1;

	while (cur<=right) {
		
		if (a[cur] < a[keyi]) {
			prev++;
			swap(&a[prev], &a[cur]);
		}
		cur++;
	}
	swap(&a[prev], &a[keyi]);
	return prev;
}

該方法的遞歸思路與上面兩種方式相當;

三數(shù)取中優(yōu)化

快速排序,是基于在綜合性能以及綜合使用場景情況下速度較快,效率較高才之所以叫做快速排序;
當然在一定情況下,快速排序依舊有短板;

在一般情況下,綜合來說,快速排序的時間復(fù)雜度為O(N*logN),而不排除一些極端的情況;
即數(shù)據(jù)本身就為有序的情況;

在這個情況下,由于上述選基準值key值的方式都是為數(shù)據(jù)中最左邊或者最右邊的數(shù)據(jù),而若是數(shù)據(jù)本身有序的情況;
快速排序的時間復(fù)雜度將會為O(N2);

【數(shù)據(jù)結(jié)構(gòu)】排序合集(萬字詳解),數(shù)據(jù)結(jié)構(gòu),算法,數(shù)據(jù)結(jié)構(gòu),排序算法,算法

由于key值每次都為最小值,導(dǎo)致快速排序遍歷速度更慢,最終時間復(fù)雜度將會為O(N2);

【數(shù)據(jù)結(jié)構(gòu)】排序合集(萬字詳解),數(shù)據(jù)結(jié)構(gòu),算法,數(shù)據(jù)結(jié)構(gòu),排序算法,算法

針對該種情況,有人設(shè)計了一種情況,即為將key值取頭尾中間三個數(shù)據(jù)中,既不是最大也不是最小的值;

int GetMidIndex(int* a, int left, int right) {
	int mid = (left + right) / 2;
	if (a[mid] > a[left]) {
		if (a[right] > a[mid]) {
			return mid;
		}
		else if (a[left] > a[right]) {
			return left;
		}
		else return right;
	}
	else // a[left]>a[mid]
	{
		if (a[right] > a[left]) {
			return left;
		}
		else if (a[mid] > a[right]) {
			return mid;
		}
		else return right;
	}
}

當每次單趟排序時,設(shè)置一個指針mid指向中間位置,將該中間值與最左以及最右進行三數(shù)取中并返回下標;
再將它與key值進行交換;

//使用hoare原生版本的單趟排序作為演示
int PartSort(int* a, int left, int right)
{
	int mid = GetMidIndex(a,left,right);
	swap(&a[left], &a[mid]);
	int keyi = left;
	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;
}

該方法的優(yōu)化解決了快速排序中遇到的有序情況;

隨機數(shù)取key優(yōu)化

由于三數(shù)取中是能解決一部分辦法,但是并沒有完全解決,有些題目的測試用例對于專門三數(shù)取中的優(yōu)化還是并不能完全解決;
因此在此基礎(chǔ)上有出現(xiàn)了一個為隨機數(shù)取key的優(yōu)化;
即為將數(shù)據(jù)中[left,right]這段區(qū)間中隨機選一個數(shù)做key;

//使用hoare原生版本的單趟排序作為演示
int PartSort(int* a, int left, int right)
{
	int randi = left+rand()%(right-left);//在使用rand函數(shù)前需先調(diào)用srand函數(shù)
	swap(&a[left], &a[randi]);
	int keyi = left;
	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;
}

三路劃分版

三路劃分版本的快速排序針對一些重復(fù)率較高的情況:

[2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,]

若是遇到該種情況,三數(shù)取中與隨機數(shù)取key的方法將會再次失效,時間復(fù)雜度也會再度來到 O(N2)的極端情況;
則在該種情況下,又有人想出了一種對應(yīng)的方法,這個方法即為三路劃分法;
該方法的思想為:

將原本的[left,keyi-1]keyi[keyi+1,right]區(qū)間;
劃分為[<key][==key][>key]三個區(qū)間;

【數(shù)據(jù)結(jié)構(gòu)】排序合集(萬字詳解),數(shù)據(jù)結(jié)構(gòu),算法,數(shù)據(jù)結(jié)構(gòu),排序算法,算法
思路為:

使用三數(shù)取中的方式選取一個適和的數(shù)據(jù)作為key值并將key值進行保存(保存的為數(shù)據(jù)不為下標),
設(shè)指針cur指向left所指數(shù)據(jù)的后一個位置,即cur = left+1;
當cur指針不大于最右邊界的情況進行循環(huán)遍歷;
當cur所指向的數(shù)據(jù)小于key值時,則交換left指向的數(shù)據(jù)與cur指向的數(shù)據(jù),并將兩個指針都向后走一步;
當cur所指向的數(shù)據(jù)等于key值時,則不進行交換,cur繼續(xù)遍歷;
當cur指向的數(shù)據(jù)大于key值時,將cur所指向的數(shù)據(jù)與right所指向的數(shù)據(jù)進行交換,同時right–;
此時cur指針保存不懂避免交換過后cur所指向的數(shù)據(jù)小于key值;

void QuitSort(int* a, int begin, int end) 
{
	if (begin >= end) {
		return;
	}
	int left = begin;
	int right = end;
	int mid = GetMidIndex(a, left, right);
	swap(&a[mid], &a[left]);
	int key = a[left];
	int cur = left+1;


	while (cur <= right) {

	    if (a[cur] < key) {
		swap(&a[left], &a[cur]);
		cur++, left++;
	}
		else if (a[cur] > key) {
			swap(&a[right], &a[cur]);
			right--;
		}
		
		else {
			cur++;
		}
	}
	QuitSort(a,begin, left - 1);
	QuitSort(a, right+1, end);
}

非遞歸

快速排序除了遞歸以外同時也存在非遞歸的寫法,
非遞歸的快速排序依靠為棧或者隊列;
基本思想為:
將每次需要處理的區(qū)間進行入棧(注意棧的順序為LIFO),
出棧后將出棧的區(qū)間進行處理(處理采用單趟排序處理);
當棧不為空的時候說明棧內(nèi)仍存在區(qū)間需要進行出棧并處理,反復(fù)直到區(qū)間不存在或是區(qū)間內(nèi)只有一個數(shù)時則不進行處理;
【數(shù)據(jù)結(jié)構(gòu)】排序合集(萬字詳解),數(shù)據(jù)結(jié)構(gòu),算法,數(shù)據(jù)結(jié)構(gòu),排序算法,算法
以改圖為例,按照順序先進[6,0];
再出棧[0,6]并將這段區(qū)間進行處理;
處理過后返回keyi,即區(qū)間又可以劃分為[left,keyi-1]keyi[keyi+1,right];
如此循環(huán);

void QuiteSortNonR(int* a, int begin, int end) {
	ST st;
	InitStack(&st);
	/*
	*第一次入棧整段區(qū)間
	*并在循環(huán)中進行處理(循環(huán)將會返回keyi值)
	*/
	StackPush(&st, end);
	StackPush(&st, begin);

	while (!StackEmpty(&st)) {
		int left = StackTop(&st);
		StackPop(&st);
		int right = StackTop(&st);
		StackPop(&st);
		int key = PartSort(a, left, right);
		if (key + 1 < right) {
			StackPush(&st,right);
			StackPush(&st, key+1);
		}
		if (key - 1 > left) {
			StackPush(&st, key - 1);
			StackPush(&st, left);
		}
	}
	Destruc(&st);//銷毀棧
}

穩(wěn)定性

  • 綜合上述來說,快速排序并不是一個十分穩(wěn)定的排序,它在綜合情況以及使用場景之中,總體效率都比較不錯
    但是若是遇到比較極端的情況下卻不能很好解決,如有序的情況,有序的情況下一些排序?qū)Ｖ古判?而快速排序若是在這種
    情況下用三數(shù)取中的方式進行處理,仍會有一定的開銷;
    故快速排序不穩(wěn)定;

歸并排序

歸并排序,是一種基于歸并操作的排序算法,該算法與快速排序算法一樣采用了分治法的排序;
基本思想為:
將兩個已經(jīng)有序的子序列進行合并,得到一個完全有序的序列;
要使兩個子序列有序,一樣要將子序列中的子序列變得有序;將問題化為子問題;
【數(shù)據(jù)結(jié)構(gòu)】排序合集(萬字詳解),數(shù)據(jù)結(jié)構(gòu),算法,數(shù)據(jù)結(jié)構(gòu),排序算法,算法

分治思路示意圖

遞歸

遞歸的思路即為上述思路,
相應(yīng)的思路可以參考二叉樹中的后序遍歷;
具體步驟為:

開出一塊與數(shù)據(jù)內(nèi)容相應(yīng)大小的空間temp,這塊空間用來進行每兩組之間的歸并;
以上圖為參考,因為每個子區(qū)間中的數(shù)據(jù)不一定都是有序的;
所以要使用后序遍歷的思路,最終將數(shù)據(jù)分為單個數(shù)據(jù)(單個數(shù)據(jù)可以看作有序);
使用歸并的思路將數(shù)據(jù)歸并至temp中;
最終再每次遞歸結(jié)束時將數(shù)據(jù)拷貝回原數(shù)組;

//遞歸
void _MergeSort(int* a, int begin, int end, int* tmp) 
{
	if (begin == end) {
		return;
	}
	int mid = (begin + end) / 2;
	/*
	*這里分出來的區(qū)間為[begin,mid][mid+1,end]
	*走后續(xù)，因為要左右區(qū)間都為有序才能進行歸并
	*/
	_MergeSort(a, begin, mid, tmp);
	_MergeSort(a, mid + 1, end, tmp);

	//與快排不同,快排的區(qū)間可以看作為三塊
	//而歸并排序只需要分為左右兩塊進行歸并即可
	int left1 = begin, right1 = mid;
	int left2 = mid + 1, right2 = end;
	int i = begin;

	//使用歸并的思路將數(shù)據(jù)依次放至tmp數(shù)組中
	while (left1 <= right1 && left2 <= right2) {
		if (a[left1] < a[left2]) {
			tmp[i++] = a[left1++];
		}
		else//a[left1]>=a[left2]
			tmp[i++] = a[left2++];
	}
	//但凡兩個其中一個結(jié)束
	//將剩余數(shù)據(jù)依次拷貝至tmp數(shù)組
	while (left1 <= right1) {
		tmp[i++] = a[left1++];
	}
	
	while (left2 <= right2) {
		tmp[i++] = a[left2++];
	}

	memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));//拷貝回原數(shù)組

}

在看過這段代碼過后就會發(fā)現(xiàn),其實歸并排序的遞歸需要用到兩個函數(shù);
其中一個函數(shù)用來作子函數(shù)從而達到遞歸的效果;
主函數(shù)用來開辟空間并釋放空間;

void MergeSort(int* a, int n/*數(shù)據(jù)個數(shù)*/)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL) {
		perror("MergeSort::malloc fail");
		exit(-1);
	}
	_MergeSort(a, 0, n - 1, tmp);
	free(tmp);
}

非遞歸

相比于遞歸不同,非遞歸比遞歸所需要在意的細節(jié)更多;
但是思路上大體相同;
與快排不同,歸并排序的非遞歸并不需要用到?；蛘哧犃?
歸并排序的非遞歸大致的思路為:

設(shè)一個gap為間距值,gap一開始為1,且gap在每次歸并過一次時*=2;
當gap為1時實現(xiàn)一一歸并,
當gap為2時實現(xiàn)兩兩歸并,以此類推;

void MergeSortNonR(int* a, int n/*數(shù)據(jù)個數(shù)*/)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL) {
		perror("MergeSort::malloc fail");
		exit(-1);
	}
	int gap = 1;
	//1  2  4  8
	while (gap < n) {
		for (int j = 0;j<n; j += 2 * gap) {
			int left1 = j, right1 = j + gap - 1;
			int left2 = j + gap, right2 = j + 2 * gap - 1;
			int i = j;
			

			while (left1 <= right1 && left2 <= right2) {

				if (a[left1] < a[left2]) {
					tmp[i++] = a[left1++];
				}

				else//a[left1]>=a[left2]

					tmp[i++] = a[left2++];

			}//單反兩個其中一個結(jié)束

			while (left1 <= right1) {
				tmp[i++] = a[left1++];
			}

			while (left2 <= right2) {
				tmp[i++] = a[left2++];
			}
		}
		memcpy(a , tmp , sizeof(int) * n);
		gap *= 2;
	}
	free(tmp);

}

該段代碼可以完美實現(xiàn)上圖中所對應(yīng)的數(shù)據(jù)所給的排序;
但是這個方法的缺陷特別明顯;

缺陷:

  1. 當數(shù)據(jù)量不為2n時,將會有越界風(fēng)險,即gap是一個不是很好控制的因素所以相應(yīng)的需要進行邊界的修正;
  2. 當數(shù)據(jù)在拷貝時,由于在控制邊界之后,有些數(shù)據(jù)不能直接轉(zhuǎn)入temp空間,導(dǎo)致空間中存在隨機值,若是盲目拷貝整塊空間將會出現(xiàn)隨機數(shù)覆蓋原有效數(shù)組的風(fēng)險;

根據(jù)相應(yīng)的缺陷需要制定出有效的措施;

調(diào)整邊界

既然gap不能很好的控制調(diào)整,那就在遍歷的過程中調(diào)整邊界以達到不會越界;
從上述情況種可以了解到在非遞歸種共有四個指針,分別為left1,right1,left2與right2;
而非遞歸中越界的情況分為3種;

right1,left2與right2都越界

【數(shù)據(jù)結(jié)構(gòu)】排序合集(萬字詳解),數(shù)據(jù)結(jié)構(gòu),算法,數(shù)據(jù)結(jié)構(gòu),排序算法,算法

left2與right2越界

【數(shù)據(jù)結(jié)構(gòu)】排序合集(萬字詳解),數(shù)據(jù)結(jié)構(gòu),算法,數(shù)據(jù)結(jié)構(gòu),排序算法,算法

right2越界

【數(shù)據(jù)結(jié)構(gòu)】排序合集(萬字詳解),數(shù)據(jù)結(jié)構(gòu),算法,數(shù)據(jù)結(jié)構(gòu),排序算法,算法
相應(yīng)的解法即為修改邊界,當right1或者left2越界時,
即表示該段區(qū)間后的數(shù)據(jù)不需要進行歸并,若是歸并則會越界;
當right2越界時,則將right2的邊界改為n-1;

void MergeSortNonR(int* a, int n/*數(shù)據(jù)個數(shù)*/)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL) {
		perror("MergeSort::malloc fail");
		exit(-1);
	}
	int gap = 1;
	//1  2  4  8
	while (gap < n) {
		for (int j = 0;j<n; j += 2 * gap) {
			int left1 = j, right1 = j + gap - 1;
			int left2 = j + gap, right2 = j + 2 * gap - 1;
			int i = j;
			
			//right1 left2 right2 全部越界
			//left2 right2 越界
			//right2
			
			//修正前
			if (right1 >= n || left2 >= n){
				break;
			}

			if (right2 >= n) {
				right2 = n - 1;
			}

			//修正后

			while (left1 <= right1 && left2 <= right2) {

				if (a[left1] < a[left2]) {
					tmp[i++] = a[left1++];
				}

				else//a[left1]>=a[left2]

					tmp[i++] = a[left2++];

			}//兩個其中一個結(jié)束

			while (left1 <= right1) {
				tmp[i++] = a[left1++];
			}

			while (left2 <= right2) {
				tmp[i++] = a[left2++];
			}
		}
		memcpy(a, tmp, sizeof(int)n);
		gap *= 2;
	}
	free(tmp);
單次歸并單次拷貝

第二個缺點的解決方法即為,每次歸并結(jié)束后,都將這段歸并的數(shù)據(jù)拷貝回原數(shù)組,歸并一段拷貝一段;
即不會出現(xiàn)隨機數(shù)覆蓋原有效數(shù)據(jù)的問題;

最終代碼:

void MergeSortNonR(int* a, int n/*數(shù)據(jù)個數(shù)*/)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL) {
		perror("MergeSort::malloc fail");
		exit(-1);
	}
	int gap = 1;
	//1  2  4  8
	while (gap < n) {
		for (int j = 0;j<n; j += 2 * gap) {
			int left1 = j, right1 = j + gap - 1;
			int left2 = j + gap, right2 = j + 2 * gap - 1;
			int i = j;
			
			//right1 left2 right2 全部越界
			//left2 right2 越界
			//right2
		

			if (right1 >= n || left2 >= n){
				break;
			}

			if (right2 >= n) {
				right2 = n - 1;
			}


			while (left1 <= right1 && left2 <= right2) {

				if (a[left1] < a[left2]) {
					tmp[i++] = a[left1++];
				}

				else//a[left1]>=a[left2]

					tmp[i++] = a[left2++];

			}

			while (left1 <= right1) {
				tmp[i++] = a[left1++];
			}

			while (left2 <= right2) {
				tmp[i++] = a[left2++];
			}

			memcpy(a + j, tmp + j, sizeof(int) * (right2 - j + 1));
			//     0        0                     1      2
			//     1        1                      3     
		}
		gap *= 2;
	}
	free(tmp);

}

時間復(fù)雜度

  • 歸并排序的時間復(fù)雜度為O(N*logN),但是以綜合性能的話,略遜快排一點,但無傷大雅;

空間復(fù)雜度

  • 歸并排序的缺點之一即為空間復(fù)雜度,在歸并的過程中的開銷并不多,但由于歸并排序需要
    開一段大小為N的空間,故空間復(fù)雜度為O(N);

穩(wěn)定性

  • 穩(wěn)定

總結(jié)

排序算是一種較為基本的且需要掌握的算法,優(yōu)秀的排序算法能在程序中使得效率倍式的提升;
不同的排序算法可以根據(jù)不同的使用場景分別進行使用;
排序中較為難的點為一些排序算法中的邊界問題,以及遞歸中分治思路的理解;

在類似快速排序樣式的排序中依舊可以再進行小區(qū)間優(yōu)化,
即在遞歸到一定數(shù)據(jù)量時使用穩(wěn)定的且效率還行的非復(fù)雜排序?qū)?shù)據(jù)進行排序;
小區(qū)間優(yōu)化的目的是為了減少排序過程中遞歸調(diào)用的次數(shù)從而達成效率的優(yōu)化;
文章來源地址http://www.zghlxwxcb.cn/news/detail-721522.html

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

本文來自互聯(lián)網(wǎng)用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務(wù)，不擁有所有權(quán)，不承擔相關(guān)法律責(zé)任。如若轉(zhuǎn)載，請注明出處： 如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實不符，請點擊違法舉報進行投訴反饋，一經(jīng)查實，立即刪除！

領(lǐng)支付寶紅包贊助服務(wù)器費用

相關(guān)文章

覺得文章有用就打賞一下文章作者

支付寶掃一掃打賞

博客贊助

微信掃一掃打賞

請作者喝杯咖啡吧~博客贊助

支付寶掃一掃領(lǐng)取紅包，優(yōu)惠每天領(lǐng)

二維碼1

領(lǐng)取紅包

二維碼2

領(lǐng)紅包