前言

排序是啥？哪個排序最優？
排序：所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作，

一、冒泡排序

大家應該最早接觸的排序就是冒泡排序，以升序為例，每一趟的冒泡排序都是把一個最大的數放到最后面，其中 a[i-1]>a[i],我們將i-1,i的值進行交換，
基本思想：所謂交換，就是根據序列中兩個記錄鍵值的比較結果來對換這兩個記錄在序列中的位置，交換排序的特點是：將鍵值較大的記錄向序列的尾部移動，鍵值較小的記錄向序列的前部移動，

觀察上面動圖，總結規律，我們可以發現一次冒泡排序兩兩交換之后可以把一個最大的數冒到最后面，那么我們要進行多少次冒泡排序才能將一組資料排好呢：n-1次，因為我們排到n-1的時候，最后一個資料也已經在他該在的位置啦！！
難點：這里的n是元素和，最后一個元素的下標是n-1

void BubbleSort(int* a, int n)
{
	//冒泡排序，升序為例	
	int end = n - 2 ;
	//end == n-2的時候是排好n-1位置的值，我們要排好最后排好下標為1的值，則0位置自然就是最小的
	while (end >= 0)
	{
//n個數一次冒泡將一個數冒到最后，則需要n-1次
		int i = 0;
//當一次排序一個數都沒交換即已經有序，跳出回圈

		int flag = 0;
		while (i <= end)
		{
			//一次排序
			if (a[i] > a[i + 1])
			{
				Swap(&a[i], &a[i + 1]);
				flag = 1;
			}
			i++;
		}
		if (flag == 0)
			break;

		end--;
	}
}

1.復雜度，穩定性分析

冒泡排序的空間復雜度O（1），時間復雜度是O(N^2),但是在加入裁剪之后的冒泡排序在接近有序的時候效率是可以達到O（N），并且兩兩交換的特性保證兩個相同的值無論如何排序，都是保持順序的，所以冒泡排序是穩定的，

二、插入排序

大家都玩過撲克牌吧，我們在整理牌的時候就可以以一個牌為中心，讓后面比他大的牌往他的前面放，反之，

觀察上圖，總結規律，插入排序的思想就是在已經有序的一段區間中一次插入一個值，所以第一次我們以下標為0的資料可以當成一個有序區間，將下標為1的數往有序區間插入，同理后面n-1張牌都是這樣處理，

void InsertSort(int* a, int n)
{
	//排升序
	for (int i = 0; i <= n - 2; i++) {
		//這里的end范圍[0,n-2]，陣列倒數第二個元素
		int end = i ;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			//當前end的值比tmp小都要往后移動
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
			}
			else
			{
				break;
			}
			--end;
		}
		//兩種情況出來的都可以在end后面這個位置放
		a[end + 1] = tmp;
	}
}

2.復雜度，穩定性分析

插入排序對比冒泡排序，他的時間復雜度也是O（N^2）,在接近有序的情況下他的時間復雜度是O（N），因為遍歷一遍就可以出結果了，空間復雜度O（1），這種排序也是穩定的，因為我們可以將相同的值放在后面，就能保證穩定了！

三、選擇排序

觀察上面的選擇排序，總結規律：在遍歷排好位置后面的數值時，選擇后面當中最小的，與當前索引的值進行交換，但是我們在這里可以進行一次優化，我們可以從遍歷一次拿到最大值和最小值，最小值往前放，最大值往后面放，再將我們的區間縮小即可，

