双向冒泡排序

2020年1月17日 1377点热度 0人点赞 0条评论

双向冒泡排序

时间: 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

提示:

参考答案:

解锁文章

没有看到答案?微信扫描二维码可免费解锁文章

微信扫描二维码解锁

使用微信扫描二维码打开广告页面后可以立即关闭,再刷新此页面即可正常浏览此文章

所跳转广告均由第三方提供,并不代表本站观点!

已经扫描此二维码?点此立即跳转

code

这个人很懒,什么都没留下

文章评论