折半插入排序-ACM题
2024-08-22 11:01:44
第一种实现方式:(本人一开始对cin的使用不是很熟悉,看了一些人得博客详解后才有了第一种方式的实现,自己都被惊讶到了so easy:题目在下面)
//
// main.cpp
// BinaryInsertSort
//
// Created by Jason on 16/9/28.
// Copyright © 2016年 Jason. All rights reserved.
// #include <iostream>
using namespace std;
//折半插入排序-算法
void BinaryInsertSort(int R[],int n )
{
int i,j,mid,low,high,temp;
for(i=2; i<=n; ++i)
{
R[0] = R[i];
low = 1;
high = i-1;
while(low <= high)
{
mid = (low + high) / 2;
if(temp > R[mid])
{
low = mid + 1;
}else{
high = mid - 1;
}
}
for(j=i-1; j>=high+1; --j)
{
R[j+1] = R[j];
}
R[high+1] = R[0];
}
}
int main(int argc, const char * argv[]) {
int n;
int i = 0;
cin>>n;
if(n<=1000&&n>=1)
{
int R[n];
int b;
while(i<n&&cin>>b)
{
R[i] = b;
i++;
}
BinaryInsertSort(R,n);
for(int j=0; j<n; ++j)
{
cout << R[j] <<" ";
}
cout << endl;
}
return 0;
}
第二种实现方式
// main.cpp // ACM_1775 // Created by Jason on 16/9/27. // Copyright © 2016年 Jason. All rights reserved. /** ACM题目: 地址:http://arena.acmclub.com/problem.php?id=1775 输入 输入的第一行包含1个正整数n,表示共有n个整数需要参与排序。其中n不超过1000。 第二行包含n个用空格隔开的正整数,表示n个需要排序的整数。 输出 只有1行,包含n个整数,表示从小到大排序完毕的所有整数。 请在每个整数后输出一个空格,并请注意行尾输出换行。 样例输入 10 2 8 4 6 1 10 7 3 5 9 样例输出 1 2 3 4 5 6 7 8 9 10 提示 在本题中,需要按照题目描述中的算法完成折半插入排序的算法。与直接插入排序算法不同,折半插入排序算法在查找插入位置时采用了折半查找的方案,减少了关键字之间的比较次数,但是记录的移动次数并没有发生改变,因此折半插入排序的时间复杂度依旧为O(n2),同样不是一种非常高效的排序方法。 **/ #include <iostream> #include <sstream>//包含串流输入输入类 #include <string> using namespace std; //折半插入算法 void BinaryInsertSort(int R[],int n ) { int i,j,mid,low,high,temp; for(i=1; i<n; ++i) { temp = R[i]; low = 0; high = i; while(low <= high) { mid = (low + high) / 2; if(temp > R[mid]) { low = mid + 1; }else{ high = mid - 1; } } for(j=i-1; j>=low; --j) { R[j+1] = R[j]; } R[low] = temp; } } int main(int argc, const char * argv[]) { int k = 0; int n; cin>>n; int R[n]; /** 问题:下面的getline(cin,m)没法键盘输入,直接跳过 解决:由于在写getline()函数之前,使用过了回车 (不论你输入的是字符,数字或是回车,空格符,getline()函数都接收) 而cin>>这种输入方式却是忽略回车的,如果你在getline()之前cin的一个数,回车被cin忽略了,却被getline函数接收了,感觉就是这条语句被跳过了 所以解决的办法是在getline函数之前再使用getline一次,将输入流里的回车符接收掉,后面就能正常输入了 **/ if (n<=1000&&n>=1) { string m; /** getline 函数不是c库函数而是C++库函数, getline函数是一个比较常见的函数。根据它的名字我们就可以知道这个函数是来完成读入一行数据的 C++中定义了一个在std名字空间的全局函数,因为这个getline函数的参数使用了string字符串,所以声明在了<string>头文件中了。 **/ getline(cin, m); getline(cin, m); /** C++引入了ostringstream、istringstream、stringstream这三个类,要使用他们创建对象就必须包含<sstream>这个头文件。 istringstream类用于执行C++风格的串流的输入操作。 ostringstream类用于执行C风格的串流的输出操作。 strstream类同时可以支持C风格的串流的输入输出操作。 istringstream的构造函数原形如下: istringstream::istringstream(string str); 它的作用是从string对象str中读取字符。 getline()的原型是istream& getline ( istream &is , string &str , char delim ); 其中 istream &is 表示一个输入流,譬如cin;string&str表示把从输入流读入的字符串存放在这个字符串中(可以自己随便命名,str什么的都可以); char delim表示遇到这个字符停止读入,在不设置的情况下系统默认该字符为'\n',也就是回车换行符(遇到回车停止读入) **/ istringstream is(m); int number; while(is>>number) { R[k] = number; k++; } BinaryInsertSort(R,n); for(int j=0; j<n; ++j) { cout << R[j] <<" "; } cout << endl; }
}
最新文章
- bzoj2330: [SCOI2011]糖果
- Android高效计算——RenderScript(二)
- spring+缓存
- SystemC简介
- POJ2065 SETI(高斯消元 同模方程)
- java22 - 1 多线程之 单线程和多线程的图解
- 采用HSV生成随机颜色
- 去除Html标签
- docker offical docs:Working with Docker Images
- linux端口
- SAP接口编程 之 JCo3.0系列(05) : Exception Handling
- 详解HTML5中的<;aside>;元素与<;article>;元素
- UML类图设计
- Winform 下拉框绑定问题
- 说说自己对RESTful API的理解s
- 【ASP.NET MVC 学习笔记】- 20 ASP.NET Web API
- logback.xml例子
- [Aaronyang] 写给自己的WPF4.5 笔记6[三巴掌-大数据加载与WPF4.5 验证体系详解 2/3]
- Build Castles(构建城堡)
- Gym101482 NWERC 2014(队内训练第4场)
热门文章
- linux shell中";2>;&;1";含义
- php中的XML DOM(10)
- “全栈2019”Java多线程第十章:Thread.State线程状态详解
- 打开SQL Server2000企业管理器时候提示“MMC 无法创建管理单元 ”
- rpm -ivh 这个ivh是干什么的
- 使用X-Pack插件来进行权限控制
- 十招谷歌 Google 搜索
- Jmeter Plugins----- Transactions per Second 配置项
- python有哪些比较隐藏的知识点?
- psp0级报告