算法

• 什么是算法
  • 输入：一个算法必须有零个或以上输入量
  • 输出：一个算法应有一个或以上输出量
  • 明确性：算法的描述必须无歧义，实际运行结果是确定的
  • 有限性：必须在有限个步骤内结束
  • 有效性：又称可行性，能够被执行者实现
• 遇到思路障碍怎么办
• 抽象的问题转化为具体的问题
• 没见过的问题转化为见过的问题

冒泡排序：高的往后排

• 比较相邻的两个元素，第一个比第二个大，则交换两个
• 对每一对相邻元素做同样工作，这样最大值被固定到最后
• 重头开始新一轮的比较，得到新的最大值，这样得到倒数第二位

• 以此类推

  
  12926249-e6ffd5b328c0c2e1.gif

function swap(array,a,b){
    var temp
    temp = array[a]
    array[a] = array[b]
    array[b] = temp
}
function sort(array){
    var i,j
    for(i = 0;i<array.length;i++){
        //排了第i次
        for(j=0;j<array.length-1-i;j++){
            if(array[j] <= array[j+1]){
            }else{
                swap(array,j,j+1)
            }
        }
    }
    return array
}
console.log(sort([3,5,6,2,5,2,4]))

每次最高的排最后

选择排序：每次选择最小的，最小的往前站

• 在序列中找到最小元素(大)，存放在序列的起始位置
• 未排序的序列中继续找最小元素，然后放序列中的第二行

• 以此类推

  
  12926249-1552111813abc71d.gif

function swap(array,a,b){
    var temp
    temp = array[a]
    array[a] = array[b]
    array[b] = temp
}
function sort(array){
    var i,j,indexMin
    for(i=0;i<array.length;i++){
        indexMin = i
        for(j=i+1;j<array.length;j++){
            //找到最小值，将j的值赋给indexMin
            if(array[j] < array[indexMin]){
                indexMin = j
            }
        }
        swap(array,i,indexMin)
    }
    return array
}
console.log(sort([3,5,6,2,5,2,4]))

插入排序：扑克牌算法

• 起一张牌，第二张牌要是小的话放前面

• 第三张牌比较有序区的元素，比较后插入到合适的位置，以此类推

  
  12926249-e63cb677a8f42840.gif

归并排序：领导算法 最底层

快速排序：自私算法：前面比我矮。后面比我高

• 1.取出一个元素为基准
• 2.对数列进行以此比较排序，比基准小的放基准前面，大的放基准后面，此操作结束后，基准位于数列中间

• 3.然后分别对基准两边的区，进行以上操作

  
  12926249-d6cb24f0bc157677.gif

var times=0;
var quickSort=function(arr){ 
    //如果数组长度小于等于1无需判断直接返回即可
    if(arr.length<=1){
        return arr;
    }
    var midIndex=Math.floor(arr.length/2);//取基准点
    var midIndexVal=arr.splice(midIndex,1);//取基准点的值,splice(index,1)函数可以返回数组中被删除的那个数arr[index+1]
    var left=[];//存放比基准点小的数组
    var right=[];//存放比基准点大的数组
    //遍历数组，进行判断分配
    for(var i=0;i<arr.length;i++){
        if(arr[i]<midIndexVal){
            left.push(arr[i]);//比基准点小的放在左边数组
        }
        else{
            right.push(arr[i]);//比基准点大的放在右边数组
        }
        console.log("第"+(++times)+"次排序后："+arr);
    }
    //递归执行以上操作,对左右两个数组进行操作，直到数组长度为<=1；
    return quickSort(left).concat(midIndexVal,quickSort(right));//连接数组
};
console.log(quickSort(arr));

随机快速排序法:比快排效率高一些

桶排序

桶排序的工作原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶分别排序
缺点：占内存

基数排序：

先从低位排序，然后收集，再慢慢高位排序，以此类推

12926249-6adaf9386e1e816d.gif