JS的算法--排序算法

冒泡排序

最简单的排序方式，但是运行性能是最差的。
冒泡排序比较任何两个相邻的项，如果第一个比第二个大，则交换它们。元素项向上移动至正确的顺序，就好像气泡升至表面一样，因此得名。
首先，声明一个名为length的变量，用来存储数组的长度。接着，外循环会从数组的第一位迭代至最后一位，它控制了在数组中经过多少轮排序。然后，内循环从第一位开始，每一轮减少（i+1）位，内循环实际上进行当前项和下一项的比较。如果这两项顺序不对（当前项比下一项大），则交换它们，意思是位置为j+1的值将会被换置到位置j处，反之亦然。

this.bubbleSort = function(array){
    var length = array.length;
    var swap = function(index1, index2){
        var aux = array[index1];
        array[index1] = array[index2];
        array[index2] = aux;
    };
    for (var i=0; i<length; i++){
        for (var j=0; j<length-i-1; j++ ){
            if (array[j] > array[j+1]){
                swap(j, j+1);
            }
        }
    }
    console.log(array);
};

选择排序

选择排序算法是一种原址比较排序算法。选择排序大致的思路是找到数据结构中的最小值并将其放置在第一位，接着找到第二小的值并将其放在第二位，以此类推。
首先声明一些将在算法内使用的变量。接着，外循环迭代数组，并控制迭代轮次（数组的第n个值–下一个最小值）。我们假设本迭代轮次的第一个值为数组最小值；如果是，则改变最小值至新最小值。当内循环结束，将得出数组第n小的值。最后，如果该最小值和原最小值不同，则交换其值。

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);
        }
    }
};

未完待续。。。

Posted by Hexo on 2017-07-31