数据结构

开发平台：
Visual C++

内部排序.txt：源码内容
							#define  MAXSIZE  8
#include<stdio.h>
#include<stdlib.h>
/*1. 输出函数
2.直接插入排序函数
3.希尔排序函数
4.冒泡排序函数
5.快速排序函数
6.简单选择排序函数
7.堆排序函数
8.归并排序函数
9.功能选择函数*/
typedef struct{
  int key;
  int otherinfo;
}RedType;
typedef struct{
  RedType r[MAXSIZE+1];
  int length;
}SqList,*Seq;
void Print(SqList L,int x)
{  int i;
   
   printf("第%d趟排序结果为:",x);
   for(i=1;i<9;i++)
    printf("%d ",L.r[i].key);
   puts("n");
}
//1
/*void Insert(SqList L)// 对顺序表 L 作直接插入排序
{ 
  int i,j;
  
  for(i=2;i<=L.length;++i)
  {
	  if(L.r[i].key<L.r[i-1].key)
	  {
	    L.r[0]=L.r[i];// 复制为监视哨
		for(j=i-1;L.r[0].key<L.r[j].key;--j)
			L.r[j+1]=L.r[j];// 记录后移
		L.r[j+1]=L.r[0];// 插入到正确位置
	  }
      Print(L,i-1);
  }
  printf(" 排序结束！n");
}
//2
Seq ShellInsert ( Seq s, int dk )//希尔排序
{
   int i,j;
   for ( i=dk+1; i<=s.length; ++i )
   {
      if ( s.r[i].key< s.r[i-dk].key)
	  {
        s.r[0] = s.r[i];            // 暂存在R[0]
        for (j=i-dk;j>0&&(s.r[0].key<s.r[j].key);j-=dk)
           s.r[j+dk] = s.r[j];  // 记录后移，查找插入位置
        s.r[j+dk] = s.r[0];                // 插入
	  } // if
   }
   return s;
} // ShellInsert
void ShellSort (SqList  L)
{   
	Seq l;
	int dlta[2]={3,1}; //增量为dlta[]的希尔排序
    int k;
	l=&L;
    for (k=0; k<2; ++k)
	{
         l=ShellInsert(l, dlta[k]);//一趟增量为dlta[k]的插入排序
		 Print(L,k+1);
	}
	printf(" 排序结束！n");
} // ShellSort
//3
void BubbleSort(SqList L)//冒泡排序
{
   int i=9,lastExc,j;
   RedType x;
   while (i >1) 
   { 
     lastExc = 1;
     for (j = 1;  j < i;  j++)
	 {
       if (L.r[j+1].key < L.r[j].key) 
	   { 
          x=L.r[j+1];//Swap
		  L.r[j+1]=L.r[j];
		  L.r[j]=x;
          lastExc = j;  //记下进行交换的记录位置
	   } //if
	   Print(L,j);
	 }
	 i = lastExc; 
   } // while
   printf(" 排序结束！n");
} // BubbleSort
//4
int Partition (Seq l, int low, int high)//快速排序
{
	int pivotkey;
    l->r[0] = l->r[low]; 
	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[low].key<=pivotkey) 
          ++ low;      // 从左向右搜索
       l->r[high] = l->r[low];
	}
    l->r[low] = l->r[0];    
	return low;
}// Partition         
void QSort (SqList L,  int s,  int  t ,int i) // 对记录序列r[s..t]进行快速排序
{
  Seq l;
  int pivotloc;
  
  l=&L;
  if (s < t) // 长度大于1
  {             
    pivotloc = Partition(l, s, t); // 对 R[s..t] 进行一次划分
    QSort(L, s, pivotloc-1,i);
	Print(L,i++);
    QSort(L, pivotloc+1, t,i); 
  }
} // QSort
//5
void Select(SqList L) // 对记录序列R[1..n]作简单选择排序
{ 
  int i,j,k=1;
  RedType s;
   
  for (i=1; i<8; ++i)
  { 
	  for(j=i+1;j<=8;j++)
	     if(L.r[j].key<L.r[j-1].key)  k=j;// 在 R[i..n] 中选择关键字最小的记录
      if(i!=k)            // R[i]←→R[k]; 与第 i 个记录交换
	  {
	     s=L.r[i];
		 L.r[i]=L.r[k];  
		 L.r[k]=s;
	  }
	  Print(L,i);
  }
} // Select
//6
void HeapAdjust (Seq l, int s, int m)//建大顶堆
{   
  RedType rc;
  rc = l->r[s];    // 暂存 R[s] 
  for ( j=2*s; j<=m; j*=2 )
  { // j 初值指向左孩子
    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; // 将调整前的堆顶记录插入到 s 位置
} // HeapAdjust
void HeapSort ( SqList L)// 对顺序表 L进行堆排序
{
  int i,j=1;
  Seq l;
  SqList s;
  for ( i=L.length/2;   i>0;   --i )
     HeapAdjust ( l, i, L.length );    // 建大顶堆
  for ( i=L.length; i>1; --i ) 
  {
     s=L.r[i];// H.r[1]←→H.r[i];
	 L.r[i]=L.r[1];
	 L.r[1]=s;
	 Print(L,j++);
     HeapAdjust(l, 1, i-1);  // 对 H.r[1] 进行筛选
  }
} // HeapSort*/
 
//7归并排序
void Merge (RedType SR[], RedType TR[],int i, int m, int n) 
{// 将有序的记录序列 SR[i..m] 和 SR[m+1..n]归并为有序的记录序列 TR[i..n]
  int k,j;
  for (j=m+1, k=i;  i<=m && j<=n;  ++k)   
  {                   // 将SR中记录由小到大地并入TR
    if (SR[i].key<SR[j].key)  TR[k] = SR[i++];
    else TR[k] = SR[j++];
  }
  if (i<=m) TR[k++] = SR[i++];// 将剩余的 SR[i..m] 复制到 TR
  if (j<=n) TR[k++] = SR[j++];// 将剩余的 SR[j..n] 复制到 TR
} // Merge
void Msort ( RedType SR[],RedType TR1[], int s, int t /*,SqList S,int i*/) 
{// 将SR[s..t] 归并排序为 TR1[s..t]
	int m,i;
    if(s==t)   TR1[s]=SR[s];
    else 
      {
       m = (s+t)/2;
       Msort (SR,TR1,s,m); // 递归地将SR[s..m]归并为有序的TR2[s..m]
       Msort (SR,TR1,m+1,t);
       Merge (SR,TR1,s,m,t);
	   for(i=1;i<9;i++)
         printf("%d ",TR1[i].key);
       puts("n");
	  // Print(S,i++);
      }
} // Msort
void MergeSort (SqList L) 
{// 对顺序表 L 作2-路归并排序
  SqList S;
  int i=1,j;
  for(j=1;j<9;j++)  S.r[j].key=0;//L.r[j].key;
  Msort(L.r, S.r,1, L.length);
} // MergeSort
//k={ 12 , 45 , 21 , 12 , 30 , 2 , 68 , 33 }
void main()
{
	int quick[9];
    int i;
	SqList L;
/*	SqList s;//辅助顺序存储数组
	Seq  l;*/
	printf("请输入8个整数：");
	for(i=1;i<9;i++)    scanf("%d",&quick[i]);
	printf("n输入的8个整数为：n");
	for(i=1;i<9;i++)
	{
	  L.r[i].key=quick[i];
      printf("%d ",quick[i]);
	}
	puts("n");
	L.length=i-1;
//	Insert(L);
   // QSort(L,1,8,1);
    MergeSort (L) ;
}

						