/*
**简单选择排序
*/
void selectSort（dataArray *array）{
int i,j,min,change;
for（i = 0;i<array->length;i++）{
min = i;//以首元素为第一个基准
for（j = i+1;j<array->length;j++）{
if（array->dataArray[min] > array->dataArray[j]）{
//若有小于基准的值，则更换基准
min = j;
}
}
if（i != min）{
//若min与i不想等，则说明找到这趟排序的最小值，交换
change = array->dataArray[min];
array->dataArray[min] = array->dataArray[i];
array->dataArray[i] = change;
}
}
}
/*
**直接插入排序
*/
void insertSort（dataArray *array）{
int i,j,temp;//temp为哨兵元素
for（i = 1;i<array->length;i++）{
if（array->dataArray[i]<array->dataArray[i-1]）{
temp = array->dataArray[i];
for（j = i-1;array->dataArray[j]>temp;j--）{
array->dataArray[j+1] = array->dataArray[j];//记录后移
}
array->dataArray[j+1] = temp;//插入到正确位置
}
}
}
/*
**希尔排序
*/
void shellSort（dataArray *array）{
int i,j,temp;
int increment = array->length;
do{
increment = increment/3+1;//定义增量序列
for（i = increment;i<array->length;i++）{
if（array->dataArray[i] < array->dataArray[i - increment]）{
temp = array->dataArray[i];//用temp暂存
for（j = i-increment;j>=0 && temp < array->dataArray[j];j-=increment）{
array->dataArray[j+increment] = array->dataArray[j];//记录后移，寻找插入位置
}
array->dataArray[j+increment] = temp;//插入
}
}
}while（increment > 1）；
}
/*
**堆排序
*/
void heapSort（dataArray *array）{
int i,temp;
for（i = array->length/2;i>=0;i--）{
heapAdjust（array, i, array->length）；//将目标处理成一个大顶堆
}
for（i = array->length-1;i>0;i--）{
temp = array->dataArray[0];//将堆顶记录和未经交换的子序列中的最后一个序列交换
array->dataArray[0] = array->dataArray[i];
array->dataArray[i] = temp;
heapAdjust（array, 0, i-1）；//将剩余序列重新调整为一个大顶堆
}
}
/*
**将目标处理成大顶堆
*/
void heapAdjust（dataArray *array,int i,int length）{
int temp,j;
temp = array->dataArray[i];
for（j = 2*i;j<length;j *= 2）{//沿关键字较大的孩子结点向下筛选
if（j<length && array->dataArray[j]<array->dataArray[j+1]）{//j为关键字中较大记录的下标
++j;
}
if（temp >= array->dataArray[j]）
break;
array->dataArray[i] = array->dataArray[j];
i = j;
}
array->dataArray[i] = temp;
}
/*
**归并排序
*/
void mergeSort（dataArray *array,dataArray *temArray,int s,int t）{
int m;
dataArray TEMP[MAXSIZE+1];
if（s == t）{
temArray->dataArray[s] = array->dataArray[s];
}
else{
m = （s+t）/2;//将目标序列等分为两个序列
mergeSort（array, TEMP, s, m）；
mergeSort（array, TEMP, m+1, t）；
merge（TEMP,temArray,s,m,t）；
}
}
/*
**将有序子序列归并为有序结果序列
*/
void merge（dataArray *array1,dataArray *array2,int i,int m,int n）{
int j,k,l;
for（j = m+1,k = i;i<=m && j<=n;k++）{
if（array1->dataArray[i]<array1->dataArray[j]）{
array2->dataArray[k] = array1->dataArray[i++];
}else{
array2->dataArray[k] = array1->dataArray[j++];
}
}
if（i<=m）{
for（l = 0;l<=m-i;l++）{
array2->dataArray[k+l] = array1->dataArray[i+l];
}
}
if（j<=n）{
for（l = 0;l<=n-j;l++）{
array2->dataArray[k+l] = array1->dataArray[j+l];
}
}
}
/*
**快速排序
*/
void quickSort（dataArray *array）{
Qsort（array, 0, array->length-1）；
}
/*
**对目标样本中的子序列array（low…high）做快速排序
*/
void Qsort（dataArray *array,int low,int high）{
int pivot;
if（low<high）{
pivot = Partition（array, low, high）；//将dataArray[low…high]一分为二，并返回枢轴下标
Qsort（array, low, pivot-1）；//递归对低子表进行排序
Qsort（array, pivot+1, high）；//递归对高子表进行排序
}
}
/*
**交换顺序表dataArray中子表的记录，使枢轴记录到位，并返回其所在位置
**目标使枢轴两边的元素均不大于（小于）它
*/
int Partition（dataArray *array,int low,int high）{
int pivotKey,temp;
pivotKey = array->dataArray[low];//用子表的第一个记录作为枢轴记录
while（low<high）{//从两端交替向中间扫描
while（low<high && array->dataArray[high]>=array->dataArray[pivotKey]）{
high--;
}
temp = array->dataArray[high];//将比枢轴小的记录交换到低端
array->dataArray[high] = array->dataArray[low];
array->dataArray[low] = temp;
while（low<high && array->dataArray[low]<=array->dataArray[pivotKey]）{
low++;
}
temp = array->dataArray[high];//将比枢轴大的记录交换到高端
array->dataArray[high] = array->dataArray[low];
array->dataArray[low] = temp;
}
return low;//返回枢轴所在的位置
}
/*
**打印结果集
*/
void printArray（dataArray *array）{
int i;
for（i = 0;i<array->length;i++）{
printf（"%d ",array->dataArray[i]）；
}
printf（" \n"）；
}
/*
**操作菜单
*/
status tableList（）{
int choose;
printf（"*******请选择排序类型*******\n"）；
printf（"*******1.冒泡法排序********\n"）；
printf（"*******2.简单选择排序*******\n"）；
printf（"*******3.直接插入排序*******\n"）；
printf（"*******4.希尔排序***********\n"）；
printf（"*******5.堆排序*************\n"）；
printf（"*******6.归并排序***********\n"）；
printf（"*******7.快速排序***********\n"）；
printf（"*******0.退出**************\n"）；
scanf（"%d",&choose）；
return choose;
}
上一页 [1] [2]
【责编:peter】
您现在的位置： 
佚名 
2014-6-22 23:25:25 
相关文章 
相关产品和培训 
文章评论 