void SelectSort(int* a, int n)
{
	//我們這里實作的選擇排序優化，一次選擇最大和最小的


	//排升序
	int begini = 0 , endi = n-1 ;
	//一次
	while(begini<endi){
	//這里尋找最大和最小下標的索引
	int maxi = begini, mini = begini;
	for (int i = begini; i <= endi; ++i)
	{
		//我們這里找出最大和最小的索引
		if (a[maxi] < a[i])
		{
			maxi = i;
		}
		if (a[mini] > a[i])
		{
			mini = i;
		}
	}
	Swap(&a[begini], &a[mini]);
	//1.mini與maxi相等說明是一個等值數列
	//2.考慮begini會不會和maxi相等，相等就出事

	//當maxi和begini是同一個位置的時候
	//這里是因為bigini是先交換的，要考慮會不會影響到后面maxi，endi交換也會有這個問題
	//即使極端情況 begini = maxi，endi = mini，也可以這樣解決，最后endi就和自己交換了一下而已
	if (begini == maxi)
	{
		maxi = mini;
	}
	Swap(&a[endi], &a[maxi]);
	--endi;
	++begini;
}
}

3.復雜度，穩定性分析

選擇排序的時間復雜度是O（N^2）,在接近有序的時候也是O（N ^ 2）,因為我們每次都要從剩下的牌中在進行挑選，N N-2 N-3 … 1,所以它是一個比較不實用排序了，并且他是一種不穩定的排序，我們遍歷一遍的時候 a[]={1 1 1 2 1 1 1 };這個陣列當中把2和最后一個位置的1交換時，對于2后面的兩個1，他們的相對順序發生了改變，

四、希爾排序（ 縮小增量排序）

希爾排序(Shell’s Sort)是插入排序的一種又稱“縮小增量排序”(Diminishing Increment Sort),是直接插入排序演算法的一種更高效的改進版本，引自百度，
所以我們可以看出這個排序跟插入排序是強相關的，
基本思想是：先選定一個整數，把待排序檔案中所有記錄分成個組，所有距離為的記錄分在同一組內，并對每一組內的記錄進行排序，然后，取，重復上述分組和排序的作業，當到達gap=1時，所有記錄在統一組內排好序，

希爾排序就是在處理一些極端情況比較高效，比如在上面的插入排序時如果我們在原陣列降序的情況下去排升序，那么我們交換的次數是十分多的，也可以說是插入排序的最壞的情況，這個時候聰明的先輩想到了希爾排序，將陣列分成了gap組，然后可以理解為分別處理每一個小組，gap從5 – 2 – 1的程序在降序的情況下，排在后面的數值小的數能步子更大排到前面，當gap為1的時候實際上就是進行了一次插入排序，設定gap的程序我們也稱之為預排序

void ShellSort(int* a, int n)
{
	
	gap為3,排升序
	//int gap = n;
	//while (gap > 1) {
	//	//這個是總結的經驗
	//	gap = gap / 3 + 1;
	//	//end的范圍是[0,n-gap)
	//	//只要保證每組都是前面先排就可以，
	//	//所以用這種寫法比較簡單，但時間復雜度跟套兩層回圈一樣

	//	for (int i = 0; i < n - gap; ++i) {
	//		int end = i;
	//		int tmp = a[end + gap];
	//		while (end >= 0)
	//		{
	//			//當前的end的值比tmp大就要往end+gap位置挪
	//			//所以要提前保存end+gap的值
	//			if (a[end] > tmp)
	//			{
	//				a[end + gap] = a[end];
	//				end -= gap;
	//			}
	//			else
	//			{
	//				break;
	//			}
	//			a[end + gap] = tmp;
	//		}
	//	}
	//}
		//gap為3,排升序
	int gap = n;
	while (gap > 1) {
		//這個是總結的經驗
		gap = gap / 3 + 1;
		//end的范圍是[0,n-gap)

		//也可以先排第一組再排gap組
		//實際上都一樣，時間復雜度一致的
		for (int j = 0; j < gap; j++) {
			for (int i = j; i < n - gap; i += gap) {
				int end = i;
				int tmp = a[end + gap];
				while (end >= 0)
				{
					//當前的end的值比tmp大就要往end+gap位置挪
					//所以要提前保存end+gap的值
					if (a[end] > tmp)
					{
						a[end + gap] = a[end];
						end -= gap;
					}
					else
					{
						break;
					}
					a[end + gap] = tmp;
				}
			}
		}
	}
}

