Web34.拓展任务

简单的排序算法

主要研究N个正整数排序
算法的简单归纳：1.输入: 一个算法必须有零个或以上输入量
                             2.输出 :一个算法应该有一个或以上输出量
                             3.明确性:  算法的描述必须无歧义
                             4.有限性 : 必须在有限个步骤内结束
                             5.有效性:又称可行性,能够被执行者实现

定义问题

数组array 含有N个正整数
输入量为array
请将array中的数字从小到大排列
输出量为排好序的数组

例如 
var array = [5,2,4,6,8]
function sort(){
    你的代码
}
sort(array) === [2,4,5,6,8]

不会做

遇到思维障碍怎么办
1.将抽象的问题转化为具体的问题
2.将没见过的问题转化为见过的问题

1.冒泡排序(教官双手算法:较高的往后站)

通过一轮遍历,最高的一定到右边去了

function sort(array){
    var i,j         
    for(i=0; i<array.length; i++){  //第i次
        for(j=0; j<array.length-1-i; j++){   //每一次的起点
           //console.log(array[j]+','+array[j+1]) 
           if(array[j]<=array[j+1]){
           
            }else{
                swap(array, j, j+1)
                //console.log('swap:'+array[j]+','+array[j+1])
            }  
        }
    }
    return array;
}

function swap(array, a,b){
    var temp = array[a]
    array[a] = array[b]
    array[b] = temp
}

console.log(sort[3,5,2,4,1])
console.log(sort[1,2,1,2,1])
console.log(sort[1])
console.log(sort[])

2.选择排序(教官一指 最矮的到前面来)

function sort(array){
    var i
    var j
    var indexOfMin
    for(i=0; i<array.length; i++){
        indexOfMin = i
        for(j=i+1; j<array.length; j++){
            if(array[j] < array[indexOfMin]){
                swap(array, j, indexOfMin)
            }
        }
        if(indexOfMin !== i){
           swap(array, i, indexOfMin)     
        }
    }
    return array;
}



function swap(){
    var temp = array[a]
    array[a] = array[b]
    array[b] = temp
}
console.log(sort([3,5,2,4,1]))
console.log(sort([1,2,1,2,1]))
console.log(sort([1]))
console.log(sort([]))

3.插入排序(起牌算法)

打个比方就类比水浒传一百单八将的排名吧，每个好汉来了不知道自己排老几，怎么办，那就和已经排过级别的人比较，然后找到其对应的位置，单八将宋万、杜迁先上的梁山，先默认杜迁第一来的也是单八将最厉害的，然后宋万来了，一比较宋万厉害，那宋万排第一，杜迁排第二，接下来朱贵来了，朱贵没他们两个厉害，那就排第三，再后来林冲来了，林冲比他们三个都厉害，那林冲排第一，宋万第二，杜迁第三，朱贵第四，依次类推。梁山排名其实就是典型的插入排序。

function insertSort(arr){
    for(var i=1; i<arr.length; i++){
        var key = arr[i]
        var j = i -1
        while( arr[j] > key){
            arr[j + 1] = arr[j]
            j--
        }
        arr[j + 1] = key
    }
    return array;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(insertSort(arr));

4.归并排序(领导算法)

function mergeSort(arr) { //采用自上而下的递归方法
　　var len = arr.length;
　　if(len < 2) {
　　　　return arr;
　　}
　　var middle = Math.floor(len / 2),
　　left = arr.slice(0, middle),
　　right = arr.slice(middle);
　　return merge(mergeSort(left), mergeSort(right));
}
 
function merge(left, right){
　　var result = [];
　　//console.time('归并排序耗时');
　　while (left.length && right.length) {
　　　　if (left[0] <= right[0]) {
　　　　　　result.push(left.shift());
　　　　} else {
　　　　　　result.push(right.shift());
　　　　}
　　}
 
　　while (left.length){
　　　　result.push(left.shift());
　　}
　　while (right.length){
　　　　result.push(right.shift());
　　}
　　//console.timeEnd('归并排序耗时');
　　return result;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(mergeSort(arr));

5.快速排序(自私算法：我前面的都比我矮 我后面的都比我高)

function quickSort(array, left, right) {
　　console.time('1.快速排序耗时');
　　if (left < right) {
　　　　var x = array[right], i = left - 1, temp;
　　　　for (var j = left; j <= right; j++) {
　　　　　　if (array[j] <= x) {
　　　　　　　　i++;
　　　　　　　　temp = array[i];
　　　　　　　　array[i] = array[j];
　　　　　　　　array[j] = temp;
　　　　　　}
　　　　}
　　　　console.log(array) ;
　　　　console.log(left,i) ;
　　　　quickSort(array, left, i - 1);
　　　　console.log(array)
　　　　console.log(i,right)
　　　　quickSort(array, i + 1, right);
　　}
　　console.timeEnd('1.快速排序耗时');
　　console.log(array)
　　return array;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(quickSort(arr,0,arr.length-1));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50];