Problem D: 双向冒泡排序
Problem D: 双向冒泡排序
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 447 Solved: 197
[Submit][Status][Web Board]
Description
注:本题只需要提交填写部分的代码
双向冒泡从小到大排序算法描述:
(1)从当前序列的第1个元素开始,对相邻元素从前往后两两比较,不满足条件(从小到大)则彼此交换,一直到序列结束。此时最后1个元素为最大值。
(2)从当前序列的倒数第2个元素开始,对相邻元素从后往前两两比较,不满足条件则彼此交换,一直到序列开始。此时第1个元素为最小值。
(3)将第2个元素作为新序列的开始,倒数第2个元素作为新序列的结束,重复(1)~(2),直到新序列没有元素。
改进的双向冒泡从小到大排序算法描述:
(a)在上述算法第(1)步,记录每次的交换位置,令high表示最后1次交换位置,若比较过程未发生交换,则算法结束;
(b)在算法第(2)步,只需要从high向前比较即可,比较过程中记录每次的交换位置,令low表示最后1次交换位置,若比较过程未发生交换,则算法结束;
(c)在算法第(3)步,令新序列为开始位置为low,结束位置为high,重复(a)~(b),直到新序列没有元素。
C++语言方式
#include<iostream>
using namespace std;
int main()
{
int a[100],i,n;
cin>>n;
for(i=0; i<n; i++)
cin>> a[i];
int low, high,lastSwapPos,temp,cnt;
low = 0;
high = n - 1;
while (low < high)
{
lastSwapPos = high; //设置未排序序列的最后一个元素位置
for (i=low; i<lastSwapPos; i++)
{
cnt++;
if (a[i]>a[i+1])
{
temp = a[i];
a[i] = a[i+1];
a[i+1] = temp;
high = i; //记录交换位置
}
}
if (lastSwapPos == high) //若未进行交换操作,说明排序已经完成
break;
lastSwapPos = low; //设置未排序序列的第一个元素位置
/*
请在该部分填写缺少的代码
*/
if (lastSwapPos == low) //若未进行交换操作,说明排序已经完
break;
}
for(i = 0; i<n; i++)
cout<<a[i]<<" ";
cout<<endl;
return 0;
}
C语言方式
#include <stdio.h>
int main(){
int a[100],i,n;
scanf("%d",&n);
for(i=0; i<n; i++)
scanf("%d",&a[i]);
int low, high,lastSwapPos,temp,cnt;
low = 0;
high = n - 1;
while (low < high){
lastSwapPos = high; //设置未排序序列的最后一个元素位置
for (i=low; i<lastSwapPos; i++){
cnt++;
if (a[i]>a[i+1]){
temp = a[i];
a[i] = a[i+1];
a[i+1] = temp;
high = i; //记录交换位置
}
}
if (lastSwapPos == high) //若未进行交换操作,说明排序已经完成
break;
lastSwapPos = low; //设置未排序序列的第一个元素位置
/*
请在该部分填写缺少的代码
*/
if (lastSwapPos == low) //若未进行交换操作,说明排序已经完
break;
}
for(i = 0; i<n; i++)
printf("%d ",a[i]);
printf("\n");
return 0;
}
Input
n和n个整数
Output
从小到大排序后的数列
Sample Input
6
21 45 85 47 3 15
Sample Output
3 15 21 45 47 85
for(i=high-1;i>low;i--)
{
if(a[i]<a[i-1])
{
temp=a[i];
a[i]=a[i-1];
a[i-1]=temp;
}
}
lastSwapPos=i;
最新文章
- 51. 顺时针打印矩阵[print matrix in clockwise direction]
- [Java入门笔记] Java语言基础(四):流程控制
- 当前界面最上面添加视图(UIWimdow)
- codevs 1033 蚯蚓的游戏问题
- c语言文件复制
- struts2视频学习笔记 29-30(Struts 2常用标签,防止表单重复提交)
- Questions that are independent of programming language. These questions are typically more abstract than other categories.
- 《深入浅出嵌入式底层软件开发》—1. ARM汇编编程基础
- Quartz2D介绍
- Java 处理json经常使用代码
- C# API 大全
- 比较实用的webpack配置代码
- Material Design学习-----SnackBar
- Centos定时任务
- 温故而知新--hashtable
- Python中编码的详细讲解
- MySQL从查找数据库表到删除全过程
- 爬虫工程师JD归纳
- 【Python】*args和**kwargs的区别
- java holdsLock()方法检测一个线程是否拥有锁
热门文章
- rlwrap: command not found和解决linux下sqlplus 提供浏览历史命令行的功能
- Jmeter-返回值乱码处理
- 如何在手机项目中使用rem单位
- Restful 3 -- 序列化组件(GET/PUT/DELETE接口设计)、视图优化组件
- TCP/IP三次握手与四次挥手的正确姿势
- Markdown 简单标签语言
- 基于C#编程语言的Mysql常用操作
- 合理设置apache httpd的最大连接数--linux
- clipboard JS(剪切板)的使用
- AngularJs在ng-click函数中如何获取代表当前元素的DOM对象