4.復雜度，穩定性分析

希爾排序的時間復雜度是O(N^1.3),這個是由科學家們弄出來的數字，我個人覺得每一次當gap是以gap/3+1的步驟走，其實while大回圈它會走logN(3為底)次回圈，每一個回圈里面每次接近是遍歷一次陣列O(N)，總的時間復雜度就是O(logN(3為底)*N)，可以看出這已經算是一種非常厲害的排序了，這個排序是不穩定的，gap將一個組分為若干組進行排序之后出現兩個相同值的順序不同其實也是很正常的，

五、快排

快排的單趟排序有很多個版本，這里說幾個比較有名的，最早的是hoare版本的，也就是創始人，后面的挖坑法相對比較好理解，還有前后指標法（很多種叫法，這里我們先稱作前后指標）

1.1. hoare版本

hoare版本，就是先確定一個key，我們假設key取左邊的值，我們就要先從右邊找到比key小的值，再從左邊找一個比key大的值，進行交換，知道左右區間為0時結束，就排好一個key這個數的位置了，

int PartSort1(int* a, int left, int right)
{
//采用前后指標法,將key先設定為左邊的值
//一開始先讓右邊找小，左邊找大，然后交換
//最后相遇的位置一定是比key對應的值小，交換就把key的值放在正確的索引了
	//注意這里磁區間，key是left，不是0！！！
	int midi = GetMidIndex(a,left,right);
	Swap(&a[midi], &a[left]);

	int key = left;
	while (left < right)
	{
		//右邊找比key的值小的
		while (left < right && a[key] <= a[right])
		{
			right--;
		}
		//左邊找大
		while (left < right && a[key] >= a[left])
		{
			left++;
		}
		//進行交換
		Swap(&a[left], &a[right]);
	}
	//跳出只有一個條件，就是left==right，而這個位置就是key要的索引，并且這個值小于key對應的索引
	Swap(&a[left], &a[key]);
	return left;
}

2.1 挖坑法

挖坑法可以選擇在0索引處挖坑（即把數拿走保存），然后從右邊找一個小的填坑，再從左邊找一個大的埋住右邊的坑，最后把key放入相遇點（最后一個坑位）即可，key在下圖為Pivot

int PartSort2(int* a, int left, int right)
{
	int midi = GetMidIndex(a, left, right);
	Swap(&a[midi], &a[left]);

	//挖坑法，讓left為坑，右邊先走找小埋坑，再左邊
	int hole = left;
	int key = a[hole];
	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[left] = key;

	return left;
}

3.1 前后指標版本

思想：一個指標從后面找小，填到前面指標指向的位置，直到后指標越界，總之也都是填好一個值在他該在的位置所做的操作，

int PartSort3(int* a, int left, int right)
{
	//不這樣做排已經有序會造成單邊樹，O（N^2）;
	int midi = GetMidIndex(a, left, right);
	Swap(&a[midi], &a[left]);

	//前后指標法的key可以選擇第一個或者最后一個，邏輯差不多
	int key = left;
	int prev = left, cur = left + 1;
	while (cur <= right)
	{
		//防止自己和自己交換的一種寫法
		if (a[cur] < a[key] && ++prev != cur)
		{
			Swap(&a[prev], &a[cur]);
		}
		cur++;
	}
	Swap(&a[prev], &a[key]);
	return prev;
}

三數取中

因為在實際當中，當我們接近有序的時候，會變成類似一顆單邊樹，所以我們會通過從left mid right 三個位置當中挑選一個適中的值作為key，這樣也能夠保證樹的高度為logN

