算法排序

• 什么是算法
  • 输入：一个算法必须有零个或以上输入量
  • 输出：一个算法应有一个或以上输出量
  • 明确性：算法的描述必须无歧义，实际运行结果是确定的
  • 有限性：必须在有限个步骤内结束
  • 有效性：又称可行性，能够被执行者实现
• 十种常见排序算法可以分为两大类：

非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。

线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。

算法分类.png

• 算法复杂度

  
  算法复杂度.png

• 遇到思路障碍怎么办
• 抽象的问题转化为具体的问题
• 没见过的问题转化为见过的问题

冒泡排序：高的往后排

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

• 以此类推

  
  冒泡排序.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]))

每次最高的排最后

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

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

• 以此类推

  
  选择排序.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]))

插入排序：扑克牌算法

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

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

  
  插入排序.gif

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

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

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

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

  
  快速排序.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));

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

桶排序

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

基数排序：

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

// LSD Radix Sort 
var counter = [];
function radixSort(arr, maxDigit) {
    var mod = 10;
    var dev = 1;
    for (var i = 0; i < maxDigit; i++ , dev *= 10, mod *= 10) {
        for (var j = 0; j < arr.length; j++) {
            var bucket = parseInt((arr[j] % mod) / dev); 
            if (counter[bucket] == null) { 
                counter[bucket] = []; 
            }
             counter[bucket].push(arr[j]);
        } 
        var pos = 0; 
        for (var j = 0; j < counter.length; j++) { 
            var value = null; 
            if (counter[j] != null) { 
                while ((value = counter[j].shift()) != null) { 
                    arr[pos++] = value; 
                } 
            } 
        }
    } 
    return arr;
}