常见算法小结

排序就是将内容中的关键信息按照递增或者递减的方式进行排列，常见的排序算法有冒泡排序，选择排序，插入排序，希尔排序，快速排序，归并排序等，下面对其中三种进行总结。

1、冒泡排序

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，当如果两个元素相等，则不会交换；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变。冒泡排序时间复杂度最好的情况为O(n),最坏的情况是O(n^2)。

var array = [21, 34, 1, 3, 53, 2]
var i, j, temp
for (i = 0; i < array.length; i++){
    for(j=0;j<array.length-1-i;j++){
        if(array[j]>array[j+1]){
            temp=array[j]
            array[j]=array[j+1]
            array[j+1]=temp
        }
    }
}
console.log(array)
console.log("done")

2、选择排序

选择排序是首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。以此类推，直到所有元素均排序完毕。时间复杂度为O(n^2)，每次都能确定一个元素所在的最终位置，比较次数与初始序列无关。

var array = [21, 34, 1, 3, 53, 2]
var i, j, temp
for (i = 0; i < array.length-1; i++) {
    for (j = i+1; j < array.length; j++) {
        if (array[i] > array[j]) {
            temp = array[i]
            array[i] = array[j]
            array[j] = temp
        }
    }
}
console.log(array)
console.log("done")

3、插入排序

插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开 始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相 等的，那么插入元素把想插入的元素放在相等元素的后面。时间复杂度也为O(n^2)。

var array = [21, 34, 2, 3, 53, 1]
var len = array.length;
var temp;
for (var i = 1; i < len; i++) {
    var j = i - 1;
    temp = array[i];
    while (j >= 0 && array[j] > temp) {
        array[j + 1] = array[j];
        j--;
    }
    array[j + 1] = temp;
}
console.log(array)
console.log("done")

小结

一个排序算法的性能不仅与时间和空间复杂度，还得考虑稳定性，及其适应的场景，在不同的场景可以选择不同的排序算法来达到最优的效果。