二元选择排序

时间： 1ms        内存：128M

描述：

注：本题只需要提交标记为修改部分之间的代码。

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;
}

C语言方式。

#include <stdio.h>

int main()

{

    int a[100],i,n;

    int j , minpos ,maxpos, tmp;

    scanf("%d",&n);

    for(i=0; i<n; i++)

scanf("%d",&a[i]);

    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++)

        printf("%d ",a[i]);

    printf("\n");

    return 0;

}

输入：

n和n个整数

输出：

从小到大排序后的数列

示例输入：

8 
12 35 69 84 52 54 75 65

示例输出：

12 35 52 54 65 69 75 84

提示：

参考答案（内存最优[0]）：

#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-1];
        a[n-i-1] = a[maxpos];
        a[maxpos] = tmp;
    }
    for(i = 0; i<n; i++)
        cout<<a[i]<<" ";
    cout<<endl;
    return 0;
}

参考答案（时间最优[0]）：

#include<iostream>
using namespace std;
void SelectSort(int r[],int n)
{
    int i ,j , min ,max, tmp;
    for (i=0 ;i <n/2;i++)
	{
		min = i; max = i ;
        for (j= i+1; j<= n-i-1; j++)
		{
            if (r[j] > r[max])
			{
                max = j ; continue ;
			}
            if (r[j]< r[min])
			{
                min = j ;
            }
		}
		//下面的代码是错的
      //tmp = r[i-1]; r[i-1] = r[min]; r[min] = tmp;
      //tmp = r[n-i]; r[n-i] = r[max]; r[max] = tmp;
		tmp = r[i]; r[i] = r[min]; r[min] = tmp; //正确代码
		if(i==max) max=min;
		tmp = r[n-i-1]; r[n-i-1] = r[max]; r[max] = tmp;

	}

}
int main()
{
	int a[100],i,j,n;
	cin>>n;
	for(i=0;i<n;i++)
	{
		cin>> a[i];

	}
	SelectSort(a, n);
	for(i = 0;i<n;i++)
		cout<<a[i]<<" ";
	cout<<endl;
	return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。