站点图标 陌路寒暄

双向冒泡排序

code

双向冒泡排序

时间： 1ms        内存：128M

描述：

注：本题只需要提交填写部分的代码

双向冒泡从小到大排序算法描述：
（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;

}

输入：

n和n个整数

输出：

从小到大排序后的数列

示例输入：

6
21 45 85 47 3 15

示例输出：

3 15 21 45 47 85

提示：

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


#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; //设置未排序序列的第一个元素位置	
        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;
	}    

 
        if (lastSwapPos == low) //若未进行交换操作，说明排序已经完
            break;
    }
    for(i = 0; i<n; i++)
       printf("%d ",a[i]);
    printf("\n");
    return 0;
}

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

#include<iostream>
using namespace std;
void BubbleSort_4(int lib[], int n)//改进版3：双向冒泡
{
     int low, high,lastSwapPos,temp,i,count;  //待排序部分数组的边界，即lib[low..high]为待排序部分，lib[0..low-1]和lib[high+1..n-1]为已排序部分
     low = 0;
     high = n - 1;
     while (low < high)
     {
          lastSwapPos = high; //设置需要排序的成员范围（大于此下标的成员已经排好序）
          for (i=low; i<lastSwapPos; i++)
          {
              count++;
              if (lib[i]>lib[i+1])
              {
                   temp = lib[i];
                   lib[i] = lib[i+1];
                   lib[i+1] = temp;
                   high = i;//该处发生了交换操作，更新需要排序的成员范围
              }
          }
          if (lastSwapPos == high) //若未进行交换操作，说明排序已经完成，提前结束扫描工作
              break;

          lastSwapPos = low; //设置需要排序的成员范围（小于此下标的成员已经排好序）
          for (i=high; i>lastSwapPos; i--)
          {
              count++;
              if (lib[i]<lib[i-1])
              {
                   temp = lib[i];
                   lib[i] = lib[i-1];
                   lib[i-1] = temp;
                   low = i;//该处发生了交换操作，更新需要排序的成员范围
              }
          }
          if (lastSwapPos == low) //若未进行交换操作，说明排序已经完成，提前结束扫描工作
              break;
     }
}
int main()
{
	int a[100],i,j;
	for(i=0;i<100;i++)
	{
		cin>> a[i];
		if(a[i]==0)break;
		j=i;
	}
	BubbleSort_4(a, j+1);
	for(i = 0;i<=j;i++)
	cout<<a[i]<<" ";
	cout<<endl;
	return 0;
    return 0;
}

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

退出移动版