冒泡排序和鸡尾酒排序的代码分析

2018-06-24 02:08:37来源：未知阅读 ()

冒泡排序

　　冒泡排序（buble sort）是一个比较入门的排序算法。顾名思义，它根据将最大（或最小）的数依次冒泡从而实现排序。

　　如下图所示，白色部分为待排序数组，红色部分为已找出的“较大的”数，每次迭代只需从白色部分找出其中最大的数字，直至找出n-1个“较大的”数后，数组已排序。

　　注：找出n-1个“较大的”数即可，因为最后一个必定为最小的数。

代码：

var s = [8, 7, 6, 5, 4, 3, 2, 1];
var bubleSort = function(array) {
    var temp;
    for(var i=0; i < array.length-1; i++) {　　　　//外层循环7次
        for(var j=0; j < array.length - i - 1; j++) {　　//已有i个较大数被冒泡，比较次数为n-i-1
            if(array[j] > array[j+1]) {
                temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }
        }
    }
};
bubleSort(s);
console.log(s);
//=>[ 1, 2, 3, 4, 5, 6, 7, 8 ]

代码分析：采用嵌套的for循环实现。其中外层循环控制找出”较大的“数的个数（n - 1）；内层循环控制找出第i个”较大的“数需要比较的次数（n - 1 - i），因为已有i个”较大的“数被冒泡，因此越到后面需要比较的次数就越少。

循环不变式：

　　第 1 次循环结束时，最后一个为最大数；

　　第 i 次循环结束时，s[n - i, n - 1]为按序排列的"较大"数；

　　...

　　第 n 次循环结束时，s[1，n - 1]为按序排列的"较大"数，而s[0]必定为最小数，因此整个数组已按序排列。

添加一行代码在控制台观察程序过程：

var s = [8, 7, 6, 5, 4, 3, 2, 1];
var bubleSort = function(array) {
    var temp;
    for(var i=0; i < array.length-1; i++) {
        for(var j=0; j < array.length - i - 1; j++) {
            if(array[j] > array[j+1]) {
                temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }
        }
        console.log(array);
    }
};
bubleSort(s);
console.log(s);
//=>[ 7, 6, 5, 4, 3, 2, 1, 8 ]
    [ 6, 5, 4, 3, 2, 1, 7, 8 ]
    [ 5, 4, 3, 2, 1, 6, 7, 8 ]
    [ 4, 3, 2, 1, 5, 6, 7, 8 ]
    [ 3, 2, 1, 4, 5, 6, 7, 8 ]
    [ 2, 1, 3, 4, 5, 6, 7, 8 ]
    [ 1, 2, 3, 4, 5, 6, 7, 8 ]
    [ 1, 2, 3, 4, 5, 6, 7, 8 ]

鸡尾酒排序

　　鸡尾酒排序（cocktail sort）对冒泡排序进行了优化，使得外层循环一次能找出两个已排序的数（最大和最小），可以理解为”双向“的冒泡排序。

　　注：因为鸡尾酒排序外层循环一次能找出两个排序数，故其外层循环次数折半，而内层循环则为两个并列的for循环（分别控制正向和反向）。总的来说，鸡尾酒排序大多数情况下要比冒泡排序效率高。

代码：

var s = [8, 7, 6, 5, 4, 3, 2, 1];
var cocktailSort = function(array) {
    var count = 0; 
    var temp;
    for(var i = 0; i < array.length/2; i++) {　　//外层循环次数折半
        for(var j = count; j < array.length - count -1; j++) {　　//一次正向循环
            if(array[j] > array[j+1]) {
                temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }
        }
        count++;　　　　//记录已找出"较大"数个数
        for(var k = array.length - 1 - count; k > count - 1; k--) {　　//一次反向循环
            if(array[k] < array[k-1]) {
                temp = array[k];
                array[k] = array[k-1];
                array[k-1] = temp;
            }
        }
    }
};
cocktailSort(s);
console.log(s);
//=>[ 1, 2, 3, 4, 5, 6, 7, 8 ]

代码分析：外层循环次数折半，因为外层循环一次内层已包含一次往返；内层正向循环找出"较大"数，其中起点为count（当前找出"较大"数个数）；内层反向循环的起点为n - 1 - count（该轮"较大"数的前一位），终点为count - 1（当前找出的"较小"数个数）。

循环不变式：

　　第 1 次循环结束时：第n个数为最大数，第1个数为最小数；

　　第 i 次循环结束时：s[n-i ,n-1]为按序排列的"较大"数，s[0, i-1]为按序排列的"较小"数；

　　...

　　第 n 次循环结束时： s[n - n/2, n-1]为按序排列的"较大数"，s[0, n/2-1]为按序排列的"较小"数，故整个数组已按序排列。

在控制台观察输出：

var s = [8, 7, 6, 5, 4, 3, 2, 1];
var cocktailSort = function(array) {
    var count = 0; 
    var temp;
    for(var i = 0; i < array.length/2; i++) {
        for(var j = count; j < array.length - count -1; j++) {
            if(array[j] > array[j+1]) {
                temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }
        }
        count++;
        for(var k = array.length - 1 - count; k > count - 1; k--) {
            if(array[k] < array[k-1]) {
                temp = array[k];
                array[k] = array[k-1];
                array[k-1] = temp;
            }
        }
        console.log(array);
    }
};
cocktailSort(s);
console.log(s);
//=>[ 1, 7, 6, 5, 4, 3, 2, 8 ]
    [ 1, 2, 6, 5, 4, 3, 7, 8 ]
    [ 1, 2, 3, 5, 4, 6, 7, 8 ]
    [ 1, 2, 3, 4, 5, 6, 7, 8 ]
    [ 1, 2, 3, 4, 5, 6, 7, 8 ]

但是，当遇到已按序排列的数组（如：[1, 2, 3, 4, 5, 6, 7, 8]）时，冒泡排序和鸡尾酒排序的结果过程均会做很多"无用功"。可以在循环内部定义一个flag，当某一轮循环数组元素不再发生交换时，便可认为数组已按序排列：

var s = [1,2,3,4,5,8,6,7];
var cocktailSort = function(array) {
    var count = 0; 
    var temp;
    for(var i = 0; i < array.length/2; i++) {
        var flag = false;　　//定义flag
        for(var j = count; j < array.length - count -1; j++) {
            if(array[j] > array[j+1]) {
                temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
                flag = true;　　//当发生交换时，改变flag的值为true
            }
        }
        count++;
        for(var k = array.length - 1 - count; k > count - 1; k--) {
            if(array[k] < array[k-1]) {
                temp = array[k];
                array[k] = array[k-1];
                array[k-1] = temp;
                flag = true;　　//当发生交换时，改变flag的值true
            }
        }
        console.log(array);
        if(!flag)
            break;
    }
};
cocktailSort(s);
//=>[ 1, 2, 3, 4, 5, 6, 7, 8 ]　　//输出结果显示，算法会提前结束
    [ 1, 2, 3, 4, 5, 6, 7, 8 ]