【文件属性】：
文件名称：各种排序 冒泡 快速 堆 希尔 基数等九种
文件大小：256KB
文件格式：7Z
更新时间：2013-06-17 14:08:15
各种排序 冒泡 快速 堆 插入
#include
#include
#define MAXSIZE 10
#define MAX_BIT 8 // 关键字最大位数
#define RADIX 10 // 关键字基数 ，此时是十进制整数的基数
#define MAX_SPACE 8 // 分配的存储空间的大小
typedef char KeyType;// define the keyType is the int
typedef int InfoType;
typedef struct
{
KeyType key;
InfoType otherinfo;// 其他数据项
}RedType;
typedef struct
{
RedType r[MAXSIZE+1];// r[0] is for the guard
int length;
}SqList;
// Radix Sorting
struct SLNode
{
KeyType key[MAX_BIT]; // the key
InfoType otheritems; // 其他数据项
int next; //下一个节点的下标位置
}; // 静态链表中的节点类型
struct SList
{
struct SLNode r[MAX_SPACE]; // 静态链表中各节点，其中r[0]为头结点
int keybit; // 关键字的位数
int recnum; // 静态链表中记录的个数
}; // 静态链表的类型
// 函数声明
void Insert_Sort ( SqList &L);// the Straight Insertion Sort
void BInsert_Sort(SqList &L);// the Binary Insertion Sort
void Shell_Sort(SqList &L);// Shell Sort
int Partition ( SqList &L,int low,int high );
void Quick_Sort(SqList &L,int low,int high);// Quick Sort
void Bubble_Sort(SqList &L);
void Select_Sort( SqList &L);
void Heap_Sort(SqList &L);
void Merge_Sort(SqList &L);// Merging Sort
void display(SqList L);// 输出显示
void main()
{
SqList L;
L.length=MAXSIZE;
int i,msg;
char ch;
do
{
system("cls"); // 清屏
cout<<"please input the data:"<>L.r[i].key;
}
cout<<"1、直接插入排序"<<"\t";
cout<<"2、折半插入排序"<>msg;
switch (msg)
{
case 1:
Insert_Sort(L);
display(L);
break;
case 2:
BInsert_Sort(L);
display(L);
break;
case 3:
Shell_Sort(L);
display(L);
break;
case 4:
Bubble_Sort(L);
display(L);
break;
case 5:
Quick_Sort(L,1,L.length);
display(L);
break;
case 6:
Select_Sort(L);
display(L);
break;
case 7:
Heap_Sort(L);
display(L);
break;
case 8:
Merge_Sort(L);
display(L);
break;
default:
cout<<"please input 1至 8"<>msg;
}
cout<<"do you want to continue !(y or n):";
cin>>ch;
} while(ch=='Y'||ch=='y');
}
// 直接插入排序
void Insert_Sort(SqList &L)
{
int i,j;
for (i=2; i<=L.length; i++)
{
if (L.r[i].key=high+1; --j)
{
L.r[j+1]=L.r[j];
}
L.r[high+1] = L.r[0]; // insert it
}
}
// 希尔排序
void Shell_Sort(SqList &L)// the ascending order
{
int d = L.length,i;
while ( d>=1 )
{
d=d/2;
for (i = 1+d; i<=L.length; i++)
if (L.r[i].key < L.r[i-d].key)
{
L.r[0]=L.r[i];
for (int j=i-d; j>0&&L.r[0].key =pivotkey)
{
high--;
}
L.r[low]=L.r[high];// while(False)
while (lowL.r[j+1].key)
{
L.r[0]=L.r[j+1];
L.r[j+1]=L.r[j];
L.r[j]=L.r[0];
flag=1;
}
}
i++;
}
}
void Select_Sort( SqList &L)// 直接选择排序
{
int i,j,min;
for (i=1; i<= L.length; i++)
{
min=i;
for (j=i+1; j<=L.length; j++)
{
if (L.r[min].key>L.r[j].key)
{
min=j;
}
}
if (min!=i)
{
L.r[0]=L.r[i];
L.r[i]=L.r[min];
L.r[min]=L.r[0];
}
}
}
void Heap_Adjust(SqList &L,int s, int m)// 堆调整
{
// 在L.r[s...m]中记录的关键字除L.r[s].key 之外均满足堆的定义，本函数调整L.r[s]的关键字，使L.r[s...m]成为一个大顶堆
int j;
L.r[0]=L.r[s];
for ( j=2*s; j<=m; j*=2 )
{
// 沿key较大的孩子节点向下筛选
if (j=L.r[j].key)
{
break;
}
else// 将三者中的最大值放入到根节点的位置，并用s记录此位置
{
L.r[s]=L.r[j];
s=j;
}
}
L.r[s]=L.r[0];
}
void Heap_Sort(SqList &L) // 堆排序
{
int i;
for (i=L.length/2; i>0; i--)// build the heap
{
Heap_Adjust(L,i,L.length);
}
for (i=L.length; i>1; i--)
{
L.r[0]=L.r[i];// 将 堆顶记录和当前未经排序子队列（1——i）中 的 最后一个记录 交换
L.r[i]=L.r[1];
L.r[1]=L.r[0];
Heap_Adjust(L,1,i-1);// 将（1——i-1）重新调整为一个大堆
}
}
void Merge( RedType S[], RedType T[], int i,int m,int n)
{
// 将有序的S前一部分和后一部分归并为有序的T
int j,k;
for (j=m+1,k=i;i<=m && j<=n; ++k)// 将S中记录由小到大并入到T中
{
if (S[i].key<=S[j].key)
{
T[k]=S[i++];
}
else
T[k] = S[j++];
}
while(i<=m)// 将剩余的S[i...m]复制到T中
T[k++]=S[i++];
while(j<=n)// 将剩余的S[j...n]复制到T
T[k++]=S[j++];
}
void MSort(RedType S[],RedType T1[],int s,int t )
{
// 将S[s...t]归并为T[s...t]MAXSIZE+1
RedType T2[MAXSIZE+1];
int m;
if ( s==t )// 只有一个记录
{
T1[s] = S[s];
}
else
{
m=(s+t)/2; // 将S 分为2份
MSort(S,T2,s,m);// 将S归并为有序的T2
MSort(S,T2,m+1,t); // 将S归并为有序的T2
Merge(T2, T1,s,m,t); // 将T1和T2归并到T1中
}
}
void Merge_Sort(SqList &L)// 归并排序
{
// 对顺序表L作归并排序
MSort(L.r,L.r,1,L.length);
}
// for Radix Sorting
// 基数排序中一趟分配的算法
void Distribute (SLNode *r,int i,int f[RADIX],int e[RADIX])
{
// 静态链表中的r域中记录已按key[0]——key[i-1]有序
// 本算法按关键字的第i位建立RADIX个链队列，使在同一链队列中关键字的第i位的数值相等；
// f、e均为长度为RADIX的指针数组,分别指向各链队列的第一条和最后一条记录
int j,p;
for (j=0; j
【文件预览】：
sort
----说明.doc(29KB)
----sort.dsp(4KB)
----sort.cpp(9KB)
----sort.ncb(57KB)
----sort.plg(877B)
----Debug()
--------vc60.pdb(68KB)
--------sort.obj(23KB)
--------sort.pdb(593KB)
--------sort.exe(244KB)
----sort.dsw(516B)
----sort.opt(53KB)
基数
----分工.ncb(49KB)
----fg.cpp(1KB)
----分工.plg(683B)
----分工.dsw(516B)
----分工.opt(53KB)
----Debug()
--------vc60.pdb(60KB)
--------分工.exe(208KB)
--------分工.pdb(513KB)
--------fg.obj(9KB)
----分工.dsp(4KB)
