算法

高德納在《計算機程序設計藝術(shù)》里對算法歸納為以下幾點：

1. 輸入: 一個算法必須有零或以上的輸入量
2. 輸出: 一個算法應有一個或以上的輸出量
3. 明確性: 算法的描述必須無歧義,實際運行結(jié)果是確定的
4. 有限性: 必須在有限個步驟內(nèi)結(jié)束
5. 有效性: 又稱可行性,能夠被執(zhí)行者實現(xiàn)

如果想詳細研究算法推薦《數(shù)據(jù)結(jié)構(gòu)與算法分析》

數(shù)據(jù)結(jié)構(gòu)與算法分析

定義問題

數(shù)組array含有N個正整數(shù)
輸入量為array
請將array中的數(shù)字從小到大排列
輸出量為排好序的數(shù)組

代碼例子

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

當你遇到思路障礙怎么辦?

• 將抽象的問題轉(zhuǎn)化為具體的問題
• 將沒見過的問題轉(zhuǎn)化為見過的問題

排序算法

所有算法都可在此查看演示

冒泡排序(BUBBLE)

重復地比較要排序的數(shù)列丰榴，一次比較兩個元素八秃，如果他們的順序錯誤就把他們交換過來捻脖。比較數(shù)列的工作是重復地進行直到?jīng)]有再需要交換密任，也就是說該數(shù)列已經(jīng)排序完成之斯。每比較一整輪,最大的都會出現(xiàn)在最后故名---冒泡排序

流程如下:

1. 我們拿到一個數(shù)組

   
   
   數(shù)組

2. 開始從前兩個開始比較,發(fā)現(xiàn)44>3,所以不用交換

   
   
   比較

3. 接著往后比較,發(fā)現(xiàn)38<44,所以交換他們兩個的位置

   
   
   比較
4. 以此類推直到第一輪結(jié)束,我們得到了最大的那一個----50(冒的第一個泡)
   
   第一輪結(jié)束
5. 接著下一輪,又從頭開始兩個兩個地比較,重復第一輪,我們就得到了第二個最大的------48
   
   第二輪結(jié)束

6. 如此進行多輪比較我們會得到一個從小到大的數(shù)組

   
   
   從小到大
7. 代碼實現(xiàn)：

function bubbleSort(array) {
    for (let i = 0; i < array.length - 1; i++) {
        for (let j = 0; j < array.length - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                let temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}

2. 選擇排序(SELECT)

每一次從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個元素宏怔，存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完昭殉。
流程如下:

1. 拿到一個數(shù)組

   
   
   數(shù)組

2. 我們要選出這個數(shù)組中最小的元素然后把它和第一個數(shù)交換(放到最前面),所以我們先認為3為最小,然后和后面的數(shù)依次進行比較.

   
   
   和最小值比較

3. 當比到2的時候,我們發(fā)現(xiàn)3>2,所以我們就認為2為最小值,后面的數(shù)應該都和2進行比較.

   
   
   改變最小值的元素

4. 當比較完所有的元素,確定2為最小值的時候,把最小值也就是2與第一個元素的位置互換.

   
   
   互換位置

5. 然后從第二個元素開始新一輪的比較,過程和第一輪一樣.把44看做最小值和后面的元素進行比較.

   
   
   第二輪

6. 經(jīng)過多輪比較得到從小到大的數(shù)組.

   
   
   從小到大
7. 代碼實現(xiàn)

function selectSort(arr) {
    var minIndex, temp;
    for (let i = 0; i < arr.length - 1; i++) {
        minIndex = i; // 先把第一個看做最小值
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}

3, 插入排序(INSERT)

將一個數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中，從而得到一個新的、個數(shù)加一的有序數(shù)據(jù)匆绣，算法適用于少量數(shù)據(jù)的排序冻押。是穩(wěn)定的排序方法苗踪。
流程如下:

1. 拿到一個數(shù)組

   
   
   數(shù)組

2. 把第一個元素看做一個新數(shù)組,然后把第二個元素依次和新數(shù)組的元素進行比較(雖然只有一個...),然后插入到適當?shù)奈恢?

   
   
   與新數(shù)組的元素進行比較
   
   
   插入到適當?shù)奈恢?/div>

3. 然后以此類推,把前兩個元素看做是一個新數(shù)組,然后把第三個元素依次與新數(shù)組進行比較,然后插入到適當?shù)奈恢?

   
   
   比較
   
   
   插入適當?shù)奈恢?/div>

4. 把剩下的元素依次插入,最后得到從小到大排列的數(shù)組.

   
   
   從小到大
5. 代碼實現(xiàn)

