wap网站建设学什么,wordpress 数据还原,怎么利用360域名做网站,wordpress模板如何安装教程视频教程插入排序及优化 插入排序算法算法讲解数据模拟代码 优化思路一、二分查找二、copy函数 优化后代码算法的用途题目#xff1a;数星星#xff08;POJ2352 star#xff09;输入输出格式输入格式#xff1a;输出格式 输入输出样例输入样例输出样例 题目讲解步骤如下AC 代码 插入… 插入排序及优化 插入排序算法算法讲解数据模拟代码 优化思路一、二分查找二、copy函数 优化后代码算法的用途题目数星星POJ2352 star输入输出格式输入格式输出格式 输入输出样例输入样例输出样例 题目讲解步骤如下AC 代码 插入排序算法
在了解如何改进插入排序之前我们先要了解插入排序的基本算法
算法讲解
插入排序对于少量元素的排序是一个有效的算法 。
插入排序是一种简单的排序方法它是将一个数据插入到已经排好序的有序数组从而形成一个新的有序数组。
插入排序的工作方式像许多人排序扑克牌
我们每次从桌子上拿走一张牌并将其插入到手中正确的位置。
为了找到它的正确位置我们从右到左将它与手中的每张牌进行比较。
因此手上的牌总是有序。
数据模拟
原本要排序的数为 5 3 4 2 9 1从小到大排序。 3 5 4 2 9 1 // 将3放到合适的位置5前面3 4 5 2 9 1 // 将4放到合适的位置3、5中间2 3 4 5 9 1 // 将2放到合适的位置最前面2 3 4 5 9 1 // 将9放到合适的位置最后面1 2 3 4 5 9 // 将1放到合适的位置最前面排序结束
代码
#include iostream
using namespace std;
int n,a[2000]; //定义数据个数n排序数组a
int main()
{cin n; //输入个数for (int i1;in;i)cin a[i]; //输入数据for (int i2;in;i) //第一个数本身只有一个元素所有有序因此不用参与排序{int j,ka[i]; //记录下当前元素for (ji-1;j0;j--){if (a[j]k) //若前面一个数大于当前元素a[j1]a[j]; //则将前面一个元素往后移动elsebreak; //否则说明当前元素已经找到了合适的位置推出循环}a[j1]k; //将当前元素放入数组的合适的位置/* 输出排序的过程for (int j1;jn;j)cout a[j] ;cout endl;*/}for (int i1;in;i)cout a[i] ; //输出排序好的数组return 0;
}优化思路
我们发现插入排序的过程浪费在了查找合适的位置上那么怎么优化呢
我们知道插入排序一直在维护 前 i i i个数是有序的那么如何快速在有序的数列中查找一个小于或大于自己的数呢
一、二分查找
二分
那么这样我们就讲查找的时间从 O ( n ) O(n) O(n)缩短为 O ( n l o g ( n ) ) O(n~log(n)) O(n log(n))
忍不住激动
可是找到位置不够还要进行移动啊。移动的时间复杂度是 O ( n ) O(n) O(n)那么这样非但没有优化反而还增加了查找的时间。。。
希望瞬间破灭
但是我会向它屈服吗
会 吗
明显不会
二、copy函数
我们可以使用一个 S T L STL STL库里面的一个函数
copy(a,an,a1);c o p y copy copy函数
这个函数可以在 O ( 1 ) O(1) O(1)的时间范围内将数组的某一段移动到 使用方法 以上面的操作为例子这表明
以 a a a数组的第 0 0 0位为开头以 a a a数组的第 n − 1 n-1 n−1位位结尾将它移动到开头位第 1 1 1位的位置
那么这就好办了只需要要讲两个结合起来一个速度与归并排序相当代码比归并排序简短许多的超级优化插入排序代码诞生了
优化后代码
#include bits/stdc.h
#define N 2000000
using namespace std;
int n,x,y,f,t[N],k[N];
int main() {scanf(%d,n);for (int i1; in; i) {scanf(%d,x);fupper_bound(t1,ti,x)-t; //记录二分的位置copy(tf,ti,tf1); //copyt[f]x; //存入数组}for (int i1; in; i) {printf(%d ,t[i]);}return 0;
}输入数据
5
4 9 1021 54 3输出数据
3 4 9 54 1021也是对了好吧~~
算法的用途
这个算法可以快速的在有序数列里面进行操作也是异常的方便快捷代码超级简短 下面给一道可以用这个算法解决的问题
题目数星星POJ2352 star
天文学家经常观察星象图。星象图中用平面上的点来表示一颗星星每一颗星星都有一个笛卡尔坐标。设定星星的等级为其左下角星星的总数。天文学家们想知道星星等级的分布情况。
比如上图 5 5 5号星星的等级为 3 3 3其左下角有编号为 1 1 1、 2 2 2、 4 4 4星星共三颗。 2 2 2号星星和 4 4 4号星星的等级为 1 1 1。在上图中只有一颗星星等级为 0 0 0两颗星星等级为 1 1 1一颗星星等级为 2 2 2一颗星星等级为 3 3 3。 给定一个星象图请你写一个程序计算各个等级的星星数目。
输入输出格式
输入格式
输入的第一行包含星星的总数 N ( 1 N 15000 ) N (1N15000) N(1N15000)。接下来 N N N行描述星星的坐标 ( X , Y ) (X,Y) (X,Y) X X X和 Y Y Y用空格分开 0 ≤ X , Y ≤ 32000 0\le X,Y\le 32000 0≤X,Y≤32000。星象图中的每个点处最多只有一颗星星。所有星星按 Y Y Y坐标升序排列。 Y Y Y坐标相等的星星按 X X X坐标升序排列。
输出格式
输出包含 N N N行每行一个整数。第一行包含等级 0 0 0的星星数目第二行包含等级 1 1 1的星星数目依此类推最后一行包含等级为 N − 1 N-1 N−1的星星数目。
输入输出样例
输入样例
5
1 1
5 1
7 1
3 3
5 5输出样例
1
2
1
1
0题目讲解
由于输入数据有序所以在第 i i i颗星星左下角的星星一定在 i i i前面原理自己想想就知道了~~
所以其实就是求在点 i i i前面的点中有多少个的 X X X坐标是比 i i i的 X X X坐标要小的因此直接考虑插入排序做法
步骤如下
输入星星的数量 n n n循环从 1 1 1到 n n n 每次输入当前点的 X X X和 Y Y Y用二分查找当前点的 X X X应当放在哪个位置用变了量 f f f记录位置 f − 1 f-1 f−1就是当前星星的等级用 c o p y copy copy将数据从当前合适的位置开始到 i − 1 i-1 i−1往后移动一位将当前数据存入排序数组用另一个数组标记这个等级的星星 循环输出每个级别的星星
AC 代码
#include bits/stdc.h
#define N 20000
using namespace std;
int n,x,y,f,t[N],k[N];
int main() {scanf(%d,n);for (int i1; in; i) {scanf(%d%d,x,y);fupper_bound(t1,ti,x)-t;copy(tf,ti,tf1);t[f]x;k[f-1];}for (int i0; in; i) {printf(%d\n,k[i]);}return 0;
}
