数据结构5（初）：续写排序

目录

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. 稳定性：稳定