首页 > 代码库 > OJ刷题之《双向冒泡排序》
OJ刷题之《双向冒泡排序》
题目描述
注:本题只需要提交填写部分的代码,请按照C++语言方式提交。
双向冒泡从小到大排序算法描述:
(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),直到新序列没有元素。
#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;
}
输入
n和n个整数
输出
从小到大排序后的数列
样例输入
6
21 45 85 47 3 15
样例输出
3 15 21 45 47 85
代码如下:
#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; //设置未排序序列的第一个元素位置 for (i=high; i>lastSwapPos; i--) { if (a[i]<a[i-1]) { temp = a[i]; a[i] = a[i-1]; a[i-1] = temp; low = i; //记录交换位置 } } if (lastSwapPos == low) //若未进行交换操作,说明排序已经完 break; } for(i = 0; i<n; i++) cout<<a[i]<<" "; cout<<endl; return 0; }
运行结果:
大早上起来就被这个项目困扰了半个多小时,无论怎么修改需要补充的代码都是得不出正确结果,用了单步调试才突然发现问题。。。原来我之前某次修改的时候改错了地方,把原代码中的循环给改动了...哭醉...
不明白的是那个cnt有什么作用,没有初始化,还出现了cnt++,后面补充的代码也没有使用到它
OJ刷题之《双向冒泡排序》