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

    万次阅读 多人点赞 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;
    
    }
    

     

     

     

     

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

     

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

    展开全文
  • 冒泡排序

    万次阅读 2019-06-30 11:35:02
    排序算法之【冒泡排序】 在写代码之前我们需要对冒泡排序有一个逻辑上的理解:即什么是冒泡排序呢? 冒泡排序是排序算法的其中一种,该排序的逻辑理解起来较为容易,理解上可以有两种方式,一种中正向的思维,一种...

     

    排序算法之【冒泡排序】

    在写代码之前我们需要对冒泡排序有一个逻辑上的理解:即什么是冒泡排序呢?
             冒泡排序是排序算法的其中一种,该排序的逻辑理解起来较为容易,理解上可以有两种方式,一种中正向的思维,一种是逆向的思维,什么意思呢?所谓的正向思维就是从前往后,从左往右,从上到下。那么逆向思维呢就正好与之相反。
             下面来说一正向思维下的冒泡排序:
              例如给你一组数据:{1, 34, 56, 8, -32, 7, -9, 0, 235 }在正向思维下的排序方式就是从左到右的进行排序,其排序的是按照第一个数和第二个数比较大小,如果第一个数比第二个数大的话,第二个数就和第一个数交换位置,第二个在和第三个比较大小,如果第二个数比第三个数小那么就位置不变,反之就交换位置,接着往后比较,依次进行下去。总结的来说就是进行一次完整的排序之后就会出现一个现象就是排在最后的数最大。
              例如:    1, 34, 56, 8, -32, 7, -9, 0, 235
              第一次:1, 34, 8,-32 ,7 , -9, 0, 56, 235      235最大的排在了最后
              第二次:1,8,-32,7,-9,0,34,56,235           56除235之外的最大的排在了最后
              ...
              第八次:-32,-9,0,1,7,8,34,56,235            ...

    排序块:

    /**
     * @author yxm
     * 正向思维下的冒泡排序
     * */
    public class MaoPaoSort {
    	public static void main(String[] args) {
    		System.out.print("[");
    		int nums[] = { 1, 34, 56, 8, -32, 7, -9, 0, 235 };
    		for (int i = 0; i < nums.length; i++) {// 当前要确定的是哪个位置的数
    			for (int j = 0; j < nums.length - 1 - i; j++) {
    				if (nums[j - 1] > nums[j]) {
    					int tmp = nums[j - 1];
    					nums[j - 1] = nums[j];
    					nums[j] = tmp;
    				}
    			}
    		}
    		for (int x : nums) {
    			System.out.print(x + ",");
    		}
    		System.out.print("]");
    
    	}
    }
    


           逆向思维呢正好就与正向思维下的相反,但是执行的效果是一样的,逻辑也是一样,只要理解了这个逻辑,代码写起来就不是那么的难了。
    逆向思维下的代码块:

    /**
     * @author yxm
     * 逆向思维下的冒泡排序
     * */
    public class MaoPaoSort {
            public static void main(String[] args) {
                int [] arr={1, 34, 56, 8, -32, 7, -9, 0, 235};
                for(int i=0;i<arr.length;i++){
                    for(int j=arr.length-1;j>=i+1;j--){
                        if(arr[j]<arr[j-1]){
                            int t=arr[j];
                            arr[j]=arr[j-1];
                            arr[j-1]=t;
                        }
                        }
                    }
                    for(int x:arr){
                    System.out.println(x);
                }
        }
    }

          总而言之呢还是要熟悉冒泡排序的逻辑,这样才能有更深的理解。

          创作难免有错误和不当的地方,还请大家多多指教。


     

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

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

    一.冒泡排序简介(从小到大排序)

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

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

                针对所有的元素重复以上的步骤,除了最后一个,即需要进行length-1次。

                第一次是对n个数进行n-1次比较,进行到最后第n个的一个是最大的;

                第二次是对n-1个数进行n-2次比较,进行到最后第n-1个的一个是最大的;

                ......

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

                动态图:

    二.代码案例

    package day0515;
    public class demo_sort {
        public static void main(String[] args) {
            //冒泡排序算法
            int[] numbers=new int[]{1,5,8,2,3,9,4};
            //需进行length-1次冒泡
            for(int i=0;i<numbers.length-1;i++)
            {
                for(int j=0;j<numbers.length-1-i;j++)
                {
                    if(numbers[j]>numbers[j+1])
                    {
                        int temp=numbers[j];
                        numbers[j]=numbers[j+1];
                        numbers[j+1]=temp;
                    }
                }
            }
            System.out.println("从小到大排序后的结果是:");
            for(int i=0;i<numbers.length;i++)
                System.out.print(numbers[i]+" ");
        }
    }
    

    三.debug命令调试

    •     在需要断点的行数前面进行点击(打断点)

    •     右键单击Debug模式运行

    •     F8快捷键依次执行代码

     

    展开全文
  • 冒泡排序

    万次阅读 多人点赞 2019-08-05 20:41:40
    冒泡排序冒泡排序法原理示意图 public static void ArraySortTest() { int[] ages= {21,27,31,19,50,32,16,25}; System.out.println(Arrays.toString(ages)); //控制比较轮数 for(int i=1;i<ages....

    冒泡排序法

    冒泡排序法原理示意图
    在这里插入图片描述
    在这里插入图片描述

    public static void ArraySortTest() {
    
    		int[] ages= {21,27,31,19,50,32,16,25};
    		System.out.println(Arrays.toString(ages));
    		//控制比较轮数
    		for(int i=1;i<ages.length;i++) {
    			//每轮比较多少
    			for(int j=0;j<ages.length-i;j++) {
    				if(ages[j]>ages[j+1]) {
    					int tmp=0;
    					tmp=ages[j];
    					ages[j]=ages[j+1];
    					ages[j+1]=tmp;					
    				}
    			}
    		}
    		System.out.println(Arrays.toString(ages));
    	}
    
    展开全文
  • 算法 - 冒泡排序(C#)

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

    2014-02-02 15:59:57
    冒泡排序它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。
  • 冒泡排序冒泡排序动画、冒泡排序代码、冒泡排序教程 代码下载
  • 冒泡排序算法

    万次阅读 多人点赞 2018-07-19 22:31:43
    什么是冒泡排序呢?冒泡排序的英语名是Bubble Sort,是一种最基础的交换排序。  大家一定都喝过汽水吧,汽水中常常有许多小小的气泡,往上飘,这是因为组成小气泡的二氧化碳比水要轻,所以小气泡才会一点一点的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 217,892
精华内容 87,156
关键字:

冒泡排序