//三數取中
int GetMidIndex(int* a, int left, int right)
{
	//為了防止int越界[1,4] 1 + 1=2 
	int mid = left + (right - left) / 2;
	if (a[left] > a[mid])
	{
		//a[mid] >= a[right]  ,mid為中
		if (a[mid] >= a[right])
		{
			return mid;
		}
		//a[mid] < a[right] 即 left>mid , mid<right，在left，right找中 
		else if (a[left] >= a[right])
		{
			//小的right為中
			return right;
		}
		else
		{
			return left;
		}
	}
	else //a[left] <= a[mid]
	{
		//a[left] >= a[right]
		if (a[left] >= a[right])
		{
			return left;
		}
		//a[left] < a[right] right和mid中選小的
		else if (a[right] >= a[mid])
		{
			return mid;
		}
		else
		{	//a[right] <a[mid]
			return right;
		}
	}
}

4. 快排代碼

快排實際上就是在單趟排序當中劃分了左右區間，對于左右區間做一個相同的操作，所以這里我們寫了遞回和非遞回（借助堆疊）這兩種實作方式

//遞回
void QuickSort(int* a, int left, int right)
{
	//當區間分割到一個值或者不存在就回傳
	//還剩兩個值我們都需要再排序
	if (left >= right)
		return;
	//當前要做就是確定一個位置,劃磁區間遞回
	//[left,key-1]key[key+1,right]
	int key = PartSort3(a, left, right);
	//遞回左右區間
	QuickSort(a, left, key - 1);
	QuickSort(a, key+1,right);

}

非遞回的在這里借助堆疊，存放我們要進行單趟排序的區間，然后將劃分的左右區間入堆疊，直到不存在左右區間則停止入堆疊，堆疊為空的時候即處理完畢，

//非遞回
void QuickSortNonR(int* a, int left, int right)
{
	//非遞回，我們可以處理當前的區間，再處理磁區間
	//先入右，后入左，就先拿到左
	Stack s;
	StackInit(&s);
	StackPush(&s,right);
	StackPush(&s,left);
	while (!StackEmpty(&s))
	{
		left = StackTop(&s);
		StackPop(&s);
		right = StackTop(&s);
		StackPop(&s);
		//處理當前區間 [left,right]
		int key = PartSort3(a, left, right);

		//劃分左右區間，分別入堆疊
		//[left,key-1]key[key+1,right]
		//先入右區間,區間有兩個值才需要處理
		if (key + 1 < right)
		{
			StackPush(&s, right);
			StackPush(&s, key + 1);
		}
		//再入左區間
		if (left < key - 1)
		{
			StackPush(&s, key - 1);
			StackPush(&s, left);
		}
	}	
}

5.復雜度，穩定性分析

快排的時間復雜度O(NlogN),加了三數取中的快排將最壞的情況轉變為最好的情況了，空間復雜度O(logN),注意空間是累計的，即使是非遞回的空間復雜度也是O(logN),因為最后一層入堆疊是2O(logN),可以理解為之前的用的空間都沒有比這個大的，我們遞回左區間的空間是可以給右區間后面使用的，這種排序也是不穩定的，因為它只是將后面選一個大的放到前面，將前面小的放到后面，a[]= {10,10,3,4,3};這樣的假如是前后指標法在第一次的時候末尾的3就跟前面的10交換了位置，

六、歸并排序

歸并的排序的思想就是在兩個有序的區間合并成一個有序的區間，觀察上圖每個被分割成一個整數的陣列，只有一個整數的時候我們就可以認為他是有序的，這個時候左右區間有序，我們就可以合并成一個有序的陣列，實際上這種方法類似于樹的后序遍歷，

遞回實作：

我們可以把一個陣列分成兩半，對于每一個陣列當他們是有序的就可以進行一次合并操作，對于他們的兩個區間進行遞回，當區間只有一個值的時候我們就可以進行合并回傳上一層，讓上一層合并再回傳，

