乐趣区

关于javascript:简单排序算法冒泡排序插入排序选择排序JS实现

冒泡排序

冒泡排序可能是咱们接触的第一个排序算法了,比较简单也实用。

思路:顺次比拟相邻的两个元素,值大的就换到左边,一趟循环下来最左边就是最大的元素了。而后再从头开始,找第二大的元素,这样始终走下来,整个数组就有序了。

能够参考以下 gif 图,了解冒泡排序的思维。

那么 N 个数字要排序实现,总共进行 N - 1 趟排序,每 i 趟的排序次数为 (N-i) 次,所以须要比拟的次数就是[n(n-1)]/2,即工夫复杂度为 O(n^2)

间接上代码:

var bubbleSort = function(array){            // 冒泡排序
    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(array, j, j+1);
            }
        }
    }
}

var swap = function(array, index1, index2){        // 替换两个元素的地位
    var aux = array[index1];
    array[index1] = array[index2];
    array[index2] = aux;
}
var createNonSortedArray =function(size){        // 创立一个 size 大小的无序列表 ArrayList
    var array = new Array();
    for (var i = size; i > 0; i--) {array.push( parseInt(Math.random()*10000));
    }
    return array;
}

var arr = createNonSortedArray(10000);
bubbleSort(arr);

这个代码无论是最好的状况(数组有序),还是最坏状况(数组逆序),须要比拟的次数都是[n(n-1)]/2,也就是工夫复杂度均为 O(n^2),但如果是最好的状况,一趟比拟下来发现没有元素要替换,那么工夫复杂度就能降到 O(n),故再加一个标记位,就能让冒泡排序的最好状况工夫复杂度降到 O(n),如下:

var bubbleSort = function(array){
    var length = array.length,
    for (var i = 0; i < length; i++) {
        var didSwap = false;            // 设置标记位
        for (var j = 0; j < length-1-i; j++) {if (array[j] > array[j+1]) {swap(array, j, j+1);
                didSwap = true;
            }
        }
        if(!didSwap) break;                // 没有替换了,间接跳出循环
    }
}

插入排序

思维:一个元素就是有序的,那么从第二个元素开始,与它之前的元素作比拟,如果比之前的元素小,就替换地位。直到比某个元素大,就完结此次循环,也就找到了该元素应该在的地位了。把所有元素都走一遍,整个数组就有序了。

能够参考以下 gif 图,了解插入排序的思维。

在插入排序中,当待排序数组是有序时,是最优的状况,只需以后数跟前一个数比拟一下就能够了,这时一共须要比拟 N - 1 次,工夫复杂度为 O(n)。

最坏的状况是待排序数组是逆序的,此时须要比拟次数最多,总次数记为:1+2+3+…+N-1,所以,插入排序最坏状况下的工夫复杂度为 O(n^2)。

var insertionSort = function(array){
    var length = array.length,
        temp, j;
        for(var i = 1; i<length; i++){
        j = i;
        temp = array[i];
        while(j > 0 && array[j-1] > temp){array[j] = array[j-1];
            j--;
        }
        array[j] = temp;
    }
}

抉择排序

思维:从数组的第一个元素开始,一趟循环,找出最小的,放到第一个元素的地位,而后从第二个元素开始,反复之前的步骤,直到数组整个有序。

能够参考以下 gif 图,了解抉择排序的思维。
其中橙色示意以后排序趟的最左侧元素,绿色是这趟排序找到的最小元素的地位,灰背景是以后比拟的指针。

工夫复杂度其实与冒泡排序相似,也是一个 O(n)复杂度的算法。
代码如下:

var selectionSort = function(array){
    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(array, i, indexMin)        // 与之前冒泡排序 swap 办法统一,替换元素地位
        }
    }
}
退出移动版