冒泡排序 订阅
冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果顺序(如从大到小、首字母从Z到A)错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。 展开全文
冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果顺序(如从大到小、首字母从Z到A)错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。
信息
时间复杂度
O(n²)
外文名
Bubble Sort
算法稳定性
稳定排序算法
中文名
冒泡排序
实    质
把小(大)的元素往前(后)调
所属学科
计算机科学
冒泡排序算法原理
冒泡排序算法的原理如下: [1] 
收起全文
精华内容
参与话题
问答
  • 冒泡排序

    万次阅读 多人点赞 2019-09-16 16:28:32
    冒泡排序是一种比较简单的排序算法,它循环走过需要排序的元素,依次比较相邻的两个元素,如果顺序错误就交换,直至没有元素交换,完成排序。 若对n个人进行排序,我们需要n-1次比较,所以第k次比较需要进行n-k次...

    冒泡排序是一种比较简单的排序算法,它循环走过需要排序的元素,依次比较相邻的两个元素,如果顺序错误就交换,直至没有元素交换,完成排序。
    若对n个人进行排序,我们需要n-1次比较,所以第k次比较需要进行n-k次比较。排序算法通过以数据对象的两两比较作为关键,所以可以得出,冒泡排序需要进行的
    比较次数为:(n-1) + (n-2) + … + 1 = n*(n-1) / 2,因此冒泡排序的时间复杂度为O(n^2)
    在这里插入图片描述
    以js实现为例:

       //1.冒泡排序-s--两两比较,大的和小的换位置
       let dataList=[12,2,3,46,1,2,8];
       let hasSort=[];
      //第一遍循环 n-1 次  (n=dataList.length)
       for(let i=0;i<dataList.length;i++){
      //第二遍循环 n-i-1 次
             for(let j=0;j<i;j++){
               if(dataList[i]>dataList[j]){
                let _data = dataList[i]
                dataList[i] = dataList[j]
                dataList[j]=_data
               }
             }
             hasSort.push(dataList[i]);
       }
       console.log("hasSort:"+hasSort)
       //1.冒泡排序-end
    
    展开全文
  • 冒泡排序冒泡排序动画、冒泡排序代码、冒泡排序教程 代码下载
    展开全文
  • Java 冒泡排序

    千次阅读 多人点赞 2019-05-28 15:19:23
    冒泡排序的原理有一下几个步骤 1 逐一比较数组中相邻的两个元素,如果后面的数字小于前面的数组,就交换前后元素 2 经过一轮的比较之后一定有一个最大的排在后面的位置 3 每次比较剩下的元素,经过n-1次比较,可以...

     

    冒泡排序的原理有一下几个步骤

    1 逐一比较数组中相邻的两个元素,如果后面的数字小于前面的数组,就交换前后元素

    2 经过一轮的比较之后一定有一个最大的排在后面的位置

    3 每次比较剩下的元素,经过n-1次比较,可以实现排序.

     

    package me;
    
    import java.util.Arrays;
    
    public  class Me {
        public static void main(String[] args) {
          int [] arr = {3,2,5,8,6,4,9}; //用冒泡排序
            for (int i=0;i<arr.length-1;i++){ //遍历数组 第一个元素定义为i
                for (int j=0;j<arr.length-1-i;j++){ //遍历数组定义第二个元素为j,加入i是3那么数组中j就是2
                    if (arr[j]>arr[j+1]){ //如果第一个元素大于第二个元素 交换
                        int value = arr[j];
                        arr[j] = arr[j+1];
                        arr[j+1]=value;
                    }
                }
            }
            System.out.println(Arrays.toString(arr));
        }
        
       
    }
    

    如果这个交换元素的值不清楚的话可以看下图

     

    展开全文
  • 经典算法---冒泡排序

    万次阅读 多人点赞 2014-09-24 15:58:50
    原文链接: 冒泡排序---经典排序算法 | 逍遥游 冒泡排序(BubbleSort)以其“在排序过程中相邻元素不断交换,一些元素慢慢被换到最后,看起来就像是元素在冒泡一样”而得名,是一种简单的基于关键词比较的排序...

    原文链接: 冒泡排序---经典排序算法 | 逍遥游

     

    冒泡排序(BubbleSort)以其“在排序过程中相邻元素不断交换,一些元素慢慢被换到最后,看起来就像是元素在冒泡一样”而得名,是一种简单的基于关键词比较的排序算法。

     

    算法原理

    冒泡排序的原理(以递增序为例)是每次从头开始依次比较相邻的两个元素,如果后面一个元素比前一个要大,说明顺序不对,则将它们交换,本次循环完毕之后再次从头开始扫描,直到某次扫描中没有元素交换,说明每个元素都不比它后面的元素大,至此排序完成。

    由于冒泡排序简洁的特点,它通常被用来对于计算机程序设计入门的学生介绍算法的概念。

     

    时间复杂度

    若文件的初始状态是排好序的的,一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数 M 均达到最小值(Cmin = n-1、Mmin = 0)

    所以,冒泡排序最好的时间复杂度为O(N)。


      若初始文件是反序的,需要进行N趟排序。每趟排序要进行 C = N-1次关键字的比较(1≤i≤N-1)和总共(Mmax = (N*(N-1))/2)次的移动(移动次数由乱序对的个数决定,即多少对元素顺序不对,如 1 3 4 2 5 中共有(3,2)、(4,2)两个乱序对),在这种情况下,比较和移动次数均达到最大值(Cmax =N*(N-1) + Mmax=(N*(N-1))/2 = O(N^2))。所以,冒泡排序的最坏时间复杂度为O(N^2)

     

    综上,冒泡排序总的平均时间复杂度为O(N^2)。

    算法稳定性

    冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较,交换也发生在这两个元素之间。如果两个相等的元素相邻,那么根据我们的算法。它们之间没有发生交换;如果两个相等的元素没有相邻,那么即使通过前面的两两交换把两个相邻起来,这时候也不会交换,所以相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法。

     

    算法改进

    由于冒泡排序算法还是比较慢的,所以有很多人对在此基础上进行了改进,我只简单介绍一下我所知道的。

    第一种是上浮操作与下沉操作相结合。传统的冒泡排序只有上浮操作,如果碰到一些很特殊的数据就会显得笨一点,例如(2、3、4、5、1)这个数列按增序排列,那么按照普通冒泡算法就要扫描5趟,可是我们一眼就看出来直接把 1 挪到第一个就行了,扫描 5 次实在是太笨了,于是我们在每次上浮操作后加上一个下沉操作,这样就更快了。

    第二中改进是减少无效比较的次数。所谓无效比较就是当我们已知结果却还要去比较。如果我们多观察冒泡排序的中间过程,我们就会发现,末尾的一些元素在一定次数的扫描后已经到达最终位置了(因为每次扫描后都至少会有一个新的元素到达最终位置),再比较就会造成无效比较。改进方法是,记录下每次扫描中发生交换的最后一个元素位置,下一次扫描就到这里为止。

    可是,无论怎么改进,冒泡排序的时间复杂度都是O(N^2)。

     

    下面给出冒泡排序的C++参考代码和下载地址。

     

     

    //冒泡排序部分,参数形式与标准库的快排一样
    
    //ps:(point start)所需排序的数据首地址
    
    //pe:(point end)  所需排序的数据第一个无效地址
    
    //cmp:自定义的比较函数
    
    int sort(int *ps,int *pe,bool(*cmp)(int,int))
    
    {
    
    //用以判断某次循环后是否有元素位置发生变化
    
        bool flag=true;
    
     
    
        while(flag)
    
        {
    
            flag=false;//假设没有交换
    
     
    
            //上浮过程
    
            for(int i=1;i<pe-ps;i++)//注意:i从1开始
    
            {
    
                if(cmp(ps[i],ps[i-1]))
    
                {
    
                    swap(ps[i],ps[i-1]);
    
                    flag=true;//有元素发生交换,说明排序可能没有结束
    
                }
    
            }
    
        }
    
        return 0;
    
    }
    

     

     

     

     

    更详细的代码,请点击这里下载。

     

    来源:逍遥游,欢迎分享本文,转载请保留出处!

    展开全文
  • Java基础(冒泡排序)

    万次阅读 多人点赞 2019-05-17 16:54:30
    冒泡排序简介 比较相邻的元素。如果第一个比第二个大,就交换他们两个。 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。 针对所有的元素重复以上的...
  • 算法 - 冒泡排序(C#)

    万次阅读 多人点赞 2019-03-14 18:34:09
    分享一个大牛的人工智能教程。... * 冒泡排序(Bubble Sort),是一种计算机科学领域较简单的排序算法。 * 它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来,直到没有元素...
  • Java冒泡排序算法

    千次阅读 多人点赞 2018-10-21 07:25:16
    java冒泡排序算法 1.基本思想: 对比相邻的元素值,如果满足条件就交换元素值,把较小的元素移动到数组的前面(从小到大排序),把大的元素移动到数组的后面,即交换两个元素的位置,这样较小的元素就像气泡一样从...
  • C语言冒泡排序算法

    千次阅读 多人点赞 2018-12-25 17:05:57
    冒泡排序的概念:冒泡排序(Bubble Sort)是一种简单的交换排序,它是通过两两比较相邻记录的关键字,如果发生逆序就进行交换,从而使关键字小的记录如气泡一般逐渐往上“漂浮”(左移),或者使关键字大的记录如...
  • 冒泡排序 C++版

    千次阅读 2018-11-03 17:49:11
    一、说明:冒泡排序的原理在注释中,文中冒泡排序使用了模板来传入数据,详细情况看下面的测试代码。 二、测试代码 #include &amp;lt;iostream&amp;gt; #include &amp;lt;vector&amp;gt; ...

空空如也

1 2 3 4 5 ... 20
收藏数 76,467
精华内容 30,586
关键字:

冒泡排序