数据结构加餐：三路划分、自省排序、文件归并排序
数据结构加餐1
- 1.快排之三路划分
- 2.快排之自省排序
- 3.文件归并排序
- 3.1外排序
- 3.2归并排序的实现
- 3.2.1归并排序思想
- 3.2.2文件归并排序代码实现
1.快排之三路划分
在之前完成的快排仍然存在这一些问题，当重复数据较多时，快速排序选择的基值也会较不恰当，比如在一组全为2的数组中，选择的基值也会是2，但是这样就会触发快排的最坏情况，导致时间的增加，下面我们要介绍一个方法来解决这种情况
我们先实现基本的快排(Hoare 版本)：
//快速排序--Hoare版本
void Swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
//寻找基值
int Quick_Sort(int* arr, int left, int right)
{
//假设第一个值为基值
int mid = left;
left++;
while (left <= right)
{
//left负责寻找比基值大的元素
while (left <= right && arr[left] < arr[mid])
{
left++;
}
//right负责寻找比基值小的元素
while (left <= right && arr[right] > arr[mid])
{
right--;
}
//将左右数据交换，大数据在右边，小数据在左边
if(left <= right)
{
Swap(&arr[left++], &arr[right--]);
}
}
Swap(&arr[mid], &arr[right]);
return mid;
}
void QuickSort(int* arr, int left, int right)
{
//快速排序需要递归寻找基值
//递归结束条件
if (left >= right)
{
return;
}
//寻找基值
int mid = Quick_Sort(arr, left, right);
//递归区间
//左区间：[left, mid-1]， 右区间：[mid+1, right]
QuickSort(arr, left, mid-1);
QuickSort(arr, mid+1, right);
}
void Print(int* arr, int len)
{
for (int i = 0; i < len; i++)
{
printf("%d ", arr[i]);
}
}
int main()
{
int arr[] = { 1, 22, 3, 43, 66, 27, 38, 49 };
QuickSort(arr, 0, 7);
Print(arr, 8);
return 0;
}
更改后的代码为：
void QuickSort(int* arr, int left, int right)
{
//递归结束条件
if (left >= right)
{
return;
}
//寻找基值
int begin = left;
int end = right;
int cur = left + 1;
int key = arr[left];
while (cur <= right)
{
if (arr[cur] < key)
{
Swap(&arr[cur], &arr[left]);
cur++;
left++;
}
else if (arr[cur] > key)
{
Swap(&arr[cur], &arr[right]);
right--;
}
else
{
cur++;
}
}
QuickSort(arr, begin, left-1);
QuickSort(arr, right+1, end);
}
int main()
{
int arr[] = { 1, 22, 3, 43, 66, 27, 38, 49 };
QuickSort(arr, 0, 7);
Print(arr, 8);
return 0;
}
2.快排之自省排序
自省排序值的就是在排序函数之中加上一个检查的功能，使得排序算法能够针对不同的环境做出不同的反应，这一部分较为简单，因为都是已经学过的内容，所以我们直接看改变即可
void IntroSort(int* a, int left, int right, int depth, int defaultDepth)
{
if (left >= right)
return;
// 数组⻓度⼩于16的⼩数组，换为插⼊排序，简单递归次数
if (right - left + 1 < 16)
{
//此时使用插入排序
InsertSort(a + left, right - left + 1);
return;
}
// 当深度超过2*logN时改⽤堆排序
if (depth > defaultDepth)
{
HeapSort(a + left, right - left + 1);
return;
}
depth++;//每次完成一次递归，将递归深度++
int begin = left;
int end = right;
// 随机选key
int randi = left + (rand() % (right - left + 1));
Swap(&a[left], &a[randi]);
int prev = left;
int cur = prev + 1;
int keyi = left;
while (cur <= right)
{
if (a[cur] < a[keyi] && ++prev != cur)
{
Swap(&a[prev], &a[cur]);
}
++cur;
}
Swap(&a[prev], &a[keyi]);
keyi = prev;
// [begin, keyi-1] keyi [keyi+1, end]
IntroSort(a, begin, keyi - 1, depth, defaultDepth);
IntroSort(a, keyi + 1, end, depth, defaultDepth);
}
void QuickSort(int* a, int left, int right)
{
int depth = 0;
int logn = 0;
int N = right - left + 1;
//计算logN的值
for (int i = 1; i < N; i *= 2)
{
logn++;
}
// introspective sort -- ⾃省排序
// 一般来说，当深度大于2倍的logN时，最合理，但也不是必须要使用2倍当作结点
IntroSort(a, left, right, depth, logn * 2);
}
int* sortArray(int* nums, int numsSize, int* returnSize) {
srand(time(0));
QuickSort(nums, 0, numsSize - 1);
*returnSize = numsSize;
return nums;
}
3.文件归并排序
3.1外排序
外排序是指能够处理大量数据的排序算法，比如说10G的数据，外排序的数据不能够一次性地写入内存，只能放在读写比较慢的硬盘上，也就是写入文件中，通常会采用“排序-归并”的思想。先读取能够放在内存中的数据量，将这些数据排成有序后放在一个临时文件中，然后在归并阶段将一个个的小文件归并成一个文件即可
3.2归并排序的实现
3.2.1归并排序思想
先将一个一个的思想列出，最后有一个总截图：
3.2.2文件归并排序代码实现
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
//创建随机数，并将数据写到文件中
void CreateNDate()
{
//造数据
int n = 100;
srand(time(0));
const char* file = "data.txt";
FILE* fin = fopen(file, "w");
if (fin == NULL)
{
perror("fopen error");
return;
}
for (int i = 0; i < n; ++i)
{
int x = rand() + i;
fprintf(fin, "%d\n", x);
}
fclose(fin);
}
//qsort函数比较方法
int compare(const void* a, const void* b)
{
return (*(int*)a - *(int*)b);
}
//读取数据，将数据排序后写入文件中
int ReadDataSortToFile(FILE* fout, int m, const char* file2)
{
//这个函数为将排序后的数据写到文件中，所以肯定要先进行排序
//排序思路为先创建出一个数组，存储m个数据，对数组中的数据进行排序
int* a = (int*)malloc(m * sizeof(int));
if (a == NULL)
{
perror("malloc fail");
return 0;
}
int x = 0;
int j = 0;
for (int i = 0; i < m; i++)
{
//这里要对最后一组数据读取进行特殊处理（最后一组数据读取可能读取不了m个数据）：
//如果读取不到数据了，就停止读取数据，也就是说实际上读取的数据个数其实只有j个
if (fscanf(fout, "%d", &x) == EOF)
break;
a[j++] = x;
}
if (j == 0)//当没有数据读取时，直接返回即可
{
free(a);
return 0;
}
//有了数组之后，就可以对数组中的数据进行排序
qsort(a, j, sizeof(int), compare);//既然读取了j个数据，那么就对j个数据进行排序
//排序完成，将数据写入文件中，这时只需要创建一个文件，然后写入数据即可
FILE* fin = fopen(file2, "w");
if (fin == NULL)
{
//注意要释放空间
free(a);
perror("fopen fail");
return 0;
}
for (int i = 0; i < j; i++)
{
fprintf(fin, "%d\n", a[i]);//这里写入时，需要加上\n
}
//最后注意要释放空间
free(a);
a = NULL;
fclose(fin);
return j;
}
//将file1和file2文件中的数据排序着写入mfile文件中
void MergeFile(const char* file1, const char* file2, const char* mfile)
{
//对于两个文件的排序，只需要一个数据一个数据地读取，然后将读取的数据进行比较,小的数据写入mfile文件即可
//先打开三个文件
FILE* fout1 = fopen(file1, "r");
if (fout1 == NULL)
{
perror("fopen error");
return;
}
FILE* fout2 = fopen(file2, "r");
if (fout2 == NULL)
{
perror("fopen error");
return;
}
FILE* mfin = fopen(mfile, "w");
if (mfin == NULL)
{
perror("fopen error");
return;
}
//然后是排序写入文件过程
int x1 = 0;
int x2 = 0;
int ret1 = fscanf(fout1, "%d", &x1);//fscanf函数，如果读取失败或已经没有数据读取了，返回EOF
int ret2 = fscanf(fout2, "%d", &x2);
while (ret1 != EOF && ret2 != EOF)
{
if (x1 < x2)
{
fprintf(mfin, "%d\n", x1);
ret1 = fscanf(fout1, "%d", &x1);
}
else
{
fprintf(mfin, "%d\n", x2);
ret2 = fscanf(fout2, "%d", &x2);
}
}
while (ret1 != EOF)
{
fprintf(mfin, "%d\n", x1);
ret1 = fscanf(fout1, "%d", &x1);
}
while (ret2 != EOF)
{
fprintf(mfin, "%d\n", x2);
ret2 = fscanf(fout2, "%d", &x2);
}
//最后要注意关闭文件
fclose(fout1);
fclose(fout2);
fclose(mfin);
}
int main()
{
//创建数据函数，也就是创建file数据文件
//CreateNDate();
//创建file1和file2文件，并且读取数据进行排序后写入file1和file2文件中
//既然要多次使用一个方法，那么我们就将这个方法写成一个函数
const char* file1 = "file1.txt";
const char* file2 = "file2.txt";
const char* mfile = "mfile.txt";
FILE* fout = fopen("data.txt", "r");//fopen函数返回一个指向打开文件的指针，错误时返回NULL
if (fout == NULL)
{
perror("fopen fail");
return 0;
}
int m = 10;
//函数参数的意思是：向fout文件中读取m个数据排序后写入file1文件中
ReadDataSortToFile(fout, m, file1);
ReadDataSortToFile(fout, m, file2);
//将file1和file2文件中的数据排序着放到mfile文件中
while (1)
{
//文件写入函数
MergeFile(file1, file2, mfile);
//关闭file1和file2文件
remove(file1);//remove函数作用为删除一个文件，成功返回0，不成功返回-1，并设置错误原因
remove(file2);
//将mfile文件名称改为file1
rename(mfile, file1);//remane函数：将文件重命名，成功时，返回0，失败时，返回非0
//读取m个数据写到file2文件中
//当读取不出数据时，也就是文件中的数据读取完了之后，就结束循环
int n = 0;
if ((n = ReadDataSortToFile(fout, m, file2)) == 0)
break;
}
return 0;
}