石家庄网站平台,东莞seo按天计费,做旅行社网站多少钱,网站建设列表基本思想——分治
分治是指就是把一个复杂的问题分成两个或更多的相同或相似的子问题#xff0c;再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解#xff0c;原问题的解即子问题的解的合并。 很多的排序问题大多都是使用分治的思想来进行解决。
实现步骤 …基本思想——分治
分治是指就是把一个复杂的问题分成两个或更多的相同或相似的子问题再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解原问题的解即子问题的解的合并。 很多的排序问题大多都是使用分治的思想来进行解决。
实现步骤
确定分界点有四种情况数列最左端、数列最右端、数列中间和随机位置。 将整个区间根据分界点值划分为小于分界点和大于分界点两部分。 分别对左右两段进行递归处理。
题目描述
给定你一个长度为 n 的整数数列。 请你使用快速排序对这个数列按照从小到大进行排序。 并将排好序的数列按顺序输出。
输入格式 输入共两行第一行包含整数 n。 第二行包含 n 个整数所有整数均在 1∼1e9 范围内表示整个数列。
输出格式 输出共一行包含 n 个整数表示排好序的数列。
数据范围 1≤n≤100000
输入样例 5 3 1 2 4 5
输出样例 1 2 3 4 5
实现代码 1. 模板
#include bits/stdc.h
using namespace std;const int N100010;
int n;
int q[N];
void quick_sort(int q[],int l,int r)
{if(lr){return;}else{int xq[lr1],il-1,jr1;while(ij){do{i;}while(q[i]x);do{j--;}while(q[j]x);if(ij){swap(q[i],q[j]);}}quick_sort(q,l,j);quick_sort(q,j1,r);}
}
int main()
{cinn;for(int i0;in;i){cinq[i];}quick_sort(q,0,n-1);for(int i0;in;i){coutq[i] ;}system(pause);return 0;
}2. STL
sort(x, y)详解
头文件algorithm。功能对数组从起点 x 到终点 y 进行从小到大的升序排列。注意sort默认为升序排列但是也可以自己添加自定义函数比较器按制定规则进行比较。 #include bits/stdc.h
using namespace std;const int N100010;
int q[N];
int main()
{int n;cinn;for(int i0;in;i){cinq[i];}sort(q,qn);for(int i0;in;i){coutq[i] ;}system(pause);return 0;
}
