问题描述 

1) 动态输入一组数字序列;

2)实现直接插入排序、简单选择排序、冒泡排序、快速排序算法;

3)在主函数中，依次测试上述算法。

类型定义

#define MAX SIZE 100
typedef int KeyType ;
typedef struct RecType
{ KeyType key ;/*关键字码*/infoType otherinfo; /* 其他域*/
} RecType ;
typedef struct SqList 
{     RecType R[MAX_ _SIZE+1]; //R[0]闲置或作哨兵单元int length ;
}SqList ;

 解决方案

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
#define MAX_STACK 100
#define TRUE 0
#define FALSE -1
typedef int KeyType;
typedef struct{KeyType key;
}RedType;
typedef struct{RedType r[MAXSIZE+1];int length;
}SqList;void InitList_Sq(SqList &L)
{int i;L.length = 0;printf("请依次输入顺序表值，以333结束:\n");for (i = 1; i < MAXSIZE; i++) {scanf("%d", &(L.r[i].key));L.length++;if(L.r[i].key==333)break;}
}void straight_insert_sort(SqList &L)    //直接插入排序
{int i, j ;for (i=2; i<=L.length; i++){ L.r[0]=L.r[i]; j=i-1; /* 设置哨兵 */while( L.r[i].key<L.r[j].key){ L.r[j+1]=L.r[j];j--;} /* 查找插入位置 */L.r[j+1]=L.r[0]; /* 插入到相应位置 */ } }void simple_selection_sort(SqList &L)   //简单选择排序
{ int m, n,k;for (m=1; m<L.length; m++){ k=m ; for (n=m+1; n<=L.length; n++)if (L.r[n].key<L.r[k].key) k=n;if (k!=m) /* 记录交换 */{L.r[0]=L.r[m]; L.r[m]=L.r[k];L.r[k]=L.r[0];} } 
}void Bubble_Sort(SqList &L)    //冒泡排序
{ int j ,k , flag ;for (j=0; j<L.length-1; j++) /* 共有n-1趟排序 */{flag=TRUE ;for (k=1; k<L.length-j; k++) /* 一趟排序 */{ if (L.r[k+1].key<L.r[k].key){ flag=FALSE ;L.r[0]=L.r[k] ; L.r[k]=L.r[k+1] ; L.r[k+1]=L.r[0] ; }}if (flag==TRUE) break ;} 
}int quick_one_pass(SqList &L , int low, int high)
{ int i=low, j=high ;L.r[0]=L.r[i] ; // R[0]作为临时单元和哨兵do { while ((L.r[i].key<L.r[j].key)&&(j>i))j-- ;if (j>i) { L.r[i]=L.r[j] ;i++; }while ((L.r[i].key<L.r[i].key)&&(j>i))i++ ;if (j>i){ L.r[j]=L.r[i] ; j--; }} while(i!=j) ; /* i=j时退出扫描 */L.r[i]=L.r[0] ; return(i) ;
}void quick_Sort(SqList &L , int low, int high)
{int k , stack[MAX_STACK] , top=0; do{ while (low<high){k=quick_one_pass(L,low,high); stack[++top]=high ;stack[++top]=k+1 ;
/* 第二个子序列的上,下界分别入栈 */high=k-1 ; }if (top!=0) { low=stack[top--] ; high=stack[top--] ;}}while (top!=0&&low<high) ;
}int main()
{SqList L;InitList_Sq(L);printf("直接插入排序法");straight_insert_sort(L);printf("排序成功");for(int i=1;i<L.length;i++)printf("%d ",L.r[i].key);printf("\n");printf("选择排序");simple_selection_sort(L);printf("排序成功");for(int i=1;i<L.length;i++)printf("%d ",L.r[i].key);printf("\n");printf("冒泡排序");Bubble_Sort(L);printf("排序成功");for(int i=1;i<L.length;i++)printf("%d ",L.r[i].key);printf("\n");printf("快速排序");quick_Sort(L,1,L.length);printf("排序成功");for(int i=1;i<L.length;i++)printf("%d ",L.r[i].key);printf("\n");return 0;
}

参考文章

https://www.cnblogs.com/leo-lv/p/10639099.html

https://blog.csdn.net/qq_20011607/article/details/82357239