排序-冒泡排序

左手的ㄟ右手 2022-09-29 04:09 191阅读 0赞

## 冒泡排序前言 ##

#### 顺序表结构 ####

#define MAXSIZE 10      /*用于要排序数组个数最大值，可根据需要修改*/
    typedef struct
    {
        int r[MAXSIZE+1];   /*用于存储要排序数组，r[0]用作哨兵或临时变量*/
        int length;         /*用于记录顺序表的长度*/
    }SqList;

#### 数组两元素交换函数 ####

/*交换L中数组r的下标为i和j的值*/
    void swap(SqList *L,int i,int j)
    {
        int temp = L->r[i];
        L->r[i] = L->r[j];
        L->r[j] = temp;
    }

## 1.冒泡排序的定义 ##

**冒泡排序(Bubble Sort)一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。**

## 2.冒泡排序的3种不同实现 ##

#### 1.最简单排序实现 ####

void BubbleSort0 (SqList *L)
    {
        int i,j;
        for(i=1; i<L->length; i++)
        {
            for(j=i+1; j<=L->length; j++)
            {
                if(L->r[i]>L->r[j])
                {
                    swap(L,i,j);    /*交换L->r[i]与L->r[j]的值*/
                }
            }
        }
    }

上面一段代码严格意义说，不算是标准的冒泡排序算法，因为它不满足“两两比较相邻记录”的冒泡排序思想，它更应该是最最简单的交换排序而已。它的思路就是让每一个关键字，都和它后面的每一个关键字比较，如果打则交换，这样第一位置的关键字在一次循环后一定变成最小值。如下图所示，假设我们待排序的关键字序列是\{9,1,5,8,3,7,4,6,2\}，当i=1时，9与1交换后，在一位置的1与后面的关键字比较都小，因此它就是最小值。当i=2时，第二位置先后由9换成5，换成3，换成2，完成了第二小的数字交换。后面的数字交换类似，不再介绍。

![AG0b9GU.jpg][]

**它应该算是最容易写出的排序代码了，不过这个简单易懂的代码，却是有缺陷的。观察后发现，在排序好1和2的位置后，对其余关键字的排序没有什么帮助(数字3反而还被换到了最后一位)。也就是说，这个算法的效率是非常低的。**

#### 2.冒泡排序算法 ####

/*对顺序表L作冒泡排序*/
    void BubbleSort(SqList *L)
    {
        int i,j;
        for(i=1; i<L->length; i++)
        {
            for(j=L->length-1; j>=i; j--)   /*注意j是从后往前循环*/
            {
                if(L->r[j]>L->[j+1])        /*若前者大于后者(与上一算法差异)*/
                {
                    swap(L,j,j+1);  /*交换L->r[j]与L->r[j+1]的值*/
                }
            }
        }
    }

依然假设我们待排序的关键字序列是\{9,1,5,8,3,7,4,6,2\}，当i=1时，变量j由8反向循环到1，逐个比较，将较小值交换到前面，直到最后找到最小值放置在了第1的位置。如下图所示，当i=1、j=8时，我们发现6>2，因此交换了它们的位置，j=7时，4>2，所以交换……直到j=2时，因为1<2，所以不交换。j=1时，9>1，交换，最终得到最小值1放置第一的位置。事实上，在不断循环的过程中，除了将关键字1放到第一的位置，我们还将关键字2从第九位置提到了第三的位置，显然这一算法比前面的要有进步，在上十万条数据的排序过程中，这种差异会体现出来。图中较小数字如同气泡慢慢浮到上面，因此就将此算法命名为冒泡算法。

![0vSTqFM.jpg][]

当i=2时，变量j由8反向循环到2，逐个比较，在将关键字2交换到第二位置的同时，也将关键字4和3有所提升。

![5su9Xd0.jpg][]

后面的数字变换很简单，就不详述了。

#### 3.冒泡排序优化 ####

上面的冒泡排序是否还可以优化？当然可以。假设我们待排序的序列是\{2,1,3,4,5,6,7,8,9\}，也就是说，除了第一和第二的关键字需要交换外，别的都已经是正常的顺序。当i=1时，交换了2和1，此时序列已经有序，但是算法仍然不依不饶地将i=2到9以及每个循环中的j循环都执行了一遍，尽管并没有交换数据，但是之后的大量比较还是大大地多余了，如下图所示：

![CfBQ8Uk.jpg][]

