数据结构中的常见排序总结（顺序表）

概述本文章向大家介绍数据结构中的常见排序总结（顺序表），主要包括数据结构中的常见排序总结（顺序表）使用实例、应用技巧、基本知识点总结和需要注意事项，具有一定的参考价值，需要的朋友可以参考一下。

以下是对顺序表进行直接插入排序、冒泡排序、快速排序代码的实现总结

#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=p) --high;

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;

}

总结

以上是内存溢出为你收集整理的数据结构中的常见排序总结（顺序表）全部内容，希望文章能够帮你解决数据结构中的常见排序总结（顺序表）所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。