用分治法实现高速排序问题
1．实验目的
(1) 掌握分治策略的基本思想及求解问题的主要步骤；
(2) 应用分治策略的基本思想设计高速排序算法。
2．实验环境
Windows操作系统，VC++ 6.0。
3．实验内容
有n个无序的数值数据。现要求将其排列成一个有序的序列。
4.实验步骤
(1) 介绍算法的主要设计思想。
(2) 自己定义input函数，从文件里读入必要的数据；
(3) 自己定义algorithm函数，得到问题的解(重点步骤)。
(4) 自己定义output函数，输出问题的解到外部文件；
(5) 自己定义main函数，初始化相关信息并调用上述三个函数完毕实验任务；
(6) 设计測试用例进行測试，验证程序是否正确。
#include<stdio.h>
#include<stdlib.h>
int Partition(int number[], int left, int right);
int input(int number[]) {
FILE *fp;
int i = -1;
if ((fp = fopen("c:\number.txt","r")) == NULL)
{
printf("file open error!
");
exit(0);
}
while (!feof(fp)) {
fscanf(fp,"%d ", &number[++i]);
}
fclose(fp);
return i;
}
void QuickSort(int number[],int left,int right) {
if (right <= left)
{
return;
}
int pivot = (left + right) / 2; //选择轴值
//不借助 第三个变量实现两个变量之间的值交换
//将轴值放入到数组末端
number[pivot] = number[pivot] + number[right];
number[right] = number[pivot] - number[right];
number[pivot] = number[pivot] - number[right];
pivot = Partition(number,left, right); //切割后轴值到达正确位置
QuickSort(number,left, pivot - 1); //对轴值左边的子序列进行递归高速排序
QuickSort(number,pivot + 1, right); //对轴值右边的子序列进行递归高速排序
}
int Partition(int number[],int left,int right) {
int l = left;
int r = right;
int temp = number[r];//将轴值放入到暂时变量中
while (l!=r) {
//l指针向右移动，越过那些小于轴值得记录。直到找到一个大于轴值得记录
while (number[l]<=temp&&l<r)
{
l++;
}
if (l < r) {
number[r] = number[l];
r--; //r向左移动一步
}
while (number[r] >= temp && r>l)
{
r--;
}
if (r>l)
{
number[l] = number[r];
l++; //l指针向右移动一步
}
}
number[l] = temp; //把轴值回填到分界位置l上
return l;
}
void output(int number[],int right) {
FILE *fp;
int i = 0;
if ((fp = fopen("c://num.txt", "w")) == NULL) {
printf("file open error!");
exit(0);
}
while (i<=right)
{
fprintf(fp, "%d ", number[i]);
i++;
}
fclose(fp);
}
int main()
{
int number[100];
int left = 0,right=input(number),i;
QuickSort(number, left, right);
output(number, right);
return 0;
}