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

 

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

}


 

 

 

 

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

 

来源：逍遥游，欢迎分享本文，转载请保留出处！

 

排序算法之【冒泡排序】

在写代码之前我们需要对冒泡排序有一个逻辑上的理解：即什么是冒泡排序呢？

         冒泡排序是排序算法的其中一种，该排序的逻辑理解起来较为容易，理解上可以有两种方式，一种中正向的思维，一种是逆向的思维，什么意思呢？所谓的正向思维就是从前往后，从左往右，从上到下。那么逆向思维呢就正好与之相反。

         下面来说一正向思维下的冒泡排序：

          例如给你一组数据：{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);
            }
    }
}

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

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



 

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

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

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

            针对所有的元素重复以上的步骤，除了最后一个，即需要进行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(i=0;i<numbers.length;i++)
            System.out.print(numbers[i]+" ");
    }
}


三.debug命令调试


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

	
    右键单击Debug模式运行
	
	

	
    F8快捷键依次执行代码
	
 

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请点击http://www.captainbed.net

/*
 * Bubble Sort - by Chimomo
 *
 * 冒泡排序（Bubble Sort），是一种计算机科学领域较简单的排序算法。
 * 它重复地走访要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来，直到没有元素再需要交换为止。
 * 这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端，故名。
 *
 * 冒泡排序的算法如下：
 * 1、对无序区的每一对相邻元素作比较，从开始第一对到最后一对，如果相邻元素对中的第一个比第二个大，就交换他们两个。
 * 从而，最后一个元素必定是最大元素，把该最大元素移出无序区。
 * 2、持续对越来越少的无序区元素重复上面的步骤，直到没有任何一对元素需要比较为止。
 *
 * 时间复杂度：
 * 冒泡排序的平均时间复杂度为O（n^2）。
 *
 * 算法稳定性：
 * 冒泡排序就是把大的元素往后调。比较是相邻的两个元素作比较，交换也发生在这两个元素之间。
 * 所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的元素交换把这两个相等相邻起来，这时候也不会交换。
 * 所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定的排序算法。
 */

namespace BubbleSort
{
    using System;

    /// <summary>
    /// The program.
    /// </summary>
    public static class Program
    {
        /// <summary>
        /// 冒泡排序算法。
        /// </summary>
        /// <param name="arr">
        /// 待排序数组。
        /// </param>
        private static void BubbleSort(int[] arr)
        {
            Console.WriteLine("In Bubble Sort:");

            // 外循环是限制一次冒泡排序比较的元素个数。
            for (int i = arr.Length - 1; i >= 1; i--)
            {
                // 内循环比较0到i-1个元素的大小。
                for (int j = 0; j <= i - 1; j++)
                {
                    // 排序过程。
                    if (arr[j] > arr[j + 1])
                    {
                        int t = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = t;
                    }
                }

                Console.Write("Round {0}: ", arr.Length - i);
                foreach (int k in arr)
                {
                    Console.Write(k + " ");
                }

                Console.WriteLine();
            }
        }

        /// <summary>
        /// The main.
        /// </summary>
        public static void Main()
        {
            int[] arr = {1, 6, 4, 2, 8, 7, 9, 3, 10, 5};

            Console.WriteLine("Before Bubble Sort:");
            foreach (int i in arr)
            {
                Console.Write(i + " ");
            }

            Console.WriteLine("\r\n");

            BubbleSort(arr);

            Console.WriteLine("\r\nAfter Bubble Sort:");
            foreach (int i in arr)
            {
                Console.Write(i + " ");
            }
        }
    }
}

// Output:
/*
Before Bubble Sort:
1 6 4 2 8 7 9 3 10 5

In Bubble Sort:
Round 1: 1 4 2 6 7 8 3 9 5 10
Round 2: 1 2 4 6 7 3 8 5 9 10
Round 3: 1 2 4 6 3 7 5 8 9 10
Round 4: 1 2 4 3 6 5 7 8 9 10
Round 5: 1 2 3 4 5 6 7 8 9 10
Round 6: 1 2 3 4 5 6 7 8 9 10
Round 7: 1 2 3 4 5 6 7 8 9 10
Round 8: 1 2 3 4 5 6 7 8 9 10
Round 9: 1 2 3 4 5 6 7 8 9 10

After Bubble Sort:
1 2 3 4 5 6 7 8 9 10
*/