当i=2时，我们已经对9与8，8与7，……，3与2作了比较，没有任何数据交换，这就说明此序列已经有序，不需要再继续后面的循环判断工作了。为了实现这个想法，我们需要改进一下代码，增加一个标记变量flag来实现这一算法的改进。

/*对顺序表L作改进冒泡算法*/
    void BubbleSort2(SqList * L)
    {
        int i,j;
        Status flag = TRUE;     /*flag用来作为标记*/
        for(i=1; i<L->length&&flag; i++)        /*若flag为true则退出循环*/
        {
            flag = FALSE;
            for(j=L->length-1; j>=i; j--)
            {
                if(L->r[j]>L->r[j+1])
                {
                    swap(L,j,j+1);  /*交换L->r[j]与L->r[j+1]的值*/
                    flag = TRUE;    /*如果有数据交换，则flag为true*/
                }
            }
        }
    }

**代码改动的关键是在i变量的for循环中，增加了对flag是否为true的判断。经过这样的改进，冒泡排序在性能上就有了一些提升，可以避免因已经有序的情况下的无意义循环判断。**

## 3.冒泡排序复杂度分析 ##

分析一下它的时间复杂度。当最好的情况，也就是要排序的表本身就是有序的，那么我们比较次数，根据最后改进的代码，可以推断出就是n-1次的比较，没有数据交换，时间复杂度是O(n)。当最坏的情况，即待排序表示逆序的情况，此时需要比较![vK4hLSZ.png][]

次，并作等数量级的记录移动。因此，总的时间复杂度为O(n\*n)。

## 4.冒泡排序实现(Java) ##

#### 工程目录结构 ####

![DDbZ3JZ.png][]

**排序类**

package com.red.sort.bubble;
    
    public class BubbleSort {
    
        public void bubbleSort(int[] array) {
    
            int temp;// 记录临时中间值
    
            for (int i = 0; i < array.length - 1; i++) {
                for (int j = array.length - 2; j >= i; j--) {
                    if (array[j] > array[j + 1]) {
                        temp = array[j];
                        array[j] = array[j + 1];
                        array[j + 1] = temp;
                    }
                }
            }
        }
    
    }

**测试类**

package com.red.sort.bubble;
    
    public class Main {
        public static void main(String[] args) {
            int[] array = new int[] { 9, 1, 5, 8, 3, 7, 4, 6, 2 };
            BubbleSort bubbleSort = new BubbleSort();
            bubbleSort.bubbleSort(array);
    
            for (int i = 0; i < array.length; i++) {
                System.out.print(array[i] + " ");
            }
        }
    }

**输出结果：**

1 2 3 4 5 6 7 8 9

## 5.冒泡排序优化实现(Java) ##

**工程目录结构**

![cZgfzr6.png][]

**排序类**

package com.red.sort.bubble;
    
    public class BubbleSort2 {
    
        public void bubbleSort(int[] array) {
            boolean flag = true;    //flag用来作为标记
            int temp;       //临时变量
            for(int i = 0; i < array.length-1; i++){
                flag = false;   //初始为false
                for(int j = array.length - 2; j >= i; j--){
                    if (array[j] > array[j + 1]) {
                        temp = array[j];
                        array[j] = array[j + 1];
                        array[j + 1] = temp;
                        flag = true;    //如果有数据交换，则flag为true
                    }
                }
            }
        }
    
    }

**测试类**

package com.red.sort.bubble;
    
    public class Main {
        public static void main(String[] args) {
            int[] array = new int[] { 9, 1, 5, 8, 3, 7, 4, 6, 2 };
            BubbleSort2 bubbleSort2 = new BubbleSort2();
            bubbleSort2.bubbleSort(array);
    
            for (int i = 0; i < array.length; i++) {
                System.out.print(array[i] + " ");
            }
        }
    }

**输出结果：**

1 2 3 4 5 6 7 8 9

[AG0b9GU.jpg]: http://i.imgur.com/AG0b9GU.jpg
[0vSTqFM.jpg]: http://i.imgur.com/0vSTqFM.jpg
[5su9Xd0.jpg]: http://i.imgur.com/5su9Xd0.jpg
[CfBQ8Uk.jpg]: http://i.imgur.com/CfBQ8Uk.jpg
[vK4hLSZ.png]: http://i.imgur.com/vK4hLSZ.png
[DDbZ3JZ.png]: http://i.imgur.com/DDbZ3JZ.png
[cZgfzr6.png]: http://i.imgur.com/cZgfzr6.png