冒泡排序-阿里云开发者社区

开发者社区> 人工智能> 正文
登录阅读全文

冒泡排序

简介: 冒泡排序

bubbleSort

比较相邻的元素。如果第一个比第二个大,就交换他们两个。

对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。

针对所有的元素重复以上的步骤,除了最后一个。

持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。

算法步骤

第一版

template <typename T>

void bubbleSort(T arr[],int n){

    //在当前数组上,每次都是从第一个元素开始比较,直到没有元素交换,flag仍为true,排序完成

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

        bool flag=true;

        //循环一次,比较总数就减少一次

        for(int j=1;j<n-i;j++){

            if(arr[j-1]>arr[j]){

                swap(arr[j-1],arr[j]);

                flag=false;

            }

        }

        if(flag) break;

    }

    return;

}

template <typename T>

void bubbleSort(T arr[],int n){

    bool swapped;

    do{

        swapped=false;

        for(int i=1;i<n;i++){

            if(arr[i-1]>arr[i]){

                swap(arr[i-1],arr[i]);

                swapped=true;

            }

        }

       // 优化, 每一趟Bubble Sort都将最大的元素放在了最后的位置

       // 所以下一次排序, 最后的元素可以不再考虑

        n--;

    }while(swapped);

}

第二版

使用newn进行优化,记录最后交换的位置

template <typename T>

void bubbleSort(T arr[],int n){

    int newn;//使用newn进行优化

    do{

        newn=0;

        for(int i=1;i<n;i++){

            if(arr[i-1]>arr[i]){

                swap(arr[i-1],arr[i]);

                //记录最后一次交换位置,在此之后的元素在下一轮扫描中不被考虑

                newn=i;

            }

        }

        n=newn;

    }while(n>0);

}

python实现

def bubbleSort(arr):

   n = len(arr)

   for i in range(n):

       flag = 1

       for j in range(1, n - i):

           if arr[j - 1] > arr[j]:

               arr[j - 1], arr[j] = arr[j], arr[j - 1]

               flag = 0

       if flag == 1:

           break

   return arr


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章
最新文章
相关文章