#include <iostream>
#include <algorithm>
#define MAXSIZE 10000
#define OK 1
typedef int KeyType;
typedef char InfoType;
typedef int Status;
using namespace std;
typedef struct{
KeyType key;
InfoType otherinfo;
}RedType;
typedef struct{
RedType r[MAXSIZE+1];
int length;
}SqList;
Status InitList_Sq(SqList &L,int a[],int n)
{
L.length=n;
for(int i=1;i<=n;i++)
L.r[i].key=a[i];
return OK;
}
void ShowSqList(SqList L)
{
for (int i=1;i<=L.length;i++)
cout<<L.r[i].key<<" ";
cout<<endl;
}
//----------------快速排序-------------
int Partition(SqList &L ,int low,int high)
{
int pivotkey=L.r[low].key;
L.r[0]=L.r[low];
while(low<high)
{
while(low<high&&L.r[high].key>=pivotkey)
{
--high;
}
L.r[low]=L.r[high];
while(low<high&&L.r[low].key<=pivotkey)
{
++low;
}
L.r[high]=L.r[low];
}
L.r[low]=L.r[0];
for(int k=1;k<=L.length;k++)
cout<<" "<<L.r[k].key<<" ";
cout<<endl;
return low;
}
void QSort(SqList &L,int low,int high)
{
int pivotloc,j=0;
if(low<high)
{
pivotloc=Partition(L,low,high);
QSort(L,low,pivotloc-1);
QSort(L,pivotloc+1,high);
}
}
void Quicksort(SqList &L)
{
QSort(L,1,L.length);
}
//------------------堆排序-----------------
void HeapAdjust(SqList &L,int s,int m)
{
int j;
RedType rc=L.r[s];
for(j=2*s;j<=m;j*=2)
{
if(j<m&&L.r[j].key<L.r[j+1].key)
j++;
if(rc.key>=L.r[j].key)
break;
L.r[s]=L.r[j];
s=j;
}
L.r[s]=rc;
}
void CreatHeap(SqList &L)
{
for(int i=L.length/2;i>0;--i)
HeapAdjust(L,i,L.length);
}
void Heapsort(SqList &L)
{
CreatHeap(L);
for (int i=L.length;i>1;--i)
{
swap(L.r[1],L.r[i]);
HeapAdjust(L,1,i-1);
cout<<"第"<<L.length-i+1<<"趟重调整堆之后:";
for(int k=1;k<=L.length;k++)
cout<<" "<<L.r[k].key<<" ";
cout<<endl;
}
}
//---------------希尔排序------------
void ShellInsert(SqList &L,int dk)
{
int i,j;
for(i=dk+1;i<=L.length;i++)
if (L.r[i].key<L.r[i-dk].key)
{
L.r[0]=L.r[i];
for (j=i-dk;j>0&&L.r[0].key<L.r[j].key;j-=dk)
L.r[j+dk]=L.r[j];
L.r[j+dk]=L.r[0];
}
}
void Shellsort(SqList &L,int dt[],int t)
{
for(int i=0;i<t;i++){
ShellInsert(L,dt[i]);
cout<<i+1<<"趟排序结果：";
for(int k=1;k<=L.length;k++)
cout<<" "<<L.r[k].key<<" ";
cout<<endl;
}
}
//------------归并排序-----------
void Merge(RedType R[],RedType T[],int low,int mid,int high)
{
//将有序表R[low..mid]和R[mid+1..high]归并为有序表T[low..high]
int i=low,j=mid+1,k=low;
while(i<=mid&&j<=high){ //将R中记录由小到大地并入T中
if(R[i].key<=R[j].key) T[k++]=R[i++];
else T[k++]=R[j++];
}
while(i<=mid) //将剩余的R[low..mid]复制到T中
T[k++]=R[i++];
while(j<=high) //将剩余的R[j.high]复制到T中
T[k++]=R[j++];
} //Merge
int x=1;
void MSort(RedType R[],RedType T[],int low,int high)
{
//R[low..high]归并排序后放入T[low..high]中
int mid;
if(low==high) T[low]=R[low];
else{
RedType *S=new RedType[high];
mid=(low+high)/2;
MSort(R,S,low,mid);
MSort(R,S,mid+1,high);
Merge(S,T,low,mid,high);
cout<<"第"<<x++<<"步骤的结果：";
for(int l=low;l<=high;l++)
cout<<" "<<T[l].key<<" ";
cout<<endl;
}
}
void MergeSort(SqList &L) {
//对顺序表L做归并排序
MSort(L.r,L.r,1,L.length);
}
//-----------------基数排序RadixSorting-------------------------
#define MAX_NUM_OF_KEY 8 //关键字项数的最大值
#define RADIX 10 //关键字基数，此时是十进制整数的基数
#define MAX_SPACE 10000
typedef int DataType ;
typedef struct
{
int data; //数据
DataType keys[MAX_NUM_OF_KEY]; //每个数据的所有关键字
int next;
}SLCell; //静态链表的节点类型
typedef struct Sllist
{
SLCell *R; //静态链表的可利用空间，r[0]为头结点
int recnum; //静态链表的当前长度
int keynum; //当前数据的关键字个数
}Sllist, * SLList; //静态链表类型
typedef int ArrType[RADIX]; //指针数组类型，声明两个指针数组，一个头指针，一个尾指针
void creatList(SLList &SLL)
{
int key, i=1,j,n,t;
cout<<"═════请输入数的个数：";
cin>>n;
cout<<"═════输入要进行排序的数据:";
for(int k=0;k<n;k++)
{
cin>>key;
t=1;
SLL->R[i].data = key;
for(j = 1;j<10; j++)
{
SLL->R[i].keys[j] = key % 10;
key /= 10;
if(key!=0) t++;
}
SLL->R[i-1].next=i++;
if(SLL->keynum<t) SLL->keynum=t;
}
SLL->recnum = i-1;
SLL->R[SLL->recnum].next=0;
}
void print(SLList &SLL)
{
for(int p=SLL->R[0].next; p; p=SLL->R[p].next)
{
cout<<SLL->R[p].data<<" ";
}
cout<<endl;
}
void distribute(SLCell *R, int i, ArrType front, ArrType end)
{
//静态链表L的R域中记录已按(keys[0]...keys[i-1]有序)。
//本算法按第i个关键字keys[i]建立RADIX个子表，使同一子表中记录的keys[i]相同。
//front[0...RADIX-1]和end[0...RADIX-1]分别指向各子表中第一个和最后一个记录。
for(int j=0; j<RADIX; ++j)
front[j] = 0; //各子表初始化为空表
for(int p=R[0].next; p; p=R[p].next)
{
int j;
j=R[p].keys[i]; //映射第i个关键字
if(!front[j])
front[j] = p; //若front[j]为空，则把记录连接到front[j]的头指针上
else
R[end[j]].next = p; //若front[j]的头指针已经连接过了，说明已j为关键字的数据已经有了，
//这时把上一个以j为关键字的数据指向当前的这个数，即下标为p的数据
end[j] = p; //尾指针重新指到每次更新的数据上
}
}//distribute
void collect(SLCell *R, int i, ArrType front, ArrType end)
{
int j;
//本算法按keys[i]自小到大地将f[0...RADIX-1]所指各子表依次链接成为一个链表
for( j=0; !front[j]; j++); //找到第一个不为空的子表
R[0].next=front[j]; //重整静态链表
int k=end[j]; //k为当前子表的尾指针
while(j<RADIX)
{
for(++j; j<RADIX; j++)
if(front[j]) //找下一个非空子表
{
R[k].next=front[j]; //连接
k=end[j];
}
}
R[k].next=0; //k指向最后一个非空子表的尾指针
}//collect
void RadixSort(SLList &SLL){
ArrType front,end;
for(int i = 1; i <= SLL->keynum; i++) //对各关键字进行分配和收集
{
distribute(SLL->R, i,front,end); //第i趟分配
collect(SLL->R, i,front,end); //第i趟收集
cout<<"═════第"<<i<<"分配和收集:";
print(SLL);
}
}
/*---------------------------------------------------------------------------------*/
void ShellSort()
{
cout<<" ╔═════════════════════════════╗"<<endl;
cout<<" ║ 希尔排序 ShellSort ║"<<endl;
cout<<" ╚═════════════════════════════╝"<<endl;
int d[3]={5,3,1},R[MAXSIZE+1],n;
cout<<"═════请输入初始关键字个数:";
cin>>n;
cout<<"═════请输入"<<n<<"个数:";
for(int i=1;i<=n;i++) cin>>R[i];
cout<<"═════您输入的初始关键字序列为:";
for(int j=1;j<=n;j++){
cout<<R[j]<<" ";
}
cout<<endl;
SqList L;
cout<<"═════希尔排序的过程为："<<endl;
InitList_Sq(L,R,n);
Shellsort(L,d,3);
}
void QuickSort()
{
cout<<" ╔═════════════════════════════╗"<<endl;
cout<<" ║ 快速排序 QuickSort ║"<<endl;
cout<<" ╚═════════════════════════════╝"<<endl;
cout<<"═════参考数值：49 38 65 97 76 13 27 49"<<endl;
cout<<"═════第一趟：27 38 13 49 76 97 65 49"<<endl;
cout<<"═════第二趟：13 27 38 49 76 97 65 49"<<endl;
cout<<"═════第三趟：13 27 38 49 49 65 76 97"<<endl;
cout<<"═════第四趟：13 27 38 49 49 65 76 97"<<endl;
int d[3]={5,3,1},R[MAXSIZE+1],n;
cout<<"请输入初始关键字个数:";
cin>>n;
cout<<"═════请输入"<<n<<"个数:";
for(int i=1;i<=n;i++) cin>>R[i];
cout<<"═════您输入的初始关键字序列为:";
for(int j=1;j<=n;j++){
cout<<R[j]<<" ";
}
cout<<endl;
SqList L;
cout<<"═════快速排序的过程为："<<endl;
InitList_Sq(L,R,n);
Quicksort(L);
}
void HeapSort()
{
cout<<" ╔═════════════════════════════╗"<<endl;
cout<<" ║ 堆排序 HeapSort ║"<<endl;
cout<<" ╚═════════════════════════════╝"<<endl;
cout<<"═════参考数值：49 38 65 97 76 13 27 49"<<endl;
cout<<"═════第一趟：76 49 65 38 49 13 27 97"<<endl;
cout<<"═════第二趟：65 49 27 38 49 13 27 97"<<endl;
cout<<"═════第三趟：49 49 27 38 13 65 76 97"<<endl;
cout<<"═════第四趟：49 38 27 13 49 65 76 97"<<endl;
cout<<"═════第五趟：38 13 27 49 49 65 76 97"<<endl;
cout<<"═════第六趟：27 13 38 49 49 65 76 97"<<endl;
cout<<"═════第七趟：13 27 38 49 49 65 76 97"<<endl;
int d[3]={5,3,1},R[MAXSIZE+1],n;
cout<<"═════请输入初始关键字个数:";
cin>>n;
cout<<"═════请输入"<<n<<"个数:";
for(int i=1;i<=n;i++) cin>>R[i];
cout<<"═════您输入的初始关键字序列为:";
for(int j=1;j<=n;j++){
cout<<R[j]<<" ";
}
cout<<endl;
SqList L;
cout<<"═════堆排序的过程为："<<endl;
InitList_Sq(L,R,n);
Heapsort(L);
}
void MergingSort()
{
cout<<" ╔═════════════════════════════╗"<<endl;
cout<<" ║ 归并排序 MergingSort ║"<<endl;
cout<<" ╚═════════════════════════════╝"<<endl;
cout<<"═════参考数值：49 38 65 97 76 13 27"<<endl;
cout<<"═════第一趟：38 49"<<endl;
cout<<"═════第二趟：65 97"<<endl;
cout<<"═════第三趟：38 49 65 97"<<endl;
cout<<"═════第四趟：13 76"<<endl;
cout<<"═════第五趟：13 27 76"<<endl;
cout<<"═════第六趟：13 27 38 49 65 76 97"<<endl;
int d[3]={5,3,1},R[MAXSIZE+1],n;
cout<<"═════请输入初始关键字个数:";
cin>>n;
cout<<"═════请输入"<<n<<"个数:";
for(int i=1;i<=n;i++) cin>>R[i];
cout<<"═════您输入的初始关键字序列为:";
for(int j=1;j<=n;j++){
cout<<R[j]<<" ";
}
cout<<endl;
SqList L;
cout<<"═════归并排序的过程为："<<endl;
InitList_Sq(L,R,n);
MergeSort(L);
}
int RadixSorting()
{
cout<<" ╔═════════════════════════════╗"<<endl;
cout<<" ║ 基数排序 RadixSorting ║"<<endl;
cout<<" ╚═════════════════════════════╝"<<endl;
cout<<"═════参考数值：278 109 63 930 589 184 505 269 008 083"<<endl;
cout<<"═════第一趟：930 063 083 184 505 278 008 109 589 269"<<endl;
cout<<"═════第二趟：505 008 109 930 063 269 278 083 184 589"<<endl;
cout<<"═════第三趟：008 063 083 109 184 269 278 505 589 930"<<endl;
SLList SLL;
SLL=(SLList)malloc(MAX_SPACE*sizeof(Sllist));
SLL->R=(SLCell *)malloc(MAX_SPACE*sizeof(SLCell));
SLL->recnum=0;
creatList(SLL);
cout<<"═════排序前:";
print(SLL);
RadixSort(SLL);
return 0;
}