void _MergeSort(int* a, int left, int right,int* newArr)
{
	if (left >= right)
		return;
	int mid = left + (right - left) / 2;
	//[left,mid][mid+1,right]
	_MergeSort(a, left, mid,newArr);
	_MergeSort(a, mid + 1, right,newArr);
	//走到這里已經是左右區間有序
	//將兩個區間合并成一個區間
	//拷貝到newArr當中，排完再放回
	int index = left;
	int begin1 = left, end1 = mid;
	int begin2 = mid+1,end2 = right;

	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			newArr[index++] = a[begin1++];
		}
		else
		{
			newArr[index++] = a[begin2++];
		}
	}
	//走到這里一定有一邊沒有走完
	while (begin1 <= end1)
	{
		newArr[index++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		newArr[index++] = a[begin2++];
	}
	//拷貝回元素組  letf -- right 的位置
	for (int i = left; i <= right; ++i)
	{
		a[i] = newArr[i];
	}
}
void MergeSort(int* a, int n)
{
//歸并排序就是在左右區間有序重新組合起來
//所以保證左右區間都是有序，遍歷到葉子就可以
	int* newArr = (int*)malloc(sizeof(int) * n);
	int left = 0;
	int right = n - 1;
	_MergeSort(a, left, right,newArr);
}

迭代實作：

迭代實作可以用回圈來實作，這里我們根據遞回思想其實很容易知道，我們控制迭代從最小的子問題出發，保存最小子問題的值，然后提供給后面用，這其實就是一個動態規劃的思想，我們可以從利用子問題的解，解決 “大BOSS” ，

void MergeSortNonR(int* a, int n)
{
	//int a[] = { 8,4,5,7,1,3,6,2,7,8 };
	
	int* newArr=(int*)malloc(sizeof(int)*n) ;
	int groupNum = 1;
	int left;
	int right;
	//動態規劃的思想，當我們把最小的問題切割
	while(groupNum<n/2+1)
	{
		for (int i = 0; i < n; i += (2*groupNum))
		{
		//分成兩組[begin1,end1][begin2,end2]
		int begin1 = i;
		int end1 = i + groupNum - 1;
		int begin2 = i + groupNum;
		int end2 = i + 2 * groupNum - 1;
		//處理兩種情況，當end1已經越界，說明處理end1的邊界
		if (end1 >= n)
		{
			end1 = n - 1;
		}
		//當end1越界，理所當然的begin2和end2都越界了
		//這里可能的[begin1,end1]區間，也需要拷貝到臨時陣列，再拷回原陣列
		if (begin2 >= n)
		{
			//表示右區間不存在
			begin2 = n;
			end2 = n-1;
		}
		else if (begin2 < n && end2 >= n)
		{
			end2 = n - 1;
		}

		left = begin1;
		right = end2;
		//index用于放到臨時陣列newArr當中的
		int index = begin1;

			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					newArr[index++] = a[begin1++];
				}
				else
				{
					newArr[index++] = a[begin2++];
				}
			}
			//走到這里一定有一邊沒有走完
			while (begin1 <= end1)
			{
				newArr[index++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				newArr[index++] = a[begin2++];
			}
			//拷貝回元素組  letf -- right 的位置
			for (int x = left; x <= right; ++x)
			{
				a[x] = newArr[x];
			}
		}
		groupNum*=2;
	}
	free(newArr);
	newArr = NULL;
}

5.復雜度，穩定性分析

歸并排序復雜度是O(N*logN),可以看出他的遞回寫法每次都將一組平均分，分完后高度大概是logN，空間復雜度O（N），因為開了一個相同大小的陣列，他是一種穩定的排序，因為它最后是從小到大有序的匯成一組的，

七、堆排

堆排在之前出過一期，詳細點擊這里，
注意的是排升序要建大堆，排降序建小堆
注意的是排升序要建大堆，排降序建小堆
注意的是排升序要建大堆，排降序建小堆

