目錄
1、外排序
2、計數排序
1、外排序
上一節中提到的排序都可以用來進行內排序，但是只有歸并排序的思想可以用來進行外部排序，因為文件數據是沒辦法像數組那樣進行訪問的。
例如：
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}int GetMidIndex(int* a, int begin, int end)
{int mid = (begin + end) / 2;if (a[begin] < a[mid]){if (a[mid] < a[end])return mid;else if (a[begin] > a[end])return begin;elsereturn end;}else // a[begin] > a[mid]{if (a[mid] > a[end])return mid;else if (a[begin] < a[end])return begin;elsereturn end;}
}void QuickSort(int* a, int left, int right)//快速排序
{assert(a);if (left >= right)return;int midIndex = GetMidIndex(a, left, right);Swap(&a[midIndex], &a[right]);int prev = left - 1;int cur = left;int keyindex = right;while (cur < right){if (a[cur] < a[keyindex] && ++prev != cur)Swap(&a[prev], &a[cur]);++cur;}Swap(&a[++prev], &a[keyindex]);int div = prev;QuickSort(a, left, div - 1);QuickSort(a, div + 1, right);}void _MergeFile(const char* file1, const char* file2, const char* mfile)//對兩個文件進行歸并。
{FILE* fout1 = fopen(file1, "r");//讀文件1。if (fout1 == NULL){printf("打開文件失敗\n");exit(-1);}FILE* fout2 = fopen(file2, "r");//讀文件2。if (fout2 == NULL){printf("打開文件失敗\n");exit(-1);}FILE* fin = fopen(mfile, "w");//寫出歸并文件。if (fin == NULL){printf("打開文件失敗\n");exit(-1);}int num1, num2;int ret1 = fscanf(fout1, "%d\n", &num1);int ret2 = fscanf(fout2, "%d\n", &num2);while (ret1 != EOF && ret2 != EOF){if (num1 < num2){fprintf(fin, "%d\n", num1);ret1 = fscanf(fout1, "%d\n", &num1);}else{fprintf(fin, "%d\n", num2);ret2 = fscanf(fout2, "%d\n", &num2);}}while (ret1 != EOF){fprintf(fin, "%d\n", num1);ret1 = fscanf(fout1, "%d\n", &num1);}while (ret2 != EOF){fprintf(fin, "%d\n", num2);ret2 = fscanf(fout2, "%d\n", &num2);}fclose(fout1);fclose(fout2);fclose(fin);
}void MergeSortFile(const char* file)//待排文件
{FILE* fout = fopen(file, "r");if (fout == NULL){printf("打開待排文件失敗\n");exit(-1);}int n = 10;//每組數據有10個，我們在該測試中，僅僅只測試100個數據的外排序，所以每組分為了10個數據。int a[10];//將num每次讀取的數據放入該數組中。int i = 0;int num = 0;//每次讀取的數據暫時存放在此處。char subfile[20];int filei = 1;memset(a, 0, sizeof(int) * n);//初始化數組awhile (fscanf(fout, "%d\n", &num) != EOF){if (i < n - 1){a[i++] = num;}else{a[i] = num;QuickSort(a, 0, n - 1);//使用快速排序進行內存上的排序。sprintf(subfile, "%d", filei++);FILE* fin = fopen(subfile, "w");if (fin == NULL){printf("打開文件失敗\n");exit(-1);}for (int j = 0; j < n; j++){fprintf(fin, "%d\n", a[j]);}fclose(fin);i = 0;memset(a, 0, sizeof(int) * n);}}// 利用互相歸并到文件，實現整體有序char mfile[100] = "12";//由file1和file2歸并出來的文件char file1[100] = "1";char file2[100] = "2";for (int i = 2; i <= n; ++i){// 讀取file1和file2,進行歸并出mfile_MergeFile(file1, file2, mfile);strcpy(file1, mfile);sprintf(file2, "%d", i + 1);sprintf(mfile, "%s%d", mfile, i + 1);}printf("%s文件排序成功\n", file);fclose(fout);
}int main()
{MergeSortFile("../DataSort.txt");return 0;
}?對于這個例子，讀者不必要關注這個代碼是不是寫的有點不規范，只需要明白外排序的思想即可。
2、計數排序
思想：計數排序又稱為鴿巢原理，操作步驟：
1. 統計相同元素出現次數。
2. 根據統計的結果進行排序。
例如：
//計數排序
void CountSort(int* a, int n)
{int min = a[0], max = a[0];for (int i = 0; i < n; i++){if (a[i] < min){min = a[i];}if (a[i] > max){max = a[i];}}int range = max - min + 1;int* countA = (int*)malloc(sizeof(int) * range);memset(countA, 0, sizeof(int) * range);//for (int i = 0; i < n; i++){countA[a[i] - min]++;}int k = 0;for (int j = 0; j < range; j++){while (countA[j]--){a[k++] = j + min;}}
}計數排序的特性總結：
1. 計數排序在數據范圍集中時，效率很高，但是適用范圍及場景有限（僅僅只適用于整數的排序）
2. 時間復雜度：O(N+range)。
3. 空間復雜度：O(range)。
4. 穩定性：穩定
)
