冒泡排序 订阅
冒泡排序(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;
    
    }
    

     

     

     

     

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

     

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

    展开全文
  • 排序算法入门之冒泡排序

    万次阅读 多人点赞 2013-01-17 15:17:47
    本文章介绍的是排序算法中较简单的一种算法:冒泡排序 题外话:在深入学习更多排序算法后和在实际使用情况中,冒泡排序的使用还是极少的。它适合数据规模很小的时候,而且它的效率也比较低,但是作为入门的排序算法...

    在开发中,对一组数据进行有序地排列是经常需要做的事情,所以掌握几种甚至更多的排序算法是绝对有必要的

    本文章介绍的是排序算法中较简单的一种算法:冒泡排序

    题外话:在深入学习更多排序算法后和在实际使用情况中,冒泡排序的使用还是极少的。它适合数据规模很小的时候,而且它的效率也比较低,但是作为入门的排序算法,还是值得学习的


    先尝试用最简单的想法去实现排序,以此来比较学习冒泡排序

    问题:设有一数组,其大小为10个元素(int   str[10])数组内的数据是无序。现在要求我们通过编程将这个无序的数组变成一个从小到大排序的数组(从下标为0开始)

    思路:按照题目的要求,毫无疑问,正确的结果应该就像这样: 1 2 3 4 5 6 7 8 9 10   要做到这样,最简单和最直接想到的方法就是进行对比交换。

    • 首先,把10个数里最小的个数放到下标为0的位置上(str[0])
    • 通过将下标为0的数(str[0])与剩下其余9个数进行对比交换(将较少者放置在下标为0的位置上),就可以得到这10个数最小的那个
    • 10个数最小的那位确定后,接下来就要找剩下9个数最小的那个。
    • 因为已经确定出一个最小的数,所以就不要动str[0],直接从str[1]开始,与剩下的8个数对比交换,找出9个数中最小的那位放到下标为1(str[1])的位置上
    • 继续按照这个思路就可以将这十个数变成有序的(从小到大)的数组
    代码:
    #include <stdio.h>
    
    void swap(int *a, int *b); //交换两个数
    
    int main()
    {
    	int     str[10];
    	int     i, j;
    	//初始化数组为10 9 8 7 6 5 4 3 2 1
    	for (i = 0; i < 10; i++)
    	{
    		str[i] = 10 - i;
    	}
    	//排序,从a[0]开始排,从小到大
    	for (i = 0; i < 10; i++)
    	{
    		for (j = i + 1; j < 10; j++)
    		{
    			if (str[i] > str[j])
    			{
    				swap(&str[i], &str[j]);
    			}
    		}
    	}
            //将十个数输出
    	for (i = 0; i < 10; i++)
    		printf("%d\n", str[i]);
    	return    0;
    }
    void swap(int *a, int *b)
    {
    	int     c;
    	 c = *a;
    	*a = *b;
    	*b =  c;
    }

    这个方法是比较容易想到的实现方法。但存在不足:就是本来位于前面的较小数被交换到后面

    演示:
    开始:9 4 5 6 8 3 2 7 10 1  (下标从左到右分别是0~9)按照上面的程序进行对比交换
    第一次:4 9 5 6 8 3 2 7 10 1 
    第二次:4 9 5 6 8 3 2 7 10 1 
    。。。:(没有交换)
    第五次:3 9 5 6 8 4 2 7 10 1 
    第六次:2 9 5 6 8 3 4 7 10 1 
    。。。:(没有交换)
    第十次:1 9 5 6 8 3 4 7 10 2 

    可以看出,原来较小的数是在前面的,经过一轮的交换后放到后面了

    那么怎样解决这个不足呢?可以使用冒泡排序
    什么是冒泡排序呢?
    你可以这样理解:(从小到大排序)存在10个不同大小的气泡,由底至上地把较少的气泡逐步地向上升,这样经过遍历一次后,最小的气泡就会被上升到顶(下标为0),然后再从底至上地这样升,循环直至十个气泡大小有序。
    冒泡排序中,最重要的思想是两两比较,将两者较少的升上去
    冒泡排序最坏情况的时间复杂度是O(n²)

    代码:
    #include <stdio.h>
    void swap(int *a, int *b);
    int main()
    {
    	int    array[10] = {15, 225, 34, 42, 52, 6, 7856, 865, 954, 10};
    	int    i, j;
    	for (i = 0; i < 10; i++)
    	{
    		//每一次由底至上地上升
    		for (j = 9; j > i; j--)
    		{
    			if (array[j] < array[j-1])
    			{
    					swap(&array[j], &array[j-1]);
    			}
    		}
    	}
    	for (i = 0; i < 10; i++)
    	{
    		printf("%d\n", array[i]);
    	}
    	return    0;
    }
    void swap(int *a, int *b)
    {
    	int    temp;
    	temp = *a;
    	  *a = *b;
    	  *b = temp;
    }
    

    冒泡排序算法只会将较少的逐步向上推,不会造成文章前面所说的不足,这里就不给予演示。
    有些追求完美的人就会思考,冒泡排序能不能优化呢?
    答案是能的。如何优化的文章在这里










    展开全文
  • 排序—冒泡排序

    千次阅读 2018-04-24 21:22:40
    要想在实际中使用冒泡排序,写出代码,需要理解冒牌程序的算法以及基本思想。通过比较相邻的两个数据单元,如果前一个比后一个大,需要一个"中介值"来存储大的那个,然后通过中介值互换比较数的位置。实际...

    要想在实际中使用冒泡排序,写出代码,需要理解冒牌程序的算法以及基本思想。

    通过比较相邻的两个数据单元,如果前一个比后一个大,需要一个"中介值"来存储大的那个,然后通过中介值互换比较数的位置。

    实际操作:通过两个for循环。外层用于控制排序轮数,内层用于交换比较两个数的位置。


    代码如下:

    package exercise;
    public class BubbleSort {
    /**
    * @param args
    */
    public static void main(String[] args) {
    // TODO Auto-generated method stub
    int[]array = {23,56,9,69,76,102};
    BubbleSort sorter = new BubbleSort();
    sorter.sort(array);
    }
    public void sort(int[]array){
    for(int i = 1;i<array.length;i++){
    for(int j = 0;j<array.length-i;j++){
    if(array[j]>array[j+1]){
    //如果前一个>后一个,将前一个的值存在temp中,后一个的值赋值给前一个位置,然后将temp中的前一个赋值给后一个
    int temp = array[j];
    array[j] = array[j+1];
    array[j+1] = temp;
    }
    }
    }
    showArray(array);
    }
    public void showArray(int[] array){
    for(int i : array){
    System.out.println(">"+i);
    }
    }
    }



    展开全文
  • 冒泡排序

    千次阅读 2018-08-20 22:02:45
    思路:总共需要多少轮冒泡?需要n-1次。 冒泡:每一轮冒泡将会在剩下的(n-i)个元素中产生一个最大或者最少的值, 第一轮i等于0,第二轮i等于1… 而每一轮的冒泡需要比较(n-i-1)次即可确定一个极值,所以(n-i-1)...

    原理:
    思路:总共需要多少轮冒泡?需要n-1次。
    冒泡:每一轮冒泡将会在剩下的(n-i)个元素中产生一个最大或者最少的值,
    第一轮i等于0,第二轮i等于1…
    而每一轮的冒泡需要比较(n-i-1)次即可确定一个极值,所以(n-i-1)就是一轮冒泡要比较的次数

    所以具体第一轮参与冒泡的元素个数是与元素总量n有递减关系,并且参数冒泡的次数也是固定的为n-1,这种明显可量化的问题可以用一个很典型的二维嵌套循环来做控制。

    实现:

    public class BubbleSortTest {
    
        public static void main(String[] args) {
    
            int[] ints = {45, 67, 32, 90, 59, 12, 70};
            int n = ints.length;
            for (int i = 0; i < n - 1; i++) {
                for (int j = 0; j < n - i - 1; j++) {
                    if (ints[j] > ints[j + 1]) {
                        int temp = ints[j];
                        ints[j] = ints[j + 1];
                        ints[j + 1] = temp;
                    }
                }
            }
            System.out.println(Arrays.toString(ints));
    
        }
    }

    改进:
    改进是为也提高冒泡排序的效率,可从两点出发:

    1。减少每轮冒泡比较的元素个数,我们可以记下第一轮冒泡最后一次交换(j与j+1的交换)的下标j,而大于等于这个下标的元素都是已经排序好的。
    如何证明是排序好的?反推法:如果不是排序好的,证明前面有元素比后面大,而这些元素都是经过冒泡的,如果有比后面大的就一定会冒泡到后面,那么最后一次交换下标为j是不成立的,因为这会比j大。
    这个时候比较次数n-i-1可以用lastExchangeIndex代替

    2。每一轮冒泡记下是否有元素交换,如果没有则可以证明所有的元素已经是有序的,这个时候直接终止外层循环

    实现:

    public class BubbleSortTest {
    
        public static void main(String[] args) {
    
            int[] ints = {45, 67, 32, 90, 59, 12, 70};
            int n = ints.length;
    
            int sortBoard = n - 1;
            int lastExchangeIndex = 0;
    
            for (int i = 0; i < n - 1; i++) {
    
                boolean isSorted = true;
                for (int j = 0; j < sortBoard; j++) {
                    if (ints[j] > ints[j + 1]) {
                        int temp = ints[j];
                        ints[j] = ints[j + 1];
                        ints[j + 1] = temp;
                        isSorted = false;
                        lastExchangeIndex = j;
                    }
                }
                if (isSorted) {
                    break;
                }
                sortBoard = lastExchangeIndex;
            }
            System.out.println(Arrays.toString(ints));
    
        }
    }
    展开全文
  • 冒泡排序

    万次阅读 多人点赞 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....
  • 算法之冒泡排序 designed by kjqkdy 冒泡排序的基本思想:以n个人站队为例,从第一个开始,一次比较相邻的两个是否为逆序对(降序),若逆序就交换着两个人…直到比较n-1与n,经过一轮比较后,则最高的就站在一排的...
  • 冒泡排序算法

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

    万次阅读 多人点赞 2017-06-14 17:52:08
    按照从大到小排序。有2种思路,第一种,score[j] 和 score[j+1] 比较 如果 前者比后者小,把前者和后者调换顺序,两两调换后一轮下来 最小的会被排到最后去。每一轮j都从0开始,当i轮排序,就有最后面的i个数字...
  • 冒泡排序 详细解析

    万次阅读 多人点赞 2018-06-26 22:35:03
    对于刚接触编程和算法的朋友来说看起排序算法可能不太清晰,接下一起分析下冒牌排序假如我们得到一堆数 10 1 35 61 89 36 55 ,这些数字都放在桌子上,我们需要对其进行从小到大排序 大的在右边小的在左边;...
  • 【c语言】冒泡排序和选择排序

    万次阅读 多人点赞 2018-12-03 12:45:06
    1.冒泡排序 冒泡排序将一个列表中的两个元素进行比较,并将最小的元素交换到顶部。两个元素中较小的会冒到顶部,而较大的会沉到底部,该过程将被重复执行,直到所有元素都被排序。 冒泡排序示意图 以如图所示的...
  • 冒泡排序C语言

    2018-10-28 20:19:32
    冒泡排序(Bubble Sort),又被称为气泡排序或泡沫排序。 它是一种较简单的排序算法。它会遍历若干次要排序的数列,每次遍历时,它都会从前往后依次的比较相邻两个数的大小;如果前者比后者大,则交换它们的位置. ...
  • 冒泡排序C语言实现 - 源码详解

    千次阅读 2019-10-12 14:29:35
    冒泡排序 时间复杂度:O(N²) 稳定性:稳定 排序原理: 从前往后依次比较相邻的两个数据(如0:1 1:2 2:3 3:4 ... n:tail), 根据排序方向,将最大(最小)值移到最后面,一次遍历浮出一个数据, N次遍历...
  • 【算法】冒泡排序C语言实现

    千次阅读 2015-02-05 22:26:22
    冒泡排序应该是我大学里遇见的第一个排序算法,没记错的话应该还是C语言课上讲指针的时候老师给介绍的,当时因为心思完全没在学习上,还沉浸在高考结束的狂欢状态,想着进了大学就真的可以爱谁谁了,反正我是不要再努力...
  • C语言中选择排序和冒泡排序

    万次阅读 多人点赞 2018-06-17 15:25:55
    今天给大家分享一些关于C语言的算法,选择排序和冒泡排序。 对于选择排序,首先理解排序的思想。给定一个数组,这种思想首先假定数组的首元素为最大或者最小的。此时就要利用3个变量表示元素的下标。一个表示当前,...
  • C语言冒泡排序法(升序排序法)

    万次阅读 多人点赞 2017-07-26 17:58:59
    冒泡排序法:也叫升序排序法,但是相比起二分法查找只能应用于有序数列,二如何将一个无序数列变的有序就可以使用冒泡排序法!!! 对上面的过程进行总结: 该思想体现在成续上的解法是: 实例: 冒泡...
  • 八种基本的排序(1)——冒泡排序C语言实现)

    万次阅读 多人点赞 2018-07-20 11:52:48
    冒泡排序 冒泡排序 原理 时间复杂度 算法稳定性 源代码 原理 冒泡排序算法的原理如下: 1.比较相邻的元素。如果第一个比第二个大,就交换他们两个,这样是从小到大排。 (如果第一个比第二个小,交换...
  • 冒泡排序(Bubble Sort) 1、冒泡排序的思想:它重复地走访需要排序的数列,按照已经规定好的排序顺序,每一次比较相邻两个元素,如果他们的顺序错误就把他们交换过来。 直到没有再需要交换的元素,该数列就排序...
  • 排序算法c语言描述---双向冒泡排序

    万次阅读 多人点赞 2013-08-14 19:13:15
    排序算法系列学习,主要描述冒泡排序,选择排序,直接插入排序,希尔排序,堆排序,归并排序,快速排序等排序进行分析。 文章规划: 一。通过自己对排序算法本身的理解,对每个方法写个小测试程序。 具体思路分析...
  • 冒泡排序 基本思想: 冒泡排序算法的运作如下: 1.比较相邻的元素。如果第一个比第二个大,就交换他们两个。 2.对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。...
  • 冒泡排序C语言实现)

    万次阅读 2018-08-03 11:43:18
    void bubbleSort(int *arr,int n) { int m,i,j; for(i=0;i&lt;n-1;i++) for(j=0;j&lt;n-1-i;j++) if(arr[j]&gt;arr[j+1]) { m=arr[j]; arr[j]=arr[j+1]; arr[j+1]=m;... 

空空如也

1 2 3 4 5 ... 20
收藏数 172,873
精华内容 69,149
关键字:

冒泡排序