function insertionSort(array) {

    for (let i = 1; i < array.length; i++) {
        let key = array[i];
        let j = i - 1;
        while (j >= 0 && array[j] > key) {
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = key;
    }
    return array;
}

4. 歸并排序(MERGE)

將已有序的子序列合并济瓢，得到完全有序的序列；即先使每個子序列有序棵帽，再使子序列段間有序熄求。
流程如下:

1. 拿到一個數(shù)組

   
   
   數(shù)組

2. 我們把數(shù)組平均分成左右兩部分,得到兩個新數(shù)組,然后再把每個數(shù)組平均分成兩部分,一直分到每個數(shù)組只有兩個元素,然后比較第一組

   
   
   比較第一組

3. 因為3<44所以位置不變?nèi)缓蟊容^第二組,因為38>5所以調(diào)換位置.

   
   
   圖片.png

4. 重點來了,這個時候先不著急比較第三組而是把排好序的一二兩組放在一起排序.

   
   
   圖片.png

5. 之后就是比較第三組和第四組,然后同樣把他們放在一起排好序.

   
   
   圖片.png

6. 然后并不是比較第五組和第六組,而是把第一組和第二組產(chǎn)生的新數(shù)組和,第三組和第四組產(chǎn)生的新數(shù)組放在一起排序成為新數(shù)組.

   
   
   圖片.png

7. 同樣把剩下的按以上步驟重來一遍.我們得到兩個排好序的數(shù)組.然后給這兩個數(shù)組排序就完成了.

   
   
   圖片.png
   
   

   排序后:

   
   
   圖片.png
8. 代碼實現(xiàn)

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 = [];

    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());

    return result;
}

5. 快速排序

每個元素找到自己對應的位置(前面的都比我小,后面的都比我大)
流程如下:

1. 拿到一個數(shù)組

   
   
   數(shù)組

2. 拿第一個元素和后面的元素進行比較,找出所有比第一個元素小的元素,放在第一個元素的右邊然后把第一個元素與這些比他小的元素的最后一個互換.

   
   
   只有2比3小
   
   
   互換

3. 前兩個元素的位置已經(jīng)沒錯了,然后以第三個元素為標準,和后面的元素進行比較.

   
   
   比較之后

4. 把比他小的元素放在他的右邊(綠色),然后讓它和綠色的最后一個交換位置.

   
   
   交換位置

5. 然后從左邊沒有確定位置的元素(非橙色)開始以上步驟----也就是19

   
   
   從19開始

6. 一直到所有元素的位置都正確.

   
   
   都有了正確的位置
7. 代碼實現(xiàn)

function quickSort(array) {
    function quick(array, left, right) {
        let index;
        if (array.length > 1) {
            index = partition(array, left, right);
            if (left < index - 1) {
                quick(array, left, index - 1);
            }
            if (index < right) {
                quick(array, index, right);
            }
        }
        return array;
    }
    function partition(array, left, right) {
        const pivot = array[Math.floor((right + left) / 2)];
        let i = left;
        let j = right;
    
        while (i <= j) {
            while (array[i] < pivot) {
                i++;
            }
            while (array[j] > pivot) {
                j--;
            }
            if (i <= j) {
                [array[i], array[j]] = [array[j], array[i]]
                i++;
                j--;
            }
        }
        return i;
    }
    quick(array, 0, array.length - 1);
};

6. 隨機快速排序

顧名思義,就是在快速排序的基礎(chǔ)上,加入隨機的機制.
在快速排序的時候我們是從左到右來選取比較對象,在隨機快速排序中我們是隨機來選取對象.
流程如下:

1. 拿到一個數(shù)組

   
   
   數(shù)組

2. 隨機選擇一個元素.

   
   
   隨機選擇到了44

3. 并且把比他小的放在他的右邊

   
   
   把比他小的先放在他的右邊

4. 然后把他和比他小的最右邊的元素交換位置

   
   
   交換位置

5. 然后在隨機選一個元素,重復步驟,知道所有元素都是在正確的位置上.

   
   
   所有元素都在正確的位置上
6. 代碼實現(xiàn)

function quickSort(array) {
    function quick(array, left, right) {
        let index;
        if (array.length > 1) {
            index = partition(array, left, right);
            if (left < index - 1) {
                quick(array, left, index - 1);
            }
            if (index < right) {
                quick(array, index, right);
            }
        }
        return array;
    }
    function partition(array, left, right) {
        const pivot = array[Math.floor(Math.random()*array.length)];
        let i = left;
        let j = right;
    
        while (i <= j) {
            while (array[i] < pivot) {
                i++;
            }
            while (array[j] > pivot) {
                j--;
            }
            if (i <= j) {
                [array[i], array[j]] = [array[j], array[i]]
                i++;
                j--;
            }
        }
        return i;
    }
    quick(array, 0, array.length - 1);
};