C# · 12月 19, 2021

数据结构中的常见排序总结(顺序表)

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

#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[i-1])

{

L.r[0]=L.r[i];//将待插入的记录暂存在监控哨中

L.r[i]=L.r[i-1];//后移

for(j=i-2;L.r[0]<L.r[j];j–)//从后向前寻找插入位置

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<high)//从表的两端交替的向中间扫描

{

while(low=p) –high;

L.r[low]=L.r[high];//将比枢轴记录小的记录移到低端

while(low<high&&L.r[low]<=p) ++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<high){//长度大于1

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;

}