js排序算法

1.冒泡排序

原理

依次比较相邻的两个值，如果后面的比前面的小，则将小的元素排到前面。依照这个规则进行多次并且递减的迭代，直到顺序正确。

var examplearr=[4,24,15,37,55,71,28,30];
function sort(arr){
    for(i=0;i<arr.length-1;i++){
        for(j=0;j<arr.length-1-i;j++){
            if(arr[j]>arr[j+1]){
                var temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
            }
        }
    }
    return arr;
}
sort(examplearr);
console.log(examplearr);

解析

使用两个循环

当i=0的时候，执行内层循环，从j=0执行到j=6,这也就是第一遍排序，结果是将最大的数排到了最后。
当i=1的时候，再次执行内层循环，由于最大的数已经在最后了，没有必要去比较数组的最后两项，这也是为什么要用j<arr.length-1-i

按照这个规律，每次将剩下数组里面最大的一个数排到最后面，当执行到i=6时，就只需要比较第一项和第二项，交换之后就排序结束。

算法分析

最佳情况：T(n) = O(n)
最差情况：T(n) = O(n2)
平均情况：T(n) = O(n2)

2.选择排序

原理

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

function selectSort(arr){
    var len=arr.length;
    var temp;
    for(var i=0;i<len-1;i++){
        for(var j=i+1;j<len;j++){
            if(arr[j]<arr[i]){
                temp=arr[j];
                arr[j]=arr[i];
                arr[i]=temp;
            }
        }
        i++;
    }
    return arr;
}

解析

把每一个数都与第一个数比较，如果小于第一个数，就把它们交换位置；这样一轮下来，最小的数就排到了最前面；重复n-1轮，就实现了选择排序

选择排序和冒泡排序思想上有些相近

算法分析

最佳情况：T(n) = O(n2)
最差情况：T(n) = O(n2)
平均情况：T(n) = O(n2)

3.插入排序

插入排序每次排一个数组项，以此方式构建最后的排序数组，假定第一项已经排序了，接着，它和第二项进行比较，第二项是应该待在原位还是插到第一项之前呢？这样头两项就已经正确排序，接着和第三项比较（它是该插入第一、第二还是第三的位置呢？）

this.insertionSort = function(){
    var length = array.length,
        j, temp;
    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;
    }
};

排序过程大概如下：

从第一个元素开始，该元素可以认为已经被排序；
取出下一个元素，在已经排序的元素序列中从后向前扫描；
如果该元素（已排序）大于新元素，将该元素移到下一位置；
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置后；
重复步骤2~5。

算法分析

最佳情况：输入数组按升序排列。T(n) = O(n)
最坏情况：输入数组按降序排列。T(n) = O(n2)
平均情况：T(n) = O(n2)

未完待续。。。