歸并排序 and 快速排序

歸并排序 and 快速排序 （ C 語言實作 ）

歸并排序

含義 ：将将一串混亂數字分成無數個以兩個數字為集合的小塊，此時隻要對兩個元素進行排序即可，再無數個有序小塊合并成一個有序集合，排序的過程就完成了。

将一個大的集合分成無數的小的集合，符合了『 分治法 』中将一個大的問題分成小問題來解決的思想，而對兩個元素進行排序，再将各個小的有序集合合并成一個大的有序集合這個過程就是『 治 』。

算法不僅僅是計算的方法，在探究算法的過程中反映的是我們對世界的認知方法，應當把算法看做事一種思維方式。

歸并排序的起始點，先申請一個和需要排序的資料同等大小的空間來存儲排列好的資料，通過 MSort 方法來切分數組 ，排序結束後釋放臨時數組所配置設定的記憶體。（ 『 歸并排序 』的實作方法有很多，這裡使用的是《 資料結構與算法分析 —— C 語言描述 》中的代碼 ）

void MergeSort(int arry[], int n)
{
	int * tempArry = (int *)malloc(n * sizeof(int));
	if (tempArry != NULL)
	{
		MSort(arry, tempArry, 0, n - 1);
		free(tempArry);
	}
	else
	{
		printf("記憶體空間不足 ！");
	}
}
           

通過遞歸方法，将數組分成 1 個 1 個的 小數組，再通過 Sort 将所有數組合并排序

void MSort(int arry[], int tempArry[], int left, int right)
{
	if (left < right)
	{
		int center = left + (right - left) / 2;// 與直接求平均值無異，此寫法隻為避免 left + right 超出 int 範圍
		MSort(arry, tempArry, left, center);//将數組從中間分開，直到隻剩下1個元素
		MSort(arry, tempArry, center + 1, right);
		Sort(arry, tempArry, left, center + 1, right);
	}
}
           

設定左起始位 left 與右起始位 center 兩兩合并排序，當數組周遊完成則數組排序結束

void Sort(int arry[], int tempArry[], int left, int center, int rightEnd)
{
	int i, leftEnd, numsArry, tempFlag;
	leftEnd = center - 1;
	tempFlag = left;
	numsArry = rightEnd - left + 1;// 元素數量
	while (left <= leftEnd&&center <= rightEnd)
	{
		if (arry[left] <= arry[center])
			tempArry[tempFlag++] = arry[left++];// 執行順序 tempArry[tempFlag] = arry[left]; => tempFlag+=1;left+=1;
		else
			tempArry[tempFlag++] = arry[center++];
	}
	while (left <= leftEnd)//兩個元素時直接放入數組
	{
		tempArry[tempFlag++] = arry[left++];
	}
	while (center <= rightEnd)
	{
		tempArry[tempFlag++] = arry[center++];
	}
	for (i = 0; i < numsArry; i++,rightEnd--)
		arry[rightEnd] = tempArry[rightEnd];
}
           

快速排序

思想：在無序數組中找到分區點 ，左邊都為小于等于分區點的值，右邊都為大于等于分區點的值。将整個數組分成 N 個這樣的數組，當最後分區小于三個元素時說明排序完成。

快速排序的算法好壞很大程度上取決于 『 分區點 』，本文代碼采用的是 『 三數中值分割法 』，即取數組最左端最右端以及數組中間三個數的中間數為分區點，減少采用左右端點碰到極端順序的出現的最壞情況（ 當選取左右端點，碰到資料有序，從大到小或是從小到大的情況 ，算法時間複雜度就會變成最壞時間複雜度）。

将數組分區

當需要排序的數組長度小與 3 時采用插入排序，否則繼續遞歸使用快速排序

void quickSort(int *arry, int left, int right)
{
	int i, j, pivot;
	if (left + 3 <= right)
	{
		i = left; j = right - 1; pivot = median(arry, left, right);
		while (true)
		{
			while (arry[++i] < pivot);
			while (arry[--j] > pivot);
			if (i < j)
				Swap(arry + i, arry + j);
			else
				break;
		}
		Swap(arry+i,arry+right-1);//将分界點放到中間
		quickSort(arry, left, i - 1);
		quickSort(arry, i + 1,right);
	}
	else
	{
		insertSort(arry+left,right-left+1);
	}
}
           

通過 『 三數中值法 』優化分區點

int median(int* arry,int left,int right)
{
	int temp = left+(right-left)/2;
	if (arry[left]>arry[right])
		Swap(arry+left,arry+right);
	if (arry[left]>arry[temp])
		Swap(arry+left,arry+temp);
	if (arry[temp] > arry[right])
		Swap(arry+temp,arry+right);
	Swap(arry+temp,arry+right-1);//将中間值放到右邊第二個數，確定右邊掃描過的數都大于 中間值
	return arry[right - 1];
}
           

采用插入排序而非冒泡排序等，在極端情況下的優化時間複雜度

void Swap(int *num1,int *num2)
{
	int temp = *num1;
	*num1 = *num2;
	*num2 = temp;
}
void insertSort(int *arry,int length)
{
	int i=0, j=0,temp=0;
	for (; i < length - 1; i++)
	{
		temp = arry[i + 1];//temp 為 arry[i] 的下一個數 
		for (j = i; j >= 0;) //按從小到大的順序排序，先從最大的開始比較，将新加入元素放入合适位置
		{
			if (temp < arry[j])
			{
				Swap(arry+j,arry+j+1);// 将較大值放到末尾
				j--;
			}
			else
				break;
		}
	}
}
           

比較分析

遞歸排序和歸并排序都采用了遞歸，将數組分成了 1-2 個元素大小的數組 則遞歸次數為 log n，每次都對整個數組有一個排序的執行 大小為 N ，綜合來看二者的平均時間複雜度都為 O(n * log n )，但從最壞情況來看，當快速排序的分區點每次都是最大或最小值時分區點就要繼續選擇，最後最小集合還有一個插入排序的過程，即為 O(n^ 2) ，而歸并排序無論最好最壞執行的步驟一緻，是以複雜度還是 O(n * log n )。通常我們會選擇合适的分區點來優化快速排序遭遇最壞情況的可能性，例如 ：三數中值分割法

從原地排序分類的角度來看 ：歸并排序在合并的時候可能會改變資料的原始順序，是以并不是原地排序算法。而快速排序法沒有開辟額的記憶體空間隻是交換大小位置，可以做到不對資料做多餘操作是以是一種原地排序算法。

綜合考慮 ：

歸并排序并不是原地排序算法，且在排序過程中要配置設定額外的記憶體空間，是以在實際應用中較少使用。

快速排序法可以通過分區點的優化來降低算法的複雜度，且不用開辟多餘的記憶體空間，在實際中應用的更為廣泛。