• 什么是算法
  • 輸入：一個(gè)算法必須有零個(gè)或以上輸入量
  • 輸出：一個(gè)算法應(yīng)有一個(gè)或以上輸出量
  • 明確性：算法的描述必須無歧義，實(shí)際運(yùn)行結(jié)果是確定的
  • 有限性：必須在有限個(gè)步驟內(nèi)結(jié)束
  • 有效性：又稱可行性，能夠被執(zhí)行者實(shí)現(xiàn)
• 十種常見排序算法可以分為兩大類：

非線性時(shí)間比較類排序：通過比較來決定元素間的相對(duì)次序，由于其時(shí)間復(fù)雜度不能突破O(nlogn)，因此稱為非線性時(shí)間比較類排序。

線性時(shí)間非比較類排序：不通過比較來決定元素間的相對(duì)次序，它可以突破基于比較排序的時(shí)間下界，以線性時(shí)間運(yùn)行，因此稱為線性時(shí)間非比較類排序。

算法分類.png

• 算法復(fù)雜度

  
  
  算法復(fù)雜度.png

• 遇到思路障礙怎么辦
• 抽象的問題轉(zhuǎn)化為具體的問題
• 沒見過的問題轉(zhuǎn)化為見過的問題

冒泡排序：高的往后排

• 比較相鄰的兩個(gè)元素，第一個(gè)比第二個(gè)大，則交換兩個(gè)
• 對(duì)每一對(duì)相鄰元素做同樣工作，這樣最大值被固定到最后
• 重頭開始新一輪的比較，得到新的最大值，這樣得到倒數(shù)第二位

• 以此類推

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

每次最高的排最后

選擇排序：每次選擇最小的，最小的往前站

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

• 以此類推

  
  
  選擇排序.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]))

插入排序：撲克牌算法

• 起一張牌，第二張牌要是小的話放前面

• 第三張牌比較有序區(qū)的元素，比較后插入到合適的位置，以此類推

  
  
  插入排序.gif

歸并排序：領(lǐng)導(dǎo)算法 最底層

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

• 1.取出一個(gè)元素為基準(zhǔn)
• 2.對(duì)數(shù)列進(jìn)行以此比較排序，比基準(zhǔn)小的放基準(zhǔn)前面，大的放基準(zhǔn)后面，此操作結(jié)束后，基準(zhǔn)位于數(shù)列中間

• 3.然后分別對(duì)基準(zhǔn)兩邊的區(qū)，進(jìn)行以上操作

  
  
  快速排序.gif

var times=0;
var quickSort=function(arr){ 
    //如果數(shù)組長(zhǎng)度小于等于1無需判斷直接返回即可
    if(arr.length<=1){
        return arr;
    }
    var midIndex=Math.floor(arr.length/2);//取基準(zhǔn)點(diǎn)
    var midIndexVal=arr.splice(midIndex,1);//取基準(zhǔn)點(diǎn)的值,splice(index,1)函數(shù)可以返回?cái)?shù)組中被刪除的那個(gè)數(shù)arr[index+1]
    var left=[];//存放比基準(zhǔn)點(diǎn)小的數(shù)組
    var right=[];//存放比基準(zhǔn)點(diǎn)大的數(shù)組
    //遍歷數(shù)組，進(jìn)行判斷分配
    for(var i=0;i<arr.length;i++){
        if(arr[i]<midIndexVal){
            left.push(arr[i]);//比基準(zhǔn)點(diǎn)小的放在左邊數(shù)組
        }
        else{
            right.push(arr[i]);//比基準(zhǔn)點(diǎn)大的放在右邊數(shù)組
        }
        console.log("第"+(++times)+"次排序后："+arr);
    }
    //遞歸執(zhí)行以上操作,對(duì)左右兩個(gè)數(shù)組進(jìn)行操作，直到數(shù)組長(zhǎng)度為<=1；
    return quickSort(left).concat(midIndexVal,quickSort(right));//連接數(shù)組
};
console.log(quickSort(arr));

隨機(jī)快速排序法:比快排效率高一些

桶排序

桶排序的工作原理：假設(shè)輸入數(shù)據(jù)服從均勻分布，將數(shù)據(jù)分到有限數(shù)量的桶里，每個(gè)桶分別排序
缺點(diǎn)：占內(nèi)存

基數(shù)排序：

基數(shù)排序.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;
}