Algorithms(二)

作者 johansen 日期 2017-02-03
技术小记
Algorithms(二)

排序算法

即上次对于搜索算法的学习，我们还记得搜索算法第一步是构建一个有序的数组结构，那么怎么获得一个有序的数组结构，首先介绍一个排序算法–冒泡排序,以及冒泡排序的优化。

算法介绍

  • 冒泡排序
    冒泡排序比较任何两个相邻的项，如果第一个比第二个大，则交换它们。元素项向上移动至 正确的顺序，就好像气泡升至表面一样，冒泡排序因此得名。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    var swap = function(index1, index2){
            var aux = array[index1];
            array[index1] = array[index2];
            array[index2] = aux;
    };
    //冒泡算法
    this.bubbleSort = function(){
            var length = array.length;          
            for (var i=0; i<length; i++){       
            for (var j=0; j<length-1; j++ ){ 
                if (array[j] > array[j+1]){  
                        swap(j, j+1);//交换元素
                } }
           } 
        };

    举例算法图解：
    blur img

    注意当算法执行外循环的第二轮的时候，数字4和5已经是正确排序的了。尽管如此，在后续 比较中，它们还一直在进行着比较，即使这是不必要的。因此，我们可以稍稍改进一下冒泡排序 算法。

  • 改进后的冒泡算法
    如果从内循环减去外循环中已跑过的轮数，就可以避免内循环中所有不必要的比较。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    var swap = function(index1, index2){
            var aux = array[index1];
            array[index1] = array[index2];
            array[index2] = aux;
    };
    //冒泡算法
    this.bubbleSort = function(){
            var length = array.length;          
            for (var i=0; i<length; i++){  
            //去掉不必要的比较过程     
            for (var j=0; j<length-1-i; j++ ){ 
                if (array[j] > array[j+1]){  
                        swap(j, j+1);//交换元素
                } }
        } 
        };

  • 选择排序
    选择排序算法是一种原址比较排序算法。选择排序大致的思路是找到数据结构中的最小值并将其放置在第一位，接着找到第二小的值并将其放在第二位，以此类推。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    var swap = function(index1, index2){
            var aux = array[index1];
            array[index1] = array[index2];
            array[index2] = aux;
    };
    //选择排序算法
    this.selectionSort = function(){
        var length = array.length,
        indexMin;
        for (var i=0; i<length-1; i++){
            indexMin = i;
            for (var j=i; j<length; j++){
                if(array[indexMin]>array[j]){ 
                    indexMin = j;
                } 
            }
            if (i !== indexMin){
                    swap(i, indexMin);
            } 
        }
    };

举例算法图解：
blur img

分析两个算法的时间复杂度如下

算法 最好情况 一般情况 最差情况
冒泡排序 O(n) O(n^2) O(n^2)
选择排序 O(n^2) O(n^2) O(n^2)
FEATURED TAGS
技术小记