// _DataStructure_C_Impl:Sort#include
     
      #include
      
       #define MaxSize 50typedef int KeyType;//数据元素类型定义typedef struct{	KeyType key;	//keyword}DataType;//顺序表类型定义typedef struct{	DataType data[MaxSize];	int length;}SqList;//---------------------------------------------//直接插入排序void InsertSort(SqList *L){	int i,j;	DataType t;	for(i=1;i
       
        length;i++){		//前i个元素已经有序，从第i+1个元素開始与前i个的有序的keyword比較		t=L->data[i+1];		//取出当前待排序的元素		j=i;		while(j>-1&&t.key
        
         data[j].key){		//找当前元素的合适位置			L->data[j+1]=L->data[j];			j--;		}		L->data[j+1]=t;		//将当前元素插入合适的位置	}}//---------------------------------------------//折半插入排序void BinInsertSort(SqList *L){	int i,j,mid,low,high;	DataType t;	for(i=1;i
         
          length;i++){		//前i个元素已经有序，从第i+1个元素開始与前i个的有序的keyword比較		t=L->data[i+1];		//取出第i+1个元素。即待排序的元素		low=1;		high=i;		while(low<=high){		//利用折半查找思想寻找当前元素的合适位置			mid=(low+high)/2;			if(L->data[mid].key>t.key)				high=mid-1;			else				low=mid+1;		}		for(j=i;j>=low;j--)		//移动元素，空出要插入的位置			L->data[j+1]=L->data[j];		L->data[low]=t;	//将当前元素插入合适的位置	}}//---------------------------------------------//对顺序表L进行一次希尔排序，delta是增量void ShellInsert(SqList *L,int delta){	int i,j;	DataType t;	for(i=delta+1;i<=L->length;i++){	//将距离为delta的元素作为一个子序列进行排序		if(L->data[i].key
          
           data[i-delta].key){ //假设后者小于前者，则须要移动元素 t=L->data[i]; for(j=i-delta;j>0&&t.key
           
            data[j].key;j=j-delta) L->data[j+delta]=L->data[j]; L->data[j+delta]=t; //依次将元素插入到正确的位置 } }}//希尔排序。每次调用算法ShellInsert,delta是存放增量的数组void ShellInsertSort(SqList *L,int delta[],int m){ int i; for(i=0;i
            
             0){ ShellInsert(L,gap); gap/=2; }}//---------------------------------------------//简单选择排序void SelectSort(SqList *L,int n){ int i,j,k; DataType t; //将第i个元素的keyword与后面[i+1...n]个元素的keyword比較，将keyword最小的的元素放在第i个位置 for(i=1;i<=n-1;i++){ k=i; for(j=i+1;j<=n;j++) //keyword最小的元素的序号为k if(L->data[j].key
             
              data[k].key) k=j; if(k!=i){ //假设序号i不等于k，则须要将序号i和序号k的元素交换 t=L->data[i]; L->data[i]=L->data[k]; L->data[k]=t; } }}//---------------------------------------------//调整H.data[s...m]的keyword，使其成为一个大顶堆void AdjustHeap(SqList *H,int s,int m){ DataType t; int j; t=(*H).data[s]; //将根结点临时保存在t中 for(j=2*s;j<=m;j*=2){ if(j
              
               <(*H).data[j+1].key) //沿keyword较大的孩子结点向下筛选 j++; //j为keyword较大的结点的下标 if(t.key>(*H).data[j].key) //假设孩子结点的值小于根结点的值，则不进行交换 break; (*H).data[s]=(*H).data[j]; s=j; } (*H).data[s]=t; //将根结点的值插入到正确位置}//建立大顶堆void CreateHeap(SqList *H,int n){ int i; for(i=n/2;i>=1;i--) //从序号n/2開始建立大顶堆 AdjustHeap(H,i,n);}//对顺序表H进行堆排序void HeapSort(SqList *H){ DataType t; int i; CreateHeap(H,H->length); //创建堆 for(i=(*H).length;i>1;i--){ //将堆顶元素与最后一个元素交换。又一次调整堆 t=(*H).data[1]; (*H).data[1]=(*H).data[i]; (*H).data[i]=t; AdjustHeap(H,1,i-1); //将(*H).data[1..i-1]调整为大顶堆 }}//---------------------------------------------//输出表中的元素void DispList3(SqList L,int count){ int i; printf("第%d趟排序结果:",count); for(i=1;i<=L.length;i++) printf("%4d",L.data[i].key); printf("\n");}//冒泡排序void BubbleSort(SqList *L,int n){ int i,j,flag=1; DataType t; static int count=1; for(i=1;i<=n-1&&flag;i++){ //须要进行n-1趟排序 flag=0; //标志位。若以有序，不须要进行以下的排序 for(j=1;j<=n-i;j++) //每一趟排序须要比較n-i次 if(L->data[j].key>L->data[j+1].key){ t=L->data[j]; L->data[j]=L->data[j+1]; L->data[j+1]=t; flag=1; } DispList3(*L,count); count++; }}//---------------------------------------------/*对顺序表L.r[low..high]的元素进行一趟排序，使枢轴前面的元素keyword小于枢轴元素的keyword，枢轴后面的元素keyword大于等于枢轴元素的keyword。并返回枢轴位置*/int Partition(SqList *L,int low,int high){ DataType t; KeyType pivotkey; pivotkey=(*L).data[low].key; //将表的第一个元素作为枢轴元素 t=(*L).data[low]; while(low
               
                =pivotkey) //从表的末端向前扫描 high--; if(low
                
                 data[k]=a[i]; } L->length=n;}//---------------------------------------------//顺序表的初始化void InitSeqList(SqList *L,DataType a[],int n){ int i; for(i=1;i<=n;i++) { L->data[i]=a[i-1]; } L->length=n;}//输出表中的元素void DispList(SqList L){ int i; for(i=1;i<=L.length;i++) printf("%4d",L.data[i].key); printf("\n");}void main(){ DataType a[]={56,22,67,32,59,12,89,26,48,37}; int delta[]={5,3,1}; int gap=5; int i,n=10,m=3; SqList L; printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n"); /*直接插入排序*/ InitSeqList(&L,a,n); printf("排序前："); DispList(L); InsertSort(&L); printf("直接插入排序结果："); DispList(L); printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n"); /*折半插入排序*/ InitSeqList(&L,a,n); printf("排序前："); DispList(L); BinInsertSort(&L); printf("折半插入排序结果："); DispList(L); printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n"); /*希尔排序*/ InitSeqList(&L,a,n); printf("排序前："); DispList(L); ShellInsertSort(&L,delta,m); printf("希尔排序结果："); DispList(L); printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n"); /*希尔排序*/ InitSeqList(&L,a,n); printf("排序前："); DispList(L); ShellInsertSort2(&L,gap); printf("希尔排序2结果："); DispList(L); printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n"); /*简单选择排序*/ InitSeqList(&L,a,n); printf("排序前："); DispList(L); SelectSort(&L,n); printf("简单选择排序结果："); DispList(L); printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n"); /*堆排序*/ InitSeqList(&L,a,n); printf("排序前："); DispList(L); HeapSort(&L); printf("堆排序结果："); DispList(L); printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n"); DataType b[]={37,22,43,32,19,12,89,26,48,92}; /*冒泡排序*/ InitSeqList(&L,b,n); printf("冒泡排序前："); DispList(L); BubbleSort(&L,n); printf("冒泡排序结果："); DispList(L); printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n"); /*高速排序*/ InitSeqList(&L,b,n); printf("高速排序前："); DispList(L); QuickSort(&L); printf("高速排序结果："); DispList(L); printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n"); /*归并排序*/ DataType c[MaxSize]; InitSeqList(&L,b,n); /*将数组a[0...n-1]初始化为顺序表L*/ printf("归并排序前："); DispList(L); MergeSort(L.data,c,1,n); InitSeqList1(&L,c,1,n); /*将数组c[1...n]初始化为顺序表L*/ printf("归并排序结果："); DispList(L); printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n"); system("pause");}