/*********************************************************************************************
*******************************
*姓名： 杨刚 *
*学号： 040640316 *
*最终完成时间： 2007年1月8日" *
*******************************
/********************************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<time.h>//此头文件用于统计排序的所用时间
#include"math.h"//此头文件用于产生随机函数
typedef long clock_t;
#define MAXSIZE 30000
typedef int KeyType;
//定义关键字的结构
typedef struct
{
KeyType key;
}RedType;
//定义线性表的结构
typedef struct
{
RedType r[MAXSIZE+1];
int length;
}SqList;
//用于打印的函数
void PrintSq(SqList L)
{
int i;
printf("输出比较结果为：\n");
for(i=1;i<=L.length;i++)
{
printf("%8d",L.r[i].key);
if(i%10==0)
printf("\n");
}
}
//用于比较的函数
int LT(SqList L,int i,int j)
{
if(L.r[i].key<L.r[j].key)
return 1;
else
return 0;
}
//用于交换的函数
void Change(SqList &L,int i,int j)
{ int temp;
temp=L.r[i].key;
L.r[i].key=L.r[j].key;
L.r[j].key=temp;
}
//1.插入排序
void InsertSort(SqList &L)
{
for(int i=2;i<=L.length;++i)
if(LT(L,i,i-1))
{
L.r[0]=L.r[i]; //复制为哨兵
L.r[i]=L.r[i-1];
for(int j = i-2;LT(L,0,j); --j)
{
L.r[j+1]= L.r[j];//记录后移
}
L.r[j+1]=L.r[0];//插入
}
PrintSq( L);
}//InsertSort
//2.折半插入排序
void BInsertSort(SqList &L)
{
int low,high,mid;
for(int i=2;i<=L.length ;++i)
{
L.r[0]=L.r[i]; //将L.r[i]暂存在L.r[0]
low = 1;
high = i-1;
while(low<=high)
{
//在r[low..high]中折半查找有序插入的位置
mid = (low+high)/2;
if(LT(L,0,mid))
high = mid - 1;//插入在低半区
else
low = mid + 1;//插入在高半区
}//while
for(int j=i-1;j>=high+1;--j)
L.r[j+1]= L.r[j];//记录后移
L.r[high+1]=L.r[0]; //插入
}//for
PrintSq( L);
}//BInsertSort
//3.起泡排序
void BubbleSort(SqList &L)
{
int i,j;
for(j=1;j<=L.length-1;j++)
{
for(i=1;i<=L.length-j;i++)
if(LT(L,i+1,i))
{
Change(L,i+1,i);
}
}
PrintSq( L);
}//BubbleSort
//4.快速排序
int Partition(SqList &L,int low,int high)
{
//交换顺序表l中子表r[low..high]的记录，枢轴记录到位，并返回其所在位置
//此时在它之前（后）的记录均不大（小）于它
L.r[0] = L.r[low];
int pivotkey = L.r[low].key;
while(low<high)
{
while(low<high && L.r[high].key>=pivotkey)
--high; //从表的两端交替的向中间扫描
L.r[low] = L.r[high]; //将比枢轴小的前移
while(low<high&&L.r[high].key<=pivotkey)
++low;
L.r[high] = L.r[low];//将比枢轴大的后移
}
L.r[low] = L.r[0];//记录枢轴到位
return low;//返回枢轴位置
}
void Qsort(SqList &L,int low,int high)
{
//对顺序表l中的子序列l.r[low..high]作快速排序
if(low<high)
{
int pivotkey = Partition(L, low, high);
Qsort(L, low,pivotkey-1);
Qsort(L,pivotkey+1,high);
}
//PrintSq( L);
}//Qsort
//5.简单选择排序
int SelectMinKey(SqList &L , int k)
{
//对顺序表l作选择排序
int i;
for(i=k;i<=L.length;i++)
{
if(LT(L,i,k))
k=i;
}
return k;
}//SelectMinKey
void SelectSort(SqList &L)
{
int j;
for(int i=1;i<L.length;++i) //选择第i小的记录，并交换到位
{
j=SelectMinKey(L,i); //在r[i..L.length]中选择Key最小的记录
if(i!=j)
Change(L,i,j); //与第i个记录交换
}
PrintSq( L);
}//SelectSort
//6.堆排序
typedef SqList HeapType;
void HeapAdjust(HeapType &L,int s,int m)
{
//Shift(L,0,s);
RedType rc=L.r[s];
for(int j=2*s;j<=m;j*=2)
{
if(j<m&<(L,j,j+1))//沿key较大的孩子结点向下筛选
++j; //j为key较大的记录的下标
if(!LT(L,0,j))
break; //rc应插在位置s上
s=j;
}
L.r[s]=rc;//插入
}//HeapAdjust
void HeapSort(HeapType &L)
{
//对顺序表l进行排序
for(int i = L.length/2;i>0;--i)
HeapAdjust(L,i,L.length);
for(i = L.length ; i>1;--i)
{
Change(L,1,i);
HeapAdjust(L,1,i-1);
}
PrintSq( L);
}//HeapSort
//7.基数排序
//定义新的数据类型
#define MAX_NUM_OF_KEY 4 //关键字项数的最大值
#define MAX_SPACE 10000
typedef struct
{
int keys[MAX_NUM_OF_KEY]; //关键字
int next;
}SLCell;//静态链表的结点类型
typedef struct
{
SLCell r[MAX_SPACE]; //静态链表的可利用空间，r[0]为头结点
int keynum; //记录的当前关键字个数
int recnum; //静态链表的长度
}SLList; //静态链表的类型
typedef int ArrType[10]; //指针数组类型
//change函数
void change(int a,int keys[4])
{
//本函数用于将int to int[4]
keys[0]=a/1000;a-=keys[0]*1000;
keys[1]=a/100; a-=keys[1]*100;
keys[2]=a/10; a-=keys[2]*10;
keys[3]=a;
}
int Change(int &a,int keys[4])
{
a=0;
a+=keys[0]*1000;
a+=keys[1]*100;
a+=keys[2]*10;
a+=keys[3];
return a;
}
//SWAP函数
//用于将L.r[i]与L.r[j]交换，借助中间变量L.r[0]
void SWAP(int i,int j,SLList &L){
SLCell temp;
int shiftcount;
shiftcount+=3; //移动次数加3
temp=L.r[j];
L.r[j]=L.r[i];
L.r[i]=temp;
}//SWAP
void Arrange(SLList &SL)
{
// 根据静态链表SL中各结点的指针值调整记录位置，
// 使得SL中记录按关键字非递减有序顺序排列
int i;
int p,q;
p = SL.r[0].next; // p指示第一个记录的当前位置
for (i=1; i<SL.recnum; ++i) {
// SL.r[1..i-1]中记录已按关键字有序排列，
// 第i个记录在SL中的当前位置应不小于i
while (p<i) // 找到第i个记录，并用p指示其在SL中当前位置
p = SL.r[p].next;
q = SL.r[p].next; // q指示尚未调整的表尾
if (p!= i) {
SWAP(i,p,SL);
SL.r[i].next=p; // 指向被移走的记录，使得以后可由while循环找回
}
p=q; // p指示尚未调整的表尾，为找第i+1个记录作准备
}
} // Arrange
void Distribute(SLList &L, int i, ArrType &f, ArrType &e) {
// 静态链表L的r域中记录已按(keys[0],...,keys[i-1])有序，
// 本算法按第i个关键字keys[i]建立RADIX个子表，
// 使同一子表中记录的keys[i]相同。f[0..RADIX-1]和e[0..RADIX-1]
// 分别指向各子表中第一个和最后一个记录
int j, p;
for (j=0; j<10; ++j)
{// 各子表初始化为空表
f[j] = 0;e[j]=0;
}
for (p=L.r[0].next; p; p=L.r[p].next)
{
j = L.r[p].keys[i]; // 将记录中第i个关键字映射到[0..RADIX-1]
if (!f[j])
{ f[j] = p;
e[j] = p;
}
else
{ L.r[e[j]].next=p;
e[j]=p; // 将p所指的结点插入第j个子表中
}
}
} // Distribute
void Collect(SLList &L, int i, ArrType f, ArrType e)
{
// 本算法按keys[i]自小至大地将f[0..RADIX-1]所指各子表依次链接成
// 一个链表，e[0..RADIX-1]为各子表的尾指针
int j,t;
for (j=0; !f[j]; j++); // 找第一个非空子表，succ为求后继函数: ++
L.r[0].next = f[j]; // L.r[0].next指向第一个非空子表中第一个结点
t = e[j];
while (j<10){
for (j=j+1; j<10 && !f[j]; j++); // 找下一个非空子表
if (j<10) // 链接两个非空子表
{ L.r[t].next = f[j]; t = e[j]; }
}
L.r[t].next = 0; // t指向最后一个非空子表中的最后一个结点
// printSL(L);
} // Collect
void RadixSort(SLList &L)
{
// L是采用静态链表表示的顺序表。
// 对L作基数排序，使得L成为按关键字自小到大的有序静态链表，
// L.r[0]为头结点。
int i;
ArrType f, e;
for (i=1; i<L.recnum; ++i) L.r[i-1].next = i;
L.r[L.recnum-1].next = 0; // 将L改造为静态链表
for (i=3; i>=0; i--)
{
// 按最低位优先依次对各关键字进行分配和收集
Distribute(L, i, f, e); // 第i趟分配
Collect(L, i, f, e); // 第i趟收集
}
Arrange(L); //调整L中记录，使按关键字非递减有序顺序排列
} // RadixSort
//printSL函数
//用于打印排序后的静态表
void printsSL(SLLi
