/*
Date: 11-02-10 17:40
Description: 排序方法
*/
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
typedef int KeyType;
typedef int OtherType;
typedef struct
{
KeyType key;
OtherType other_data;
}RecordType;
void InsSort(RecordType r[], int length);
void BinSort (RecordType r[], int length);
void ShellInsert(RecordType r[], int length, int delta);
void ShellSort(RecordType r[], int length, int delt[], int n);
void BubbleSort(RecordType r[], int length );
int QKPass(RecordType r[],int left,int right);
void QKSort(RecordType r[],int low, int high );
void SelectSort(RecordType r[], int length);
void sift(RecordType r[], int k, int m);
void crt_heap(RecordType r[], int length );
void HeapSort(RecordType r[],int length);
void Merge(RecordType r1[], int low, int mid, int high, RecordType r2[]);
void MSort(RecordType r1[], int low, int high, RecordType r3[]);
void MergeSort ( RecordType r[], int n );
int main()
{
int i,j,n;
RecordType r[20];
int len;
int delta[3]={4,2,1};
printf("/n请输入待排序记录的长度:");
scanf("%d",&len);
printf("/n");
for(i=1;i<=len;i++)
{
printf("请输入第%d个记录元素:",i);
fflush(stdin);
scanf("%d",&j);
r[i].key = j;
}
printf("/n未排序的序列为：/n");
for(i=1;i<=len;i++)
printf("%d ",r[i].key);
printf("/n");
while(1)
{
printf("/n");
printf(" *********************************/n");
printf(" ** 1-------------直接插入排序法**/n");
printf(" ** 2-------------折半插入排序法**/n");
printf(" ** 3-----------------希尔排序法**/n");
printf(" ** 4-----------------冒泡排序法**/n");
printf(" ** 5-----------------快速排序法**/n");
printf(" ** 6---------------- 选择排序法**/n");
printf(" ** 7-------------------堆排序法**/n");
printf(" ** 8-----------------归并排序法**/n");
printf(" ** 8-------------------退出程序**/n");
printf(" *********************************/n");
while(1)
{
printf("/n请选择上述排序方法中的任意一种：");
scanf("%d",&n);
if(n>=1&&n<=9)
break;
else
printf("/n 请选择1|2|3|4|5|6|7|8|9|/n");
}
switch(n)
{
case 1:
InsSort(r,len);
break;
case 2:
BinSort(r,len);
break;
case 3:
ShellSort(r,len,delta,3);
break;
case 4:
BubbleSort(r,len);
break;
case 5:
QKSort(r,1,len);
break;
case 6:
SelectSort(r,len);
break;
case 7:
HeapSort(r,len);
break;
case 8:
MergeSort(r,len);
break;
case 9:
exit(0);
default:
break;
}
printf("/n排序后的序列为：/n");
for(i=1;i<=len;i++)
printf("%d ",r[i].key);
printf("/n");
}
}
void InsSort(RecordType r[], int length)
/* 对记录数组r做直接插入排序，length为数组中待排序记录的数目*/
{
int i,j;
for (i=2; i<=length; i++)
{
r[0]=r[i]; /*将待插入记录存放到监视哨r[0]中*/
j=i-1;
while (r[0].key< r[j].key ) /* 寻找插入位置 */
{
r[j+1]= r[j];
j--;
}
r[j+1]=r[0]; /*将待插入记录插入到已排序的序列中*/
}
}
void BinSort (RecordType r[], int length)
/*对记录数组r进行折半插入排序，length为数组的长度*/
{
int i,j;
RecordType x;
int low,high,mid;
for ( i=2; i<=length ; ++i )
{
x= r[i];
low=1; high=i-1;
while (low<=high ) /* 确定插入位置*/
{
mid=(low+high) / 2;
if ( x.key< r[mid].key )
high=mid-1;
else
low=mid+1;
}
for ( j=i-1 ; j>= low; --j )
r[j+1]= r[j]; /* 记录依次向后移动 */
r[low]=x; /* 插入记录 */
}
}
void ShellInsert(RecordType r[], int length, int delta)
/*对记录数组r做一趟希尔插入排序，
length为数组的长度,delta 为增量
*/
{
int i,j;
for(i=1+delta;i<= length; i++)/* 1+delta为第一个子序列的第二个元素的下标 */
if(r[i].key < r[i-delta].key)
{
r[0]= r[i]; /* 备份r[i] (不做监视哨) */
for(j=i-delta; j>0 &&r[0].key < r[j].key; j-=delta)
r[j+delta]= r[j];
r[j+delta]= r[0];
}
}
void ShellSort(RecordType r[], int length, int delt[], int n)
/*对记录数组r做希尔排序，length为数组r的长度，
delta 为增量数组，n为delta[]的长度
*/
{
int i;
for(i=0 ; i<=n-1; ++i)
ShellInsert(r, length, delt[i]);
}
void BubbleSort(RecordType r[], int length )
/*对记录数组r做冒泡排序，length为数组的长度*/
{
int n,i,j;
int change;
RecordType x;
n=length;
change=TRUE;
for ( i=1 ; i<= n-1 && change ;++i )
{
change=FALSE;
for ( j=1 ; j<= n-i ; ++j)
if (r[j].key > r[j+1].key )
{
x= r[j];
r[j]= r[j+1];
r[j+1]= x;
change=TRUE;
}
}
}
int QKPass(RecordType r[],int left,int right)
/*对记录数组r 中的r[left]至r[right]部分进行一趟排序
并得到基准的位置，使得排序后的结果满足其之后（前）
的记录的关键字均不小于（大于）于基准记录
*/
{
RecordType x;
int low,high;
x= r[left]; /* 选择基准记录*/
low=left;
high=right;
while ( low<high )
{
while (low< high && r[high].key>=x.key )
/* high从右到左找小于x.key的记录 */
high--;
if ( low <high )
{
r[low]= r[high];
low++;
}
/* 找到小于x.key的记录，则进行交换*/
while (low<high && r[low].key<x.key ) /* low从左到右找大于x.key的记录 */
low++;
if ( low<high )
{
r[high]= r[low];
high--;
} /* 找到大于x.key的记录，则交换*/
}
r[low]=x; /*将基准记录保存到low=high的位置*/
return low; /*返回基准记录的位置*/
}
void QKSort(RecordType r[],int low, int high )
/*对记录数组r[low..high]用快速排序算法进行排序*/
{
int pos;
if(low<high)
{
pos=QKPass(r, low, high); /*调用一趟快速排序，将枢轴元素为界划分两个子表*/
QKSort(r, low, pos-1); /*对左部子表快速排序*/
QKSort(r, pos+1, high); /*对右部子表快速排序*/
}
}
void SelectSort(RecordType r[], int length)
/*对记录数组r做简单选择排序，length为数组的长度*/
{
int i,j,k;
int n;
RecordType x;
n=length;
for ( i=1 ; i<= n-1; ++i)
{
k=i;
for ( j=i+1 ; j<= n ; ++j)
if (r[j].key < r[k].key )
k=j;
if ( k!=i)
{
x= r[i];
r[i]= r[k];
r[k]=x;
}
}
}
void sift(RecordType r[], int k, int m)
/* 假设ｒ[k..m]是以ｒ[k]为根的完全二叉树，且分别以ｒ[2k]和ｒ[2k+1]为根的左、右子树为大根堆，调整r[k]，使整个序列r[k..m]满足堆的性质 */
{
RecordType t;
int i,j;
int x;
int finished;
t= r[k]; /* 暂存"根"记录r[k] */
x=r[k].key;
i=k;
j=2*i;
finished=FALSE;
while( j<=m && !finished )
{
if (j<m && r[j].key< r[j+1].key )
j=j+1; /* 若存在右子树，且右子树根的关键字大，则沿右分支"筛选" */
if ( x>= r[j].key)
finished=TRUE; /* 筛选完毕 */
else
{
r[i] = r[j];
i=j;
j=2*i;
} /* 继续筛选 */
}
r[i] =t; /* r[k]填入到恰当的位置 */
}
void crt_heap(RecordType r[], int length )
/*对记录数组r建堆，length为数组的长度*/
{
int i,n;
n= length;
for ( i=n/2; i >= 1; --i) /* 自第[n/2]个记录开始进行筛选建堆 */
sift(r,i,n);
}
void HeapSort(RecordType r[],int length)
/* 对r[1..n]进行堆排序，执行本算法后，r中记录按关键字由大到小有序排列 */
{
int i,n;
RecordType b;
crt_heap(r, length);
n= length;
for ( i=n ; i>= 2; --i)
{
b=r[1]; /* 将堆顶记录和堆中的最后一个记录互换 */
r[1]= r[i];
r[i]=b;
sift(r,1,i-1); /* 进行调整，使r[1..i-1]变成堆 */
}
}
void Merge(RecordType r1[], int low, int mid, int high, RecordType r2[])
/* 已知r1[low..mid]和r1[mid+1..high]分别按关键字有序排列，
将它们合并成一个有序序列，存放在r2[low..high]
*/
{
int i,j,k;
i=low;
j=mid+1;
k=low;
while ( (i<=mid)&&(j<=high) )
{
if ( r1[i].key<=r1[j].key )
{
r2[k]=r1[i];
++i;
}
else
{
r2[k]=r1[j];
++j;
}
++k;
}
while( i<=mid )
{
r2[k]=r1[i];
k++;
i++;
}
while( j<=high)
{
r2[k]=r1[j];
k++;
j++;
}
}
void MSort(RecordType r1[], int low, int high, RecordType r3[])
/* r1[low..high]经过排序后放在r3[low..high]中，r2[low..high]为辅助空间 */
{
int mid;
RecordType r2[20];
if ( low==high )
r3[low]=r1[low];
else
{
mid=(low+high)/2;
MSort(r1,low, mid, r2);
MSort(r1,mid+1,high, r2);
Merge (r2,low,mid,high, r3);
}
}
void MergeSort ( RecordType r[], int n )
/*对记录数组r[1..n]做归并排序 */
{
MSort ( r, 1, n, r );
}