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

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

新老客户大回馈,云服务器低至5折

冒泡排序

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

 

--------------------------------------------------------------------------------------------------

注:本文为个人学习随笔,仅供个人学习使用,如有雷同,敬请原谅!

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:npm --save-dev --save 的区别

下一篇:js世界这么大,闭包想看看