当javascript遇上排序算法

当javascript遇上---快速排序：

快速排序算法描述：说到快速排序，我觉得《坐在马桶上看算法》这一系列的讲解很生动。其中快速排序的部分：http://developer.51cto.com/art/201403/430986.htm。、分别从初始序列“6  1  2 7  9  3  4  5 10  8”两端开始“探测”。先从右往左找一个小于6的数，再从左往右找一个大于6的数，然后交换他们。这里可以用两个变量i和j，分别指向序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵i”和“哨兵j”。刚开始的时候让哨兵i指向序列的最左边（即i=1），指向数字6。让哨兵j指向序列的最右边（即=10），指向数字。其时间复杂度为O(nlogn)。

function quickSort(left,right){
    var i,j,t,temp;
    if(left>right)
        return;
    temp=arr[left];
    i=left;
    j=right;
    while(i != j){
        //从右侧先找
        while(arr[j] >= temp && i<j){
            j--;
        }
        //从左侧找
        while(arr[i] < = temp && i<j){
            i++;
        }
        //交换位置
        if(i<j){
            t=arr[i];
            arr[i]=arr[j];
            arr[j]=t;
        }
    }
    arr[left]=arr[i];
    arr[i]=temp;
    quickSort(left,i-1);
    quickSort(i+1,right);

}

当javascript遇上---插入排序：

  插入排序算法描述：插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置，直到全部插入完毕。开始的第一个元素可以认为已经被排序，取出下一个元素，在已经排序的元素序列中向前扫描。其时间复杂度为O(n^2)

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

当javascript遇上---选择排序：

选择排序算法描述：选择排序就是直接从待排序数组中选择最小的元素放入一个新的数组中。其时间复杂度为O(n^2)

function selectSort(arr){
    var length = arr.length;
    var i, j, minIndex, minValue, temp;
    for(i = 0; i<length - 1; i++){
        minIndex = i;
        minValue = arr[i];
        for(j = i+1; j<length; j++){
            if(arr[j] < minValue){
                minValue = arr[j];
                minIndex = j;
            }
        }
        //将剩余序列最小值和位置i交换
        temp = arr[i];
        arr[i] = minValue;
        arr[minIndex] = temp;
    }
    return arr;
}

当javascript遇上---归并排序：

归并排序算法描述：将序列元素两两进行归并，得到n/2个长度为2的有序子序列，重复上述步骤，直到所有记录归并成一个长度为n的有序序列。其时间复杂度为O(nlogn)

function merge(left,right){
    var temp = [];
    while(left.length && right.length){
        if(left[0] < right[0])
            temp.push(left.shift());
        else
            temp.push(right.shift());
    }

    //left或right有剩余元素
    return temp.concat(left,right);
}
function mergeSort(arr){
    if(arr.length == 1){
        return arr;
    }
    var mid = Math.floor(arr.length/2);
    var left = arr.slice(0,mid);
    var right = arr.slice(mid);
    
    return merge(mergeSort(left),mergeSort(right));
}

当javascript遇上---冒泡排序：

冒泡排序算法描述：比较相邻的元素，如果第一个比第二个大，就交换他们。。对每一对相邻元素都进行同样的工作，这样，最大的元素在将会“沉”到最底下。时间复杂度为O(n^2)。

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

 Floyd算法：http://www.cnblogs.com/ahalei/p/3622328.html

Dijkstra算法：http://www.cnblogs.com/ahalei/p/3635090.html