遞歸與分治之合并排序和快速排序

合并排序

合并排序的基本思想是：将待排序元素分為大小大緻相同的兩個子集，分别對兩個子集合進行排序，最終将排序好的子集合合并為所要求的排好序的集合。

具體步驟可以通過下列的動圖檢視：（引用自https://blog.csdn.net/li528405176/article/details/86615003）

void merge_sort_recursive(int arr[], int reg[], int start, int end)//僅列舉函數 
{
    if (start >= end)
        return;
    int len = end - start, mid = (len >> 1) + start;
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;
    merge_sort_recursive(arr, reg, start1, end1);
    merge_sort_recursive(arr, reg, start2, end2);
    int k = start;
    while (start1 <= end1 && start2 <= end2)
        reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
    while (start1 <= end1)
        reg[k++] = arr[start1++];
    while (start2 <= end2)
        reg[k++] = arr[start2++];
    for (k = start; k <= end; k++)
        arr[k] = reg[k];
}

void merge_sort(int arr[], const int len) {
    int reg[len];
    merge_sort_recursive(arr, reg, 0, len - 1);
}
           

合并排序的最壞和平均複雜度均為O(nlogn)

快速排序

快速排序是最常用的排序算法。其原理如下：

1.設定一個基準A（一般是以第一個元素為基準），把大于這個基準A的數放在這個基準後，小于這個基準A的數字放在這個基準前；

2.對大于和小于基準A的部分分别使用步驟1，設定新的基準，劃分數組，直到數組中隻有一個元素為止。

這樣說起來有些抽象，我們利用一個例子具體說明排序過程：

我們現在有無序的數組{6，7,5，2,5，8}，第一次循環我們以6為基準。

首先，設定兩個變量i,j記錄位置（位置從0—5），初始時i=1，j=5，如圖：

現在從後往前找第一個小于6的數字，j現在指向8，大于6，j減小，指向5，此時5小于6，如圖：

交換i和j指向的元素位置，7和5交換位置得到結果如下：

現在從前往後找第一個大于6的數字，顯然到7之前沒有比6大的數字，而從後往前找第一個小于6的數字時，找到了2，也就是此時i>j，如圖：

按理說i在前半部分，j在後半部分，但此時i>j了，是以，我們已經确定了，在j處（我們要保證從小到大排列 ，i指向的此時大于6），之前的數字小于6，之後的數字大于6，我們将6置換到j處，得到：

這就是一次快速排序的結果，之後我們分别再對前半部分和後半部分使用快速排序，直到每個數組隻有一個數字的時候，我們的快速排序就完成了。

代碼如下：

void QuickSort(int a[],int start,int last)
{
	int i=start;
	int j=last;
	int temp=a[i];
if(i<j)
{
	while(true)
	{
		while(a[i]<x)
		{
		i++;
		}
		while(a[j]>x)
		{
		j--;
		}	
		if(i>=j) break;
		int m=a[i];
		a[i]=a[j];
		a[j]=m;
	}
	a[i]=a[j];
	a[j]=temp;
	QuickSort(a,start,j-1);
	QuickSort(a,j+1,last);
}	
}
           

快速排序的最壞時間複雜度：O（n^2）,平均時間複雜度為O（nlogn）；