快速排序算法：c++

参考视频：

数据结构合集 - 快速排序(算法过程, 效率分析, 稳定性分析)_哔哩哔哩_bilibili

快速排序代码(C/C++实现) 细到爆炸！_哔哩哔哩_bilibili

核心：

任取一个元素作为枢轴，比枢轴大的去左边，比枢轴小的去右边，递归处理左右两边，直到空一个或者为空

题目1

6-13 数据结构考题 - 快速排序 - 划分函数

分数 25

作者 陈皓

单位 合肥师范学院

用顺序表作存储结构，输入一组数据，用快速排序法对其进行排序。

顺序表的类型描述：

#define MAXSIZE 50 // MAXSIZE为最大数据元素数目 typedef int ElemType; typedef struct { ElemType r[MAXSIZE +1]; // r[0]闲置或另作它用 int length; }SqList;

函数接口定义：

下面给出了快速排序 - 划分函数的大部分内容，但缺少了一部分（以下划线____标识出来的部分）。

请先将以下代码中画横线的部分补充完整，然后将完整的函数Partition提交系统，完成题目要求的功能。

int Partition(SqList &L,int low,int high) { int i,j; L.r[0]=L.r[____]; while ( ____ ) { while ( low<high && L.r[____]>=L.r[0] ) high--; L.r[____]=L.r[____]; while ( low<high && L.r[____]<=L.r[0] ) low++; L.r[____]=L.r[____]; } L.r [____] =L.r[0]; return low; }

int Partition(SqList &L,int low,int high)快速排序算法中，对 顺序表low ~ high范围内的元素进行划分的函数

测试主程序样例：

int main () { SqList L; int low,high; create(L); low=1; high=L.length; QuickSort(L,low,high); print(L); return 0; }

输入格式:

第一行输入一个整数n，表示顺序表的元素个数。

第二行输入原始序列的n 个整数。

输出格式:

在一行中输出从小到大排序后的结果，数字间以1个空格分隔，行末不得有多余空格。

输入样例:

8 19 -18 13 26 275 26 7 35

输出样例:

-18 7 13 19 26 26 35 275

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

C++ (g++)

int Partition(SqList &L,int low,int high){ int i,j; L.r[0]=L.r[low]; while(low<high){ while(low<high&&L.r[high]>=L.r[0])high--; L.r[low]=L.r[high]; while(low<high&&L.r[low]<=L.r[0])low++; L.r[high]=L.r[low]; } L.r[low]=L.r[0]; return low; }

题目二

6-14 数据结构考题 - 快速排序 - 主调函数

分数 25

作者 陈皓

单位 合肥师范学院

用顺序表作存储结构，输入一组数据，用快速排序法对其进行排序。

顺序表的类型描述：

#define MAXSIZE 50 // MAXSIZE为最大数据元素数目 typedef int ElemType; typedef struct { ElemType r[MAXSIZE +1]; // r[0]闲置或另作它用 int length; }SqList;

函数接口定义：

下面给出了快速排序主调函数的大部分内容，但缺少了一部分（以下划线____标识出来的部分）。

请先将以下代码中画横线的部分补充完整，然后将完整的函数QuickSort提交系统，完成题目要求的功能。

void QuickSort(SqList &L, int low, int high) { int i; if (low<high ) { i=Partition(L, ____, ____ ); QuickSort(L, ____, ____ ); QuickSort(L, ____ , ____ ); } }

测试主程序样例：

int main () { SqList L; int low,high; create(L); low=1; high=L.length; QuickSort(L,low,high); print(L); return 0; }

输入格式:

第一行输入一个整数n，表示顺序表的元素个数。

第二行输入原始序列的n 个整数。

输出格式:

在一行中输出从小到大排序后的结果，数字间以1个空格分隔，行末不得有多余空格。

输入样例:

8 19 -18 13 26 275 26 7 35

输出样例:

-18 7 13 19 26 26 35 275

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

C++ (g++)

void QuickSort(SqList &L, int low, int high){ int i; if(low<high){ i=Partition(L,low,high); QuickSort(L,low,i-1); QuickSort(L,i+1,high); } }