#ifndef SORTLIST_H
#define SORTLIST_H
#define MAXSIZE 40
#define LT(key1,key2) ((key1)<(key2))
typedef int KeyType;
typedef int* InfoType;
typedef struct
{
KeyType key;
InfoType otherinfo;
int next;//用于表插入排序法
}RedType;
typedef struct
{
RedType r[MAXSIZE+1];
int length;
}SortList;
//最暴力的插入算法，从排序表中不停的取出数据插入到已经排好序的数组中
//这里用了一个小技巧，把所有的操作都集中到了一个排序表中了
//还有这里的第0项不储存任何数据但是就不能说它没有作用，恰恰相反，它很有用，
//用了它可以减少一半的比较次数，
//他就是传说中的哨兵
//经过实验的检验载40个数据的排序表中他的比较次数和交换次数约为400-500次，且比较次数接近交换次数
//（如果不特别说明，下面的关于交换次数和比较次数的讨论都是针对40个数据的排序表，因为我在实验中设置的最大数据个数就是40ok？
void InsertSort(SortList &L,int *times,int *Changes)//直接插入排序
{
int i,j;
for(i=2;i<L.length;i++)
{
if(LT(L.r[i-1].key,L.r[i].key))//按〉号从左到右排序
{
L.r[0].key=L.r[i].key;//0号单元作哨兵
for(j=i-1;LT(L.r[j].key,L.r[0].key);j--,(*times)++)//注意这里要用change,应为key是指针，他的直不可靠
{
L.r[j+1].key=L.r[j].key;//key存的是指针，要实现交换，用*
(*Changes)++;//Change用于记录交换的次数，比较算法的性能,下同
}
L.r[j+1].key=L.r[0].key;
(*Changes)++;
}
(*times)++;//times用于记录交换的次数，比较算法的性能,下同
}
}
void BInsertSort(SortList &L,int *times,int *changes)//折半插入排序
{
int i=0,j=0;
int low=0,high=0;
int m=0;
for(i=2;i<L.length;i++)
{
L.r[0].key=L.r[i].key;
low=1;high=i-1;
while(low<=high)
{
m = (low+high)/2;
if(LT(L.r[m].key,L.r[0].key))high=m-1;//比较中点的值
else low = m+1;
(*times)++;
}
for(j=i-1;j>=high+1;j--)
{
L.r[j+1].key = L.r[j].key;//记录后移
(*changes)++;
}
L.r[high+1].key = L.r[0].key;//插入
(*changes)++;
}
}
void TLInsertSort(SortList &L,int *times,int *changes)//二路插入排序
{
int i,j,k;
int help[MAXSIZE+1];
help[0]=L.r[1].key;//将L.r[1]看成中间记录
help[MAXSIZE]=L.r[1].key;
int first=MAXSIZE;
int final=0;
for(i=2;i<L.length;i++)
{
if(LT(L.r[i].key,help[0]))//小于中间记录
{
for(j=final;LT(help[j],L.r[i].key);j--)
{
help[j+1]=help[j];//记录后移
(*changes)++;
(*times)++;
}
help[j+1]=L.r[i].key;//插入
final++;
}
else//大于中间记录
{
for(k=first;LT(L.r[i].key,help[k]);k++)
{
help[k-1]=help[k];//记录前移
(*changes)++;
(*times)++;
}
help[k-1]=L.r[i].key;//插入
first--;
}
(*times)+=2;
}
i=1;
for(j=first;j<MAXSIZE+1;j++)//重排记录
{
L.r[i].key = help[j];
i++;
}
for(j=1;j<=final;j++)
{
L.r[i].key = help[j];
i++;
}
}
#define MIN_INT -858993460
void TBInsertSort(SortList &L,int *times,int *changes)//表插入排序法
{
L.r[0].key=MIN_INT;
L.r[0].next=1;
L.r[1].next=0;//构建一个循环链表
int i;
int p=L.r[0].next;
int q=0;
for(i=2;i<L.length;i++)
{
p=L.r[0].next;
q=0;
while(LT(L.r[i].key,L.r[p].key))//寻找插入位置
{
q=p;
p=L.r[p].next;
(*times)++;
}
(*times)++;
L.r[i].next=L.r[q].next;
L.r[q].next=i;
}
//重排记录
int head=L.r[0].next;
int changedata;
for(i=1;i<L.length-1;i++)
{
while(head<i)head=L.r[head].next;
L.r[0].next=L.r[head].next;//0号单元保存链表头
if(head!=i)
{
changedata =L.r[i].key;
L.r[i].key =L.r[head].key;
L.r[head].key =changedata;
L.r[head].next=L.r[i].next;//交换数据
(*changes)++;
L.r[i].next=head;//指向被移走的记录的位置
}
head=L.r[0].next;//链表头下移
}
}
#undef MIN_INT
//shell's Sort
//对排序表作一趟Shell insert sort,dk是间隔
//对照直接插入排序，
void ShellInsertSort(SortList &L,int dk,int *times,int *changes)
{
int i,j;
for(i=dk+1;i<L.length;++i)
{
if(LT(L.r[i-dk].key,L.r[i].key))
{
L.r[0].key = L.r[i].key;
for(j=i-dk;j>0&<(L.r[j].key,L.r[0].key);j-=dk)
{
L.r[j+dk].key=L.r[j].key;//后移
(*times)++;(*changes)++;
}
L.r[j+dk].key=L.r[0].key;//插入
(*times)++;(*changes)++;
}
(*times)++;
}
}
// 按增量序列dk[]对排序表作Shell 排序
void ShellSort(SortList &L,int dk[],int t,int *times,int *changes)
{
int k;
for(k=0;k<t;k++)
{
ShellInsertSort(L,dk[k],times,changes);
}
}
//冒泡排序
void BubbleSort(SortList &L,int *times,int *changes)
{
int data;
for(int i=1;i<L.length-1;i++)
{
for(int j=i;j<L.length-1;j++)
{
if(LT(L.r[j].key,L.r[j+1].key))//如果后者大，交换
{
data=L.r[j+1].key;
L.r[j+1].key=L.r[j].key;
L.r[j].key=data;
(*times)++;
(*changes)++;
}
(*times)++;
}
}
}
//Quick Sort
//一趟quick sort
int Partition(SortList &L,int low,int high,int *times,int *changes)
{
L.r[0].key=L.r[low].key;
while(low<high)
{
while(!(LT(L.r[0].key,L.r[high].key)) && (low<high))
//注意这里，否则进入死循环,对相等的情况特殊处理
{
--high;
(*times)++;
}
L.r[low].key=L.r[high].key;
while((LT(L.r[0].key,L.r[low].key)) && (low<high))
{
low++;
(*times)++;
}
L.r[high].key=L.r[low].key;
(*times)+=2;
(*changes)+=2;
}
L.r[low].key=L.r[0].key;
return low;
}
//梯归的快速排序
void QSort(SortList &L,int low,int high,int *times,int *changes)
{
int pivotloc=0;
if(low<high)
{
pivotloc=Partition(L,low,high,times,changes);//找到分割点
QSort(L,low,pivotloc-1,times,changes);
QSort(L,pivotloc+1,high,times,changes);
}
}
void QuickSort(SortList &L,int *times,int *changes)
{
QSort(L,1,L.length-1,times,changes);
}
//下面的是选择排序，要有点耐心，因为有点难啊
//从最简单的开始 ，简单选择排序，不多说，bagin
void SimSelSort(SortList &L,int *times,int *changes)//Simple Selected Sorting
{
int i=0,j=0;
int max=0;
int max_offset=0;
for(i=1;i<L.length;i++)//选择第i大的元素让他排在第i 位 0号单元用于临时存储交换的数据
{
for(j=i+1;j<L.length;j++)//寻找i--L.length中最大的
{
if(LT(max,L.r[j].key))
{
max=L.r[j].key;
max_offset=j;
}
(*times)++;
}
if(max_offset>0)
{
L.r[max_offset].key=L.r[i].key;
L.r[i].key=max;//
(*changes)++;
}
}
}
//改进一下把，比较次数太多了
//竞标赛排序,数型选择排序
//首先来定义一棵树，用顺序结构
void TreeSelSort(SortList &L,int *times,int *changes)
{
}
//树排序实现起来比较麻烦，并且效率不会提高多少，我们还是放弃他把
//用堆排序是一个明智的选择
void HeapAdjust(SortList &L,int s,int m,int *times,int *changes)
//这个函数把L.r[s---m]的元素调整为一个小顶堆，保证除L.r[s]之外的元素已经是小顶堆
//否则会死的好难看
{
int j;
L.r[0].key=L.r[s].key;
for(j=2*s;j<=m;j*=2)
{
if(j<m&<(L.r[j+1].key,L.r[j].key))
{
++j;
}
(*times)+=2;
if(!LT(L.r[j].key,L.r[0].key))break;
L.r[s].key=L.r[j].key;
s=j;
(*changes)++;
}
L.r[s].key=L.r[0].key;
}
void HeapSort(SortList &L,int *times,int *changes)
{
int length=L.length-1;
int i;
for(i=length/2;i>0;--i)//把L.r[1---length-1]调整为小顶堆
//不用想了，length/2号元素就是最后一个非叶子节点了
{
HeapAdjust(L,i,length,times,changes);
}
for(i=length;i>1;--i)
{
L.r[0].key=L.r[1].key;
L.r[1].key=L.r[i].key;
L.r[i].key=L.r[0].key;
(*changes)++;
HeapAdjust(L,1,i-1,times,changes);//从新调整为小顶堆
}
}
//归并排序，将有序表组合成新的有序表，利用的是集合的思想
void Merge(RedType SR[],RedType *TR,int i,int m,int n)
//将SR[s---m]和SR[m+1---n]归并到ＴＲ[i----]
{
int j,k;
for(j=m+1,k=i;i<=m&&j<=n;k++)
{
if(LT(SR[i].key,SR[j].key))
TR[k].key=SR[j++].key;
else
TR[k].key=SR[i++].key;
}
}
void MSort(RedType SR[],RedType *TR1,int s,int t)
{
RedType *TR2;//TR2是辅助数组
int m;
TR2=(RedType *)malloc(sizeof(RedType)*(t-s+1));//分配空间
if(s==t)TR1[s].key=SR[s].key;
else
{
m=(s+t)/2;
MSort(SR,TR2,s,m);//将前半段归并
MSort(SR,TR2,m+1,t);//后半段归并
Merge(TR2,TR1,s,m,t);
}
free(TR2);//一定要记得释放
}
void MergeSort(SortList &L,int *times,int *changes)
{
MSort(L.r,&(L.r[0]),1,L.length-1);
}
#endif