#include <stdlib.h>
#include <time.h>
#include <conio.h>
#include <memory.h>
#define ElemType int
#define Status int
#define TRUE 1
#define FALSE 0
typedef struct
{
ElemType *elem;
long length;
}SqList;
//初始化排序表
Status InitList(SqList &L,long len)
{
L.length = len + 1;
L.elem = (int*)malloc(sizeof(int)*L.length);
if(!L.elem)
{
printf("The system malloc memory error!\n");
return FALSE;
}
return TRUE;
}
//删除排序表
Status DeleteList(SqList &L)
{
if(L.elem != NULL)
free(L.elem);
L.length = 0;
return TRUE;
}
//产生一组伪随机数组
Status CreateList_R(SqList &L)
{
long i;
L.elem[0] = 0;
srand((unsigned)time(NULL));
for(i = 1;i<L.length;i++)
L.elem =::rand();
return TRUE;
}
//产生一组正序数组
Status CreateList_P(SqList &L)
{
long i;
L.elem[0] = 0;
for(i=1;i<L.length;i++)
L.elem = i;
return TRUE;
}
//产生一组逆序数组
Status CreateList_N(SqList &L)
{
long i,j;
L.elem[0] = 0;
j = L.length - 1;
for(i=1;i<L.length;i++)
L.elem = j--;
return TRUE;
}
/*
插入类
简单插入排序(InsertSort) 折半插入排序(BInsertSort) 希尔排序(ShellSort) 改进后的希尔排序(ShellSortA)
*/
//简单插入排序
void InsertSort(SqList &L)
{
long i,j;
for(i=2;i<L.length;++i) //从2到L.Length依次进行插入排序
{
if(L.elem < L.elem[i-1]) //R表示待插入有序序列的值 如果R<R[i-1]则找插入位置 否则不移动
{
L.elem[0] = L.elem; //R[0]为哨兵，复制待插入值R到哨兵位
L.elem = L.elem[i-1];
for(j=i-2;L.elem[0]<L.elem[j];--j)
L.elem[j+1] = L.elem[j]; //记录后移
L.elem[j+1] = L.elem[0]; //插入到正确位置
}//if
}//for
}//InsertSort
//折半插入排序
void BInsertSort(SqList &L)
{
long i,j,low,high,mid;
for(i=2;i<L.length;++i) //从2到L.Length依次进行插入排序
{
L.elem[0] = L.elem;
low = 1;
high = i-1;
while(low <= high) //将R通过折半查找插入恰当的位置
{
mid = (low + high) / 2;
if(L.elem[0] < L.elem[mid])
high = mid - 1;
else
low = mid + 1;
}//while
for(j = i-1;j >= high+1;--j) //记录后移空出位置来插入R值
L.elem[j+1] = L.elem[j];
L.elem[high+1] = L.elem[0];//插入到正确位置
}//for
}//BInsertSort
//教材上的希尔排序
void ShellInsert(SqList L,int dk)
{
long i,j;
for(i = dk+1;i<L.length;++i)
if(L.elem < L.elem[i-dk])
{
L.elem[0] = L.elem;
for(j = i-dk; j>0&&(L.elem[0]<L.elem[j]);j-=dk)
L.elem[j+dk] = L.elem[j];
L.elem[j+dk] = L.elem[0];
}
}//ShellInsert
void ShellSort(SqList L,int dlta[],int t)
{
int k;
for(k=0;k<t;k++)
ShellInsert(L,dlta[k]);
}//ShellSort
//经过改进的希尔排序
void ShellSortA(SqList L)
{
int i,j,h,v;
for(h = 1; h <= (L.length-1) / 9; h = 3*h+1); //查找确定最大增量值
for(; h>0;h /= 3)
for(i = h; i < L.length; i++) //直接插入排序的一种改进（与直接插入排序比较）
{
j = i; v = L.elem;
while(j > h && v<L.elem[j-h])
{
L.elem[j] = L.elem[j-h]; j -= h;
}
L.elem[j] = v;
}
}
/*
交换类
起泡排序(BubbleSort) 快速排序(QuickSort)
*/
//起泡排序
void BubbleSort(SqList &L)
{
long i,j;
int change,tmp;
for(i=L.length-1,change=TRUE;i>=2&&change;--i) //change作为监视值 当一次扫描过程中没有交换 表明序列已全部有序
{
change = FALSE;
for(j=1;j<i;++j)
if(L.elem[j]>L.elem[j+1])
{
tmp = L.elem[j];
L.elem[j] = L.elem[j+1];
L.elem[j+1] = tmp;
change = TRUE;
}
}
}
//快速排序
int Partition(SqList &L,int low,int high)
{
int key = L.elem[low];
L.elem[0] = L.elem[low];
while(low<high)
{
while(low<high && L.elem[high]>=key)
--high;
L.elem[low] = L.elem[high];
while(low<high && L.elem[low]<=key)
++low;
L.elem[high] = L.elem[low];
}
L.elem[low] = L.elem[0];
return low;
}//Partition
void QSort(SqList &L,int low,int high)
{
int key;
if(low < high)
{
key = Partition(L,low,high);
QSort(L,low,key-1);
QSort(L,key+1,high);
}
}//QSort
void QuickSort(SqList &L)
{
QSort(L,1,L.length-1);
}
/*
选择类
简单选择排序(SelectSort) 堆排序(HeapSort)
*/
//简单选择排序
void SelectSort(SqList &L)
{
long i,j;
int tmp,mins=0;
for(i=1;i<L.length;i++)
{
mins = i;
for(j=i+1;j<L.length;j++)
if(L.elem[j]<L.elem[mins])
mins = j;
tmp = L.elem; L.elem = L.elem[mins]; L.elem[mins] = tmp;
}
}
//堆排序
void HeapAdjust(SqList &L,int s,int m)
{
long j;
int rc = L.elem[s];
for(j=2*s;j<=m;j*=2)//沿key较大的孩子结点向下筛选
{
if(j<m&&(L.elem[j]<L.elem[j+1])) //j为key较大的记录的下标
++j;
if(!(rc<L.elem[j]))
break;
L.elem[s]=L.elem[j];
s=j;
}
L.elem[s] = rc; //插入
}//HeapAdjust
void HeapSort(SqList &L)
{
long i;
int tmp;
for(i = (L.length-1)/2;i>0;--i)
HeapAdjust(L,i,L.length-1);
for(i = L.length-1;i>1;--i)
{
tmp = L.elem[1];
L.elem[1] = L.elem;
L.elem = tmp;
HeapAdjust(L,1,i-1);
}
}//HeapSort
/*
其它
基数排序(HeapSort)
*/
//基数排序
void RadixSort(SqList &L)
{
int keysize=5;
int n = L.length;
int i,j,k,t;
int d,e,m=0;
int *c[10],z[10];
for (i=0;i<10;i++)
c=(int*)malloc(sizeof(int)*n);
for(i=0;i<keysize;i++)
{
memset(z,0,sizeof(z));
for(j=1;j<n;j++)
{
k=L.elem[j];
for (t=0;t<i;t++)
k=k/10;
k=k%10;
*(c[k]+z[k])=L.elem[j];
z[k]++;
}
m=1;
for(d=0;d<10;d++)
{
for(e=0;e<z[d];e++)
{
L.elem
m++;
}
}
}
for (i=0;i<10;i++)
free(c);
}
Status CopyList(SqList L,SqList &T)
{
long i;
for(i=1;i<L.length;i++)
T.elem = L.elem;
return TRUE;
}
//显示排序表中的元素
Status ShowList(SqList L,char sz)
{
int i;
if((sz == 'y') || (sz == 'Y'))
{
for(i=1;i<L.length;i++)
printf("%d ",L.elem);
printf("\n\n");
return TRUE;
}
else
return FALSE;
}
//计算排序算法运行时间
void RunTime(int runtime)
{
printf("花费时间%f\n",(long double) runtime/CLOCKS_PER_SEC);
}
Status Display(SqList &L,int size,char sz,int kind)
{
int start_time, end_time;
SqList T;
InitList(T,size);
InitList(L,size);
switch(kind)
{
case 0:
CreateList_R(L);
break;
case 1:
CreateList_P(L);
break;
case 2:
CreateList_N(L);
break;
default:
return FALSE;
}
if(sz == 'Y'|| sz == 'y')
{
printf("---------－未排序序列-----------\n");
ShowList(L,sz);
}
if(kind == 0)
{
printf("---------－快速排序-------------\n");
CopyList(L,T);
start_time = clock();
QuickSort(T);
end_time = clock();
RunTime(end_time - start_time);
ShowList(T,sz);
}
else
{
if(size>500)
printf("\n正反序过大时，快速排序可能会导致堆栈溢出，故屏蔽测试\n");
else
{
printf("--------－快速排序-------------\n");
CopyList(L,T);
start_time = clock();
QuickSort(T);
end_time = clock();
RunTime(end_time - start_time);
ShowList(T,sz);
}
}
printf("--------－堆排序----------------\n");
CopyList(L,T);
start_time = clock();
HeapSort(T);
end_time = clock();
RunTime(end_time - start_time);
ShowList(T,sz);
printf("--------－基数排序--------------\n");
CopyList(L,T);
start_time = clock();
RadixSort(T);
end_time = clock();
RunTime(end_time - start_time);
ShowList(T,sz);
printf("--------－改进的希尔排序--------\n");
CopyList(L,T);
start_time = clock();
ShellSortA(T);
end_time = clock();
RunTime(end_time - start_time);
ShowList(T,sz);
printf("-------－教材上希尔排序---------\n");
CopyList(L,T);
int a[3] = {5,3,1};
start_time = clock();
ShellSort(T,a,3);
end_time = clock();
RunTime(end_time - start_time);
ShowList(T,sz);
printf("-------－简单插入排序-----------\n");
CopyList(L,T);
start_time = clock();
InsertSort(T);
end_time = clock();
RunTime(end_time - start_time);
ShowList(T,sz);
printf("-------－折半插入排序-----------\n");
CopyList(L,T);
start_time = clock();
BInsertSort(T);
end_time = clock();
RunTime(end_time - start_time);
ShowList(T,sz);
printf("-------－简单选择排序-----------\n");
CopyList(L,T);
start_time = clock();
SelectSort(T);
end_time = clock();
RunTime(end_time - start_time);
ShowList(T,sz);
printf("----------－冒泡排序------------\n");
CopyList(L,T);
start_time = clock();
BubbleSort(T);
end_time = clock();
RunTime(end_time - start_time);
ShowList(T,sz);
DeleteList(L);
DeleteList(T);
return TRUE;
}
//建立排序表
Status MenuList(SqList &L)
{
int size,kind,ct;
char sz = 'N',ch;
do
{
printf("请输入需要测试的数据个数(N>0): \n");
do
{
scanf("%d",&size);
}while(size<1&&printf("输入的数据个数小于1，请重新输入: \n"));
printf(" 输入测试类型值 : (0--随机数 1--正序 2--逆序) \n");
do{
scanf("%d",&kind);
}while(((kind>2)||(kind<0))&&(printf("类型值范围(0-2),请重新输入:\n")));
if(size<50000)
{
printf(" 是否显示排序结果(Y/N):\n");
do
{
scanf("%c",&sz);
} while((sz!= 'Y' && sz!= 'N' && sz != 'y' && sz!= 'n')&&(printf("请输入(Y or N):\n")));
}
else
printf("输出测试值太多( >50000 ),没有必要显示\n\n");
Display(L,size,sz,kind);
printf("\n是否继续？(Y/N)\n");
do{
scanf("%c",&ch);
} while((ch!= 'Y' && ch!= 'N' && ch != 'y' && ch!= 'n')&&(printf("请输入(Y or N):\n")));
if(ch == 'Y' || ch == 'y')
ct = TRUE;
else
ct = FALSE;
}while(ct == TRUE);
return TRUE;
}
int main()
{
SqList L;
MenuList(L
最新评论