C语言实现外部排序算法 - 归并排序

#include\x20\x3cstdio.h\x3e #include\x20\x3cstdlib.h\x3e

//\x20定义最大数组长度 #define\x20MAX_SIZE\x20100

//\x20归并排序合并函数 void\x20merge(int\x20arr[],\x20int\x20left,\x20int\x20mid,\x20int\x20right)\x20{ \x20int\x20i,\x20j,\x20k; \x20int\x20n1\x20=\x20mid\x20-\x20left\x20+\x201; \x20int\x20n2\x20=\x20right\x20-\x20mid;

\x20//\x20临时数组 \x20int*\x20L\x20=\x20(int*)malloc((n1\x20+\x201)\x20*\x20sizeof(int)); \x20int*\x20R\x20=\x20(int*)malloc((n2\x20+\x201)\x20*\x20sizeof(int));

\x20//\x20将数据分别复制到临时数组中 \x20for\x20(i\x20=\x200;\x20i\x20\x3c\x20n1;\x20i++) \x20\x20L[i]\x20=\x20arr[left\x20+\x20i]; \x20for\x20(j\x20=\x200;\x20j\x20\x3c\x20n2;\x20j++) \x20\x20R[j]\x20=\x20arr[mid\x20+\x201\x20+\x20j];

\x20//\x20添加末尾的null\x20terminator \x20L[n1]\x20=\x20R[n2]\x20=\x200;

\x20//\x20归并临时到原数组中 \x20i\x20=\x200; //子数组的起始索引 \x20j\x20=\x200; //右数组的起始索引
\x20k\x20=\x20left; //合并后的数组的起始索引 \x20while\x20(i\x20\x3c\x20n1\x20&&\x20j\x20\x3c\x20n2)\x20{ \x20\x20if\x20(L[i]\x20\x3c=\x20R[j])\x20{ \x20\x20\x20arr[k]\x20=\x20L[i]; \x20\x20\x20i++; \x20\x20}\x20else\x20{ \x20\x20\x20arr[k]\x20=\x20R[j]; \x20\x20\x20j++; \x20\x20} \x20\x20k++; \x20}

\x20//\x20处理剩余元素 \x20while\x20(i\x20\x3c\x20n1)\x20{ \x20\x20arr[k]\x20=\x20L[i]; \x20\x20i++; \x20\x20k++; \x20} \x20while\x20(j\x20\x3c\x20n2)\x20{ \x20\x20arr[k]\x20=\x20R[j]; \x20\x20j++; \x20\x20k++; \x20}

\x20//\x20释放临时数组的内存 \x20free(L); \x20free(R); }

//\x20归并排序函数 void\x20mergeSort(int\x20arr[],\x20int\x20left,\x20int\x20right)\x20{ \x20if\x20(left\x20\x3c\x20right)\x20{ \x20\x20int\x20mid\x20=\x20left\x20+\x20(right\x20-\x20left)\x20/\x202;

\x20\x20//\x20分割数组 \x20\x20mergeSort(arr,\x20left,\x20mid); \x20\x20mergeSort(arr,\x20mid\x20+\x201,\x20right);

\x20\x20//\x20合并数组 \x20\x20merge(arr,\x20left,\x20mid,\x20right); \x20} }

//\x20外部排序函数 void\x20externalSort(int\x20arr[],\x20int\x20size)\x20{ \x20//\x20创建临时文件 \x20FILE*\x20tempFile; \x20if\x20(fopen_s(&tempFile,\x20"temp.txt",\x20"w")\x20!=\x200)\x20{ \x20\x20printf("Failed\x20to\x20create\x20temp\x20file.\n"); \x20\x20return; \x20}

\x20//\x20将数据写入临时文件 \x20for\x20(int\x20i\x20=\x200;\x20i\x20\x3c\x20size;\x20i++)\x20{ \x20\x20fprintf(tempFile,\x20"%d\x20",\x20arr[i]); \x20}

\x20//\x20关闭文件 \x20fclose(tempFile);

\x20//\x20读取临时文件并排序 \x20FILE*\x20inputFile; \x20if\x20(fopen_s(&inputFile,\x20"temp.txt",\x20"r")\x20!=\x200)\x20{ \x20\x20printf("Failed\x20to\x20open\x20temp\x20file.\n"); \x20\x20return; \x20} \x20int\x20tempArr[MAX_SIZE]{}; \x20int\x20count\x20=\x200;

\x20while\x20(count\x20\x3c\x20size\x20&&\x20fscanf_s(inputFile,\x20"%d",\x20&tempArr[count])\x20==\x201)\x20{ \x20\x20count++; \x20}

\x20//\x20关闭文件 \x20fclose(inputFile);

\x20//\x20删除临时文件 \x20remove("temp.txt");

\x20//\x20对临时数组进行排序 \x20mergeSort(tempArr,\x200,\x20count\x20-\x201);

\x20//\x20输出排序结果 \x20printf("排序结果：\n"); \x20for\x20(int\x20i\x20=\x200;\x20i\x20\x3c\x20count;\x20i++)\x20{ \x20\x20printf("%d\x20",\x20tempArr[i]); \x20} }

int\x20main()\x20{ \x20int\x20arr[]\x20=\x20{\x2051,\x2049,\x2039,\x2046,\x2038,\x2029,\x2014,\x2061,\x2015,\x2030,\x201,\x2048,\x2052,\x203,\x2063,\x2027,\x204,\x2013,\x2089,\x2024,\x2046,\x2058,\x2033,\x2076\x20}; \x20int\x20size\x20=\x20sizeof(arr)\x20/\x20sizeof(arr[0]);

\x20//\x20外部排序 \x20externalSort(arr,\x20size);

\x20return\x200;