void AdjustDwon(int* a, int n, int parent)
{
	//大堆
	//默認左孩子為最大的
	int child = parent * 2 + 1;
	//孩子更新到葉子就停止更新
	while (child < n)
	{
		if (child + 1 < n && a[child + 1] > a[child])
		{
			child++;
		}
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = child * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapSort(int* a, int n)
{
	//建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDwon(a, n, i);
	}
	//排升序為例（大堆）
	int size = n-1;
	while (size > 0) {
		Swap(&a[0], &a[size]);
		AdjustDwon(a, size, 0);
		size--;
	}
}

7.復雜度，穩定性分析

建堆的復雜度是O（N），如下圖，堆排的時間復雜度是O（N*logN），空間復雜度O（1），當然堆排序也是不穩定的，因為向下調整的時候可能把一個值就調到最底下了改變相對順序了，

八、計數排序

這是一種非比較排序，看前面的那些排序，他們都是兩兩比較確定是否交換，而這種排序是通過將這個值通過映射到陣列，陣列里存的值表示有多少個這樣的值，當然，在對于資料比較大的時候我們可以通過相對映射，讓（該值-min）后的陣列加一，最后還原回去即可，如圖最小的是90，95-90映射到我們的陣列當中，最后再還原

void CountSort(int* a, int n)
{
	//int a[] = { 31,24,25,16,1,0,79 };

	//遍歷一遍找到最大和最小，然后開大一的陣列
	int max = a[0];
	int min = a[0];
	for (int i = 1; i < n; ++i)
	{
		if (max < a[i])
		{
			max = a[i];
		}
		if (min > a[i])
		{
			min = a[i];
		}
	}
	int size = max - min + 1;
	int* tmp = (int*)calloc(size,sizeof(int));
	//將a遍歷映射到tmp當中,a的長度是n，tmp的長度只有size
	for (int i = 0; i < n; ++i)
	{
		tmp[a[i] - min]++;
	}
	//在按照tmp當中的存放放回去
	int index = 0;
	for (int i = 0; i < size; ++i)
	{
		while (tmp[i] > 0)
		{
			//這里應該是下標+映射的
			a[index++] = i + min;
			--tmp[i];
		}
	}
}

8.復雜度，穩定性分析

計數排序的時間復雜度是O（N），我們只需要遍歷一遍元素組，再把映射的陣串列填回去就可以了，所以這在一些場景下使用是非常高效的，空間復雜度是O(max-min),就是我們開的陣列是這個區間的范圍差，所以對于數值差距比較大的情況下這不適用，它是一種穩定的排序，

九、歸并排序外排序使用

這里我的實作是自己控制每次想在記憶體當中存放多少資料NUM ，當然這個數字是可以稍微大一點的，因為一次IO所需要的時間比在記憶體上差距是很大的，所以我們電腦允許的話一次放入1G，2G的資料進行排序在寫回檔案夾是很好的選擇，這里我們實作還用了宏FILENUM讓我們自己選擇創建檔案夾的多少，所以對于一個具體的數字時，需要算一算然后填寫這兩個值，NUM可以直接給到5千萬，然后用（要排的總數/NUM+1）放到FILENUM當中，

要解決上述這種情況，我們可以先切分成小檔案進行排序寫回檔案，注意這里檔案也不要太小，最好和記憶體掛鉤，一次IO的時間消耗是很大的，我們假設一次在記憶體中排5千萬的數，則需要20個檔案

第二步就把這些有序檔案在硬碟當中進行合并就可以了，

代碼如下：

// 我們做這個最好知道大概有多少資料，我們記憶體一次拿多少資料排好放在一個檔案
// 一般來說，32位陣列開個2G左右就很勉強了，所以我們的n可以到5千萬左右，
// 但這里模擬的話我們只給100個資料，一次從檔案當中拿10個資料排序，模擬這個程序，
// 排好若干子檔案后，再通過兩兩檔案進行歸并實作，
#define NUM 10  //控制一次性放多少資料到檔案當中，就從log.txt拿多少排序好放到檔案中
#define FILENUM 11  //控制檔案的數量
void MergeSortFile()
{
	
	//先對我們要排序的檔案進行分成若干份有序的子檔案
	FILE* pf = fopen("log.txt", "r");
	char filename[20];//檔案名給個20夠了
	int n = NUM;//一次讀取十個,后續可以通過需求直接替換成宏

	//對filename進行初始化
	memset(filename, 0, sizeof(filename));
	int a[10];//緩沖區，將檔案的資料放入a當中
	int i = 1;
	int count = 0;
	//注意考慮一次性讀到檔案尾的情況
	while (count++ < FILENUM)
	{
		memset(filename, 0, sizeof(filename));
		//創建子檔案，從log.txt當中讀取10個數放到a進行歸并排序
		sprintf(filename, "%d",i++);
		FILE* nf = fopen(filename, "w");

		//從pf流里面寫入到a當中
		int index = 0;

		//這里控制兩個邊界有一點難，所以要多一個條件判斷，
		while (~fscanf(pf, "%d", &a[index]))
		{
			//一次讀資料有n個拿n個，沒有就拿到index個
//這里當資料不足這樣寫有問題,可能有資料只有1個的時候，index應該是0，又在這里++
			if (index < n - 1)
				index++;
			else
				break;
		}

		if (index != (NUM - 1))
		{
			index--;
		}

		//這里的index是我們讀到的最大值的索引 0--9
		QuickSort(a, 0, index);

		//往新的檔案里面寫在記憶體當中排好的資料
		for (int i = 0; i <= index; ++i)
		{
			fprintf(nf, "%d\n", a[i]);
		}
		fclose(nf);
	}
	//每一個檔案都已經是有序的了
	//對已經創建出來的檔案進行兩兩歸并，注意這里不能在記憶體歸并了
	//我們要在硬碟上進行歸并，我們選擇將兩兩歸并的檔案以兩個檔案名的和
	char filename1[20];
	char filename2[20];
	//歸并的檔案放到filename當中
	sprintf(filename, "12");
	sprintf(filename1, "1");
	sprintf(filename2, "2");

	//i控制合并多少次 ， 12 ... 1234567891011 9次即可
	for (int i = 2; i <= FILENUM; ++i)
	{
		FILE* f1 = fopen(filename1, "r");
		FILE* f2 = fopen(filename2, "r");
		FILE* pf = fopen(filename, "w");
		//f1 ,f2 兩個有序檔案中讀取放入pf指向的檔案
		int num1 = 0;
		int num2 = 0;
		//每次從兩個檔案中讀取一個，放到num當中進行比較
		int ret1 = fscanf(f1, "%d", &num1);
		int ret2 = fscanf(f2, "%d", &num2);
		while (~ret1 && ~ret2)
		{
			//當兩個當中一個讀到檔案尾則結束
			if (num1 > num2)
			{
				//讀一個更新檔案指標，另一個檔案不動
				fprintf(pf, "%d\n", num2);
				ret2 = fscanf(f2, "%d", &num2);
			}
			else
			{
				fprintf(pf, "%d\n", num1);
				ret1 = fscanf(f1, "%d", &num1);
			}
		}
		//到這里還有一個沒有讀完
		while (ret1 !=EOF)
		{
			fprintf(pf, "%d\n", num1);
			ret1 = fscanf(f1, "%d", &num1);
		}
		while (ret2 != EOF)
		{
			fprintf(pf, "%d\n", num2);
			ret2 = fscanf(f2, "%d", &num2);
		}
		fclose(pf);
		//這里不改變i，所以我們弄個臨時變數保存i，
		int x = i;
		x++;
		//在這里我們更新檔案名
		sprintf(filename2, "%d", x);
		sprintf(filename1, "%s", filename);
		sprintf(filename, "%s%d", filename,x);

	}
}

總結

制作不易，一鍵三連支持一下吧！！！