• 冒泡排序


    概要

    本章介绍排序算法中的冒泡排序,重点讲解冒泡排序的思想。

    目录
    1. 冒泡排序介绍
    2. 冒泡排序图文说明
    3. 冒泡排序的时间复杂度和稳定性
    4. 冒泡排序实现
    4.1 冒泡排序C实现
    4.2 冒泡排序C++实现
    4.3 冒泡排序Java实现

    转载请注明出处:http://www.cnblogs.com/skywang12345/p/3596232.html


    更多内容:数据结构与算法系列 目录

    冒泡排序介绍

    冒泡排序(Bubble Sort),又被称为气泡排序或泡沫排序。

    它是一种较简单的排序算法。它会遍历若干次要排序的数列,每次遍历时,它都会从前往后依次的比较相邻两个数的大小;如果前者比后者大,则交换它们的位置。这样,一次遍历之后,最大的元素就在数列的末尾! 采用相同的方法再次遍历时,第二大的元素就被排列在最大元素之前。重复此操作,直到整个数列都有序为止!

    冒泡排序图文说明

    冒泡排序C实现一

    void bubble_sort1(int a[], int n)
    {
        int i,j;
    
        for (i=n-1; i>0; i--)
        {
            // 将a[0...i]中最大的数据放在末尾
            for (j=0; j<i; j++)
            {
                if (a[j] > a[j+1])
                    swap(a[j], a[j+1]);
            }
        }
    }

    下面以数列{20,40,30,10,60,50}为例,演示它的冒泡排序过程(如下图)。

    我们先分析第1趟排序
    当i=5,j=0时,a[0]<a[1]。此时,不做任何处理!
    当i=5,j=1时,a[1]>a[2]。此时,交换a[1]和a[2]的值;交换之后,a[1]=30,a[2]=40。
    当i=5,j=2时,a[2]>a[3]。此时,交换a[2]和a[3]的值;交换之后,a[2]=10,a[3]=40。
    当i=5,j=3时,a[3]<a[4]。此时,不做任何处理!
    当i=5,j=4时,a[4]>a[5]。此时,交换a[4]和a[5]的值;交换之后,a[4]=50,a[3]=60。

    于是,第1趟排序完之后,数列{20,40,30,10,60,50}变成了{20,30,10,40,50,60}。此时,数列末尾的值最大。

    根据这种方法:
    第2趟排序完之后,数列中a[5...6]是有序的。
    第3趟排序完之后,数列中a[4...6]是有序的。
    第4趟排序完之后,数列中a[3...6]是有序的。
    第5趟排序完之后,数列中a[1...6]是有序的。

    第5趟排序之后,整个数列也就是有序的了。

    冒泡排序C实现二

    观察上面冒泡排序的流程图,第3趟排序之后,数据已经是有序的了;第4趟和第5趟并没有进行数据交换。
    下面我们对冒泡排序进行优化,使它效率更高一些:添加一个标记,如果一趟遍历中发生了交换,则标记为true,否则为false。如果某一趟没有发生交换,说明排序已经完成!

    void bubble_sort2(int a[], int n)
    {
        int i,j;
        int flag;                 // 标记
    
        for (i=n-1; i>0; i--)
        {
            flag = 0;            // 初始化标记为0
    
            // 将a[0...i]中最大的数据放在末尾
            for (j=0; j<i; j++)
            {
                if (a[j] > a[j+1])
                {
                    swap(a[j], a[j+1]);
                    flag = 1;    // 若发生交换,则设标记为1
                }
            }
    
            if (flag==0)
                break;            // 若没发生交换,则说明数列已有序。
        }
    }

    冒泡排序的时间复杂度和稳定性

    冒泡排序时间复杂度

    冒泡排序的时间复杂度是O(N2)
    假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N),需要遍历多少次呢?N-1次!因此,冒泡排序的时间复杂度是O(N2)。

    冒泡排序稳定性

    冒泡排序是稳定的算法,它满足稳定算法的定义。
    算法稳定性 -- 假设在数列中存在a[i]=a[j],若在排序之前,a[i]在a[j]前面;并且排序之后,a[i]仍然在a[j]前面。则这个排序算法是稳定的!

     

    冒泡排序实现

    冒泡排序C实现
    实现代码(bubble_sort.c)

     1 /**
     2  * 冒泡排序:C 语言
     3  *
     4  * @author skywang
     5  * @date 2014/03/11
     6  */
     7 
     8 #include <stdio.h>
     9 
    10 // 数组长度
    11 #define LENGTH(array) ( (sizeof(array)) / (sizeof(array[0])) )
    12 // 交互数值
    13 #define swap(a,b)    (a^=b,b^=a,a^=b)
    14 
    15 /*
    16  * 冒泡排序
    17  *
    18  * 参数说明:
    19  *     a -- 待排序的数组
    20  *     n -- 数组的长度
    21  */
    22 void bubble_sort1(int a[], int n)
    23 {
    24     int i,j;
    25 
    26     for (i=n-1; i>0; i--)
    27     {
    28         // 将a[0...i]中最大的数据放在末尾
    29         for (j=0; j<i; j++)
    30         {
    31             if (a[j] > a[j+1])
    32                 swap(a[j], a[j+1]);
    33         }
    34     }
    35 }
    36 
    37 /*
    38  * 冒泡排序(改进版)
    39  *
    40  * 参数说明:
    41  *     a -- 待排序的数组
    42  *     n -- 数组的长度
    43  */
    44 void bubble_sort2(int a[], int n)
    45 {
    46     int i,j;
    47     int flag;                 // 标记
    48 
    49     for (i=n-1; i>0; i--)
    50     {
    51         flag = 0;            // 初始化标记为0
    52 
    53         // 将a[0...i]中最大的数据放在末尾
    54         for (j=0; j<i; j++)
    55         {
    56             if (a[j] > a[j+1])
    57             {
    58                 swap(a[j], a[j+1]);
    59                 flag = 1;    // 若发生交换,则设标记为1
    60             }
    61         }
    62 
    63         if (flag==0)
    64             break;            // 若没发生交换,则说明数列已有序。
    65     }
    66 }
    67 
    68 void main()
    69 {
    70     int i;
    71     int a[] = {20,40,30,10,60,50};
    72     int ilen = LENGTH(a);
    73 
    74     printf("before sort:");
    75     for (i=0; i<ilen; i++)
    76         printf("%d ", a[i]);
    77     printf("
    ");
    78 
    79     bubble_sort1(a, ilen);
    80     //bubble_sort2(a, ilen);
    81 
    82     printf("after  sort:");
    83     for (i=0; i<ilen; i++)
    84         printf("%d ", a[i]);
    85     printf("
    ");
    86 }
    View Code

    冒泡排序C++实现
    实现代码(BubbleSort.cpp)

     1 /**
     2  * 冒泡排序:C++
     3  *
     4  * @author skywang
     5  * @date 2014/03/11
     6  */
     7 
     8 #include <iostream>
     9 using namespace std;
    10 
    11 /*
    12  * 冒泡排序
    13  *
    14  * 参数说明:
    15  *     a -- 待排序的数组
    16  *     n -- 数组的长度
    17  */
    18 void bubbleSort1(int* a, int n)
    19 {
    20     int i,j,tmp;
    21 
    22     for (i=n-1; i>0; i--)
    23     {
    24         // 将a[0...i]中最大的数据放在末尾
    25         for (j=0; j<i; j++)
    26         {
    27             if (a[j] > a[j+1])
    28             {    
    29                 // 交换a[j]和a[j+1]
    30                 tmp = a[j];
    31                 a[j] = a[j+1];
    32                 a[j+1] = tmp;
    33             }
    34         }
    35     }
    36 }
    37 
    38 /*
    39  * 冒泡排序(改进版)
    40  *
    41  * 参数说明:
    42  *     a -- 待排序的数组
    43  *     n -- 数组的长度
    44  */
    45 void bubbleSort2(int* a, int n)
    46 {
    47     int i,j,tmp;
    48     int flag;                 // 标记
    49 
    50     for (i=n-1; i>0; i--)
    51     {
    52         flag = 0;            // 初始化标记为0
    53 
    54         // 将a[0...i]中最大的数据放在末尾
    55         for (j=0; j<i; j++)
    56         {
    57             if (a[j] > a[j+1])
    58             {
    59                 // 交换a[j]和a[j+1]
    60                 tmp = a[j];
    61                 a[j] = a[j+1];
    62                 a[j+1] = tmp;
    63 
    64                 flag = 1;    // 若发生交换,则设标记为1
    65             }
    66         }
    67 
    68         if (flag==0)
    69             break;            // 若没发生交换,则说明数列已有序。
    70     }
    71 }
    72 
    73 int main()
    74 {
    75     int i;
    76     int a[] = {20,40,30,10,60,50};
    77     int ilen = (sizeof(a)) / (sizeof(a[0]));
    78 
    79     cout << "before sort:";
    80     for (i=0; i<ilen; i++)
    81         cout << a[i] << " ";
    82     cout << endl;
    83 
    84     bubbleSort1(a, ilen);
    85     //bubbleSort2(a, ilen);
    86 
    87     cout << "after  sort:";
    88     for (i=0; i<ilen; i++)
    89         cout << a[i] << " ";
    90     cout << endl;
    91 
    92     return 0;
    93 }
    View Code

    冒泡排序Java实现
    实现代码(BubbleSort.java)

     1 /**
     2  * 冒泡排序:Java
     3  *
     4  * @author skywang
     5  * @date 2014/03/11
     6  */
     7 
     8 public class BubbleSort {
     9 
    10     /*
    11      * 冒泡排序
    12      *
    13      * 参数说明:
    14      *     a -- 待排序的数组
    15      *     n -- 数组的长度
    16      */
    17     public static void bubbleSort1(int[] a, int n) {
    18         int i,j;
    19 
    20         for (i=n-1; i>0; i--) {
    21             // 将a[0...i]中最大的数据放在末尾
    22             for (j=0; j<i; j++) {
    23 
    24                 if (a[j] > a[j+1]) {
    25                     // 交换a[j]和a[j+1]
    26                     int tmp = a[j];
    27                     a[j] = a[j+1];
    28                     a[j+1] = tmp;
    29                 }
    30             }
    31         }
    32     }
    33 
    34     /*
    35      * 冒泡排序(改进版)
    36      *
    37      * 参数说明:
    38      *     a -- 待排序的数组
    39      *     n -- 数组的长度
    40      */
    41     public static void bubbleSort2(int[] a, int n) {
    42         int i,j;
    43         int flag;                 // 标记
    44 
    45         for (i=n-1; i>0; i--) {
    46 
    47             flag = 0;            // 初始化标记为0
    48             // 将a[0...i]中最大的数据放在末尾
    49             for (j=0; j<i; j++) {
    50                 if (a[j] > a[j+1]) {
    51                     // 交换a[j]和a[j+1]
    52                     int tmp = a[j];
    53                     a[j] = a[j+1];
    54                     a[j+1] = tmp;
    55 
    56                     flag = 1;    // 若发生交换,则设标记为1
    57                 }
    58             }
    59 
    60             if (flag==0)
    61                 break;            // 若没发生交换,则说明数列已有序。
    62         }
    63     }
    64 
    65     public static void main(String[] args) {
    66         int i;
    67         int[] a = {20,40,30,10,60,50};
    68 
    69         System.out.printf("before sort:");
    70         for (i=0; i<a.length; i++)
    71             System.out.printf("%d ", a[i]);
    72         System.out.printf("
    ");
    73 
    74         bubbleSort1(a, a.length);
    75         //bubbleSort2(a, a.length);
    76 
    77         System.out.printf("after  sort:");
    78         for (i=0; i<a.length; i++)
    79             System.out.printf("%d ", a[i]);
    80         System.out.printf("
    ");
    81     }
    82 }
    View Code

    上面3种实现的原理和输出结果都是一样的。下面是它们的输出结果:

    before sort:20 40 30 10 60 50 
    after  sort:10 20 30 40 50 60
  • 相关阅读:
    数学是最好的语言
    人类的语言--自然语言--》逻辑语言
    为什么大脑喜欢看图?
    思考是调用大脑存储的上下文对输入信息进行处理的过程
    Redis的相关问题总结
    TP5 关联模型使用(嵌套关联、动态排序以及隐藏字段)
    array_column 函数, 以及在PHP5.5之下的替代方法
    thinkphp在app接口开发过程中的通讯安全认证
    PHP开发APP接口实现--基本篇
    分布式与集群的区别是什么?
  • 原文地址:https://www.cnblogs.com/skywang12345/p/3596232.html
一二三 - 开发者的网上家园