首页 > 代码库 > OJ刷题之《二元选择排序》
OJ刷题之《二元选择排序》
Description
注：本题只需要提交标记为修改部分之间的代码，请按照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 j , minpos ,maxpos, tmp;
for (i=0 ; i <n/2; i++)
{
minpos = i;
maxpos = i ;
for (j= i+1; j<= n-i-1; j++)
{
if (a[j] > a[maxpos])
{
maxpos = j ;
continue ;
}
if (a[j]< a[minpos])
minpos = j ;
}
/*****修改的起始行******/
tmp = a[i];
a[i] = a[minpos];
a[minpos] = tmp;
tmp = a[n-i];
a[n-i] = a[maxpos];
a[maxpos] = tmp;
/*****修改的终止行*****/
}
for(i = 0; i<n; i++)
cout<<a[i]<<" ";
cout<<endl;
return 0;
}
Input
n和n个整数
Output
从小到大排序后的数列
Sample Input
8
12 35 69 84 52 54 75 65
Sample Output
12 35 52 54 65 69 75 84HINT
代码如下：
#include<iostream>
using namespace std;
int main()
{
int a[100],i,n;
cin>>n;
for(i=0; i<n; i++)
cin>> a[i];
int j , minpos ,maxpos, tmp;
for (i=0 ; i <n/2; i++)
{
minpos = i;
maxpos = i ;
for (j= i+1; j<= n-i-1; j++)
{
if (a[j] > a[maxpos])
{
maxpos = j ;
continue ;
}
if (a[j]< a[minpos])
minpos = j ;
}
tmp = a[i];
a[i] = a[minpos];
a[minpos] = tmp;
if (maxpos==i)
{
tmp = a[minpos];
a[minpos] = a[n-i-1];
a[n-i-1] = tmp;
}
else
{
tmp = a[maxpos];
a[maxpos] = a[n-i-1];
a[n-i-1] = tmp;
}
}
for(i = 0; i<n; i++)
cout<<a[i]<<" ";
cout<<endl;
return 0;
}
运行结果：
OJ刷题之《二元选择排序》