4.cpp

分别实现直接插入排序、冒泡排序、简单选择排序、希尔排序、快速排序、堆排序

#include "iostream.h"
#include "stdlib.h"


const LIST_INIT_SIZE=100;
const LISTINCREMENT=10;
typedef struct{
	int key;
	char a;
}RcdType;
typedef struct{
  RcdType *r;
  int length;
  int listsize;
  int incrementsize;
  int move;
  int comp;
}SqList;


void InitList_sq(SqList &L,int maxsize=LIST_INIT_SIZE,int incresize=LISTINCREMENT)
{
	L.r=new RcdType[maxsize];
	L.length=0;
	L.listsize=maxsize;
	L.incrementsize=incresize;
	L.move=0;
	L.comp=0;
}

void  output(SqList &L)
{int i;
 for(i=1;i<=L.length;i++)
	 cout<<L.r[i].key<<"  "<<L.r[i].a<<"  ";
     cout<<"比较次数:"<<L.comp<<" 移动次数:"<<L.move<<endl;
}

void  copynumber(SqList &L1,SqList &L2)
{int i;
  for(i=1;i<=L1.length;i++)
	  L2.r[i]=L1.r[i];
  L2.length=L1.length;
  L2.comp=L1.comp;
  L2.move=L1.move;
}

void randcreat(SqList &L,int n)
{int i,R;
  for(i=1;i<=n;i++)
  {R=rand();
   L.r[i].key=R%100;
   L.r[i].a='A'+i;
   L.length++;
  }

}



void SelectSort (SqList &L) {
      // 对顺序表L作简单选择排序。
     RcdType  W;
	 int i,j,k;
     for (i=1; i<L.length; ++i) {              // 选择第i小的记录，并交换到位
        j = i;                        
        for ( k=i+1; k<=L.length; k++,L.comp++ )        // 在L.r[i..L.length]中选择key最小的记录
			if ( L.r[k].key < L.r[j].key )  j =k ;
		if ( i!=j )
		{ W=L.r[j];L.r[j] =L.r[i];L.r[i] = W;L.move +=3;}    // 与第i个记录交换
     }
} // SelectSort



void InsertSort ( SqList &L) {
      // 对顺序表L作插入排序
	int i,j;
      for ( i=2; i<=L.length; ++i,L.comp++ )
        if ( L.r[i].key < L.r[i-1].key ) {  // "<"时，才需将L.r[i]插入有序子表
          L.r[0] = L.r[i];                  // 复制为哨兵
          for ( j=i-1;  L.r[0].key < L.r[j].key;  --j,L.comp++,L.move++ )
            L.r[j+1] = L.r[j];              // 记录后移
          L.r[j+1] = L.r[0]; L.move++;               // 插入到正确位置
        } // if
} // InsertSort

void BubbleSort( SqList &L ){
    // 对顺序表L作起泡排序,
    RcdType  W;
	int lastExchangeIndex,i,j;
      i = L.length;
      while (i >1) {              // i>1 表明上一趟曾进行过记录的交换
        lastExchangeIndex = 1;
        for (j = 1; j < i; j++){
          if (L.r[j+1].key < L.r[j].key) { L.comp++;
            W=L.r[j];L.r[j] =L.r[j+1];L.r[j+1] = W;     // 互换记录
            lastExchangeIndex = j;    L.move+=3;
          } //if                      
        } //for
        i = lastExchangeIndex;   // 一趟排序中无序序列中最后一个记录的位置
      } // while
} // BubbleSort

int Partition ( RcdType R[], int low, int high) {
      // 对记录子序列R[low..high]进行一趟快速排序，并返回枢轴记录所在位置，
      // 使得在它之前的记录的关键字均不大于它的关键字，在它之后的记录的关键
      // 字均不小于它的关键字
      int pivotkey;
	  R[0] = R[low];  // 将枢轴记录移至数组的闲置分量
      pivotkey = R[low].key;    // 枢轴记录关键字
      while (low<high) {        // 从表的两端交替地向中间扫描
        while(low<high&& R[high].key>=pivotkey)
        --high;
	    R[low++] = R[high];     // 将比枢轴记录小的记录移到低端
        while (low<high && R[low].key<=pivotkey) 
        ++low;
		R[high--] = R[low];   // 将比枢轴记录大的记录移到高端
		
	  } //while
      R[low] = R[0];            // 枢轴记录移到正确位置
      return low;               // 返回枢轴位置
} // Partition

void QSort (RcdType R[],  int s,  int t ) {
       // 对记录序列R[s..t]进行快速排序
      int  pivotloc;
	  if (s < t-1) {                  // 长度大于1
         pivotloc = Partition(R, s, t);// 对 R[s..t] 进行一次划分，并返回枢轴位置
         QSort(R, s, pivotloc-1);      // 对低子序列递归排序
         QSort(R, pivotloc+1, t);      // 对高子序列递归排序
       } // if
} // Qsort

void QuickSort( SqList & L) {
      // 对顺序表 L 进行快速排序
       QSort(L.r, 1, L.length);
} // QuickSort

void Merge(RcdType SR[],RcdType TR[],int i,int m,int n)
{
	int j,k;
	for(j=m+1,k=i;i<=m && j<=n;++k)
	{
		if(SR[i].key<=SR[j].key)TR[k]=SR[i++];
		else TR[k]=SR[j++];
	}
	while(i<=m) TR[k++]=SR[i++];
			while(j<=n) TR[k++]=SR[j++];
}//merge

void MSort(RcdType SR[],RcdType TR1[],int s,int t)
{
	int m;
	TR1[t-s+1];
	if(s==t) TR1[s]=SR[s];
	else
	{
		SR[s]=TR1[s];
		m=(s+t)/2;
		MSort(SR,TR1,s,m);
		MSort(SR,TR1,m+1,t);
		Merge(TR1,SR,s,m,t);
	}
}//MSort

void MergeSort( SqList & L) {
      // 对顺序表 L 进行归并排序
       MSort(L.r,L.r,1, L.length);
} // MergeSort

void main()
{  SqList a,b;
int i,n;
cout<<"input n:";
cin>>n;
for(i=1;i<=3;i++)
{
InitList_sq(a);
InitList_sq(b);
randcreat(a,n);
output(a);
copynumber(a,b);
SelectSort(b);
output(b);
copynumber(a,b);
InsertSort(b);
output(b);
copynumber(a,b);
BubbleSort(b);
output(b);
copynumber(a,b);
QuickSort(b);
output(b);
copynumber(a,b);
MergeSort(b);
output(b);
cout<<endl;
}//for

}