数据结构中的常见排序总结（顺序表）
|
以下是对顺序表进行直接插入排序、冒泡排序、快速排序代码的实现总结 #include using namespace std; #include #define M 100 typedef struct { int r[M+1]; int length; }SqList; void InsertSort(SqList &L)//直接插入排序实现； { int j; for(int i=2;i<=L.length;i++) { if(L.r[i] { L.r[0]=L.r[i];//将待插入的记录暂存在监控哨中 L.r[i]=L.r[i-1];//后移 for(j=i-2;L.r[0] L.r[j+1]=L.r[j];//记录逐个后移，直到找到插入位置 L.r[j+1]=L.r[0];//将r[0]即原r[i]，插入到正确位置 } } } void BubbleSort(SqList &L) {//冒泡排序； int m,flag,j,t; m=L.length-1; flag=1;//用flag标记一趟排序是否发生交换； while((m>0)&&(flag==1)) { flag=0;//flag置为0，若本趟未发生交换，则不会执行下一趟排序 for(j=1;j<=m;j++) { if(L.r[j]>L.r[j+1]) { flag=1;//flag置为1，表示本趟排序发生了交换； t=L.r[j]; L.r[j]=L.r[j+1]; L.r[j+1]=t; } } --m;//此处注意：该语句是在for循环外面，while循环里面 } } int Partition(SqList &L,int low,int high) {//对顺序表L中的子表r[low..high]进行一趟排序，返回枢轴位置 int p; L.r[0]=L.r[low];//用子表的第一个记录做枢轴记录 p=L.r[low];//枢轴记录的关键字保存在P中 while(low { while(low L.r[low]=L.r[high];//将比枢轴记录小的记录移到低端 while(low L.r[high]=L.r[low];//将比枢轴记录大的记录移到高端 } L.r[low]=L.r[0];//枢轴记录到位 return low;//返回枢轴位置 } void QSort(SqList &L,int high) {//对顺序表L中的子序列L.r[]做快速排序 int p; if(low p=Partition(L,low,high);//将顺序表一分为二，p是枢轴位置 QSort(L,p-1);//对左子表递归排序 QSort(L,p+1,high);//对右子表递归排序 } } void QuickSort(SqList &L) {//对顺序表做快速排序 QSort(L,1,L.length); } void Intput(SqList &L)//输入函数 { scanf("%d",&L.length); for(int i=1;i<=L.length;i++) scanf("%d",&L.r[i]); } void Output(SqList &L)//输出函数 { for(int i=1;i<=L.length;i++) printf("%d ",L.r[i]); } int main() { SqList LA,LB,LC; printf("请输入您要排序的序列中的元素个数及各元素：n"); Intput(LA); LB=LC=LA; InsertSort(LA); printf("直接插入排序的结果为："); Output(LA); printf("n"); printf("冒泡排序的结果为："); BubbleSort(LB); Output(LB); printf("n"); printf("快速排序的结果为："); QuickSort(LC); Output(LC); return 0; } （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |