[第七届蓝桥杯省赛C++B组]快速排序
2023-09-11 14:18:49 时间
题目来源:第七届蓝桥杯省赛C++B组
算发标签:快速排序
题目描述:
排序在各种场合经常被用到。
快速排序是十分常用的高效率的算法。
其思想是:先选一个“标尺”,
用它把整个队列过一遍筛子,
以保证:其左边的元素都不大于它,其右边的元素都不小于它。
这样,排序问题就被分割为两个子区间。
再分别对子区间排序就可以了。
下面的代码是一种实现,请分析并填写划线部分缺少的代码。
#include <stdio.h>
void swap(int a[], int i, int j)
{
int t = a[i];
a[i] = a[j];
a[j] = t;
}
int partition(int a[], int p, int r)
{
int i = p;
int j = r + 1;
int x = a[p];
while(1){
while(i<r && a[++i]<x);
while(a[--j]>x);
if(i>=j) break;
swap(a,i,j);
}
______________________;
return j;
}
void quicksort(int a[], int p, int r)
{
if(p<r){
int q = partition(a,p,r);
quicksort(a,p,q-1);
quicksort(a,q+1,r);
}
}
int main()
{
int i;
int a[] = {5,13,6,24,2,8,19,27,6,12,1,17};
int N = 12;
quicksort(a, 0, N-1);
for(i=0; i<N; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}
注意:只填写缺少的内容,不要书写任何题面已有代码或说明性文字。
题目答案:
swap(a,p,j);
题目思路:
我们只要依据快速排序的整体思路分析相关代码即可:
while(i<r && a[++i]<x);
表明左指针找到比目标值大的数字,
while(a[--j]>x);
表明右指针找到比目标值小的数字,
f(i>=j) break;
表明形成小标i>=j就终止
swap(a,i,j);
交换a[i],a[j]
即使得逆序对复原,符合左小右大的整体区间。
经过以上的步骤,我们可以确定一次逆序对被复原,则现在程序进行到了标准值P更换的步骤。
我们将交换swap(a,p,j)
因为p是标准值,a[j]则是小于标准值的值,而程序中P为a[0],则我们应该将P更换为最小值,所以更换为a[j].
相关文章
- 【C/C++学院】(4)c++开篇/类和对象/命名空间/类型增强/三目运算符/const专题/引用专题/函数增强
- C++ vector 赋值、删除、排序类之外的其他函数
- C/C++基础讲解(十三)之数据结构篇排序大比拼
- 蓝桥杯官网 试题 PREV-278 历届真题 双向排序【第十二届】【省赛】【研究生组】【C++】【C】【Java】【Python】四种解法
- C++数据结构-- 递归 排序
- 【 华为OD机试 2023】字符串重新排序(C++ Java JavaScript Python)
- 解答私信@被c++折磨头秃的花季美少女 //C++ 编写一个进阶版的进制转换程序,运行功能如下:请选择要输入的数字的进制(2、8、10、16):请输入该数字:请选择要转换成的进制(2、8。。。
- C++ std::function的用法
- c++中字符串的反转
- C++友元函数和友元类(三)
- C++ 排序函数 sort(),qsort()的使用方法
- PAT 1110 Complete Binary Tree C++ 版
- c++ STL
- 快速排序(c++,java)
- C++如何进行sort的使用——C++如何进行排序
- C++数据处理之求众数+排序
- C++算法之排序算法
- 【C++】算法集锦(1):八大排序算法 :GIF + 亲测代码 +专项练习平台
- 【C++要笑着学】面向对象总结 | 瞎编的C++小故事 | 再次理解封装 | 再次理解面向对象