2016年11月13日 星期日

Javascript 之排序演算法 ( Sort Algorithm )

氣泡排序法 ( Bubble Sort )

從第一筆開始,每相鄰兩筆比較,大小交換位置,大的在右,小的在左,以此類退,直到最後一筆。 不斷的循環直到都沒有交換為止。

時間複雜度 ( Time Complexity )

  • Best Case:Ο(n)
  • Worst Case:Ο(n2)
  • Average Case:Ο(n2)
(8)~(5)~(7)~(2)~(3)~(9)~(4)~(6) - 8、5(處理值)
(5)~(8)~(7)~(2)~(3)~(9)~(4)~(6) - 8、7(處理值)
(5)~(7)~(8)~(2)~(3)~(9)~(4)~(6) - 8、2(處理值)
(5)~(7)~(2)~(8)~(3)~(9)~(4)~(6) - 8、3(處理值)
(5)~(7)~(2)~(3)~(8)~(9)~(4)~(6) - 8、9(處理值)
(5)~(7)~(2)~(3)~(8)~(9)~(4)~(6) - 9、4(處理值)
(5)~(7)~(2)~(3)~(8)~(4)~(9)~(6) - 9、6(處理值)
(5)~(7)~(2)~(3)~(8)~(4)~(6)~(9)
(5)~(7)~(2)~(3)~(8)~(4)~(6)~(9) - 5、7(處理值)
(5)~(7)~(2)~(3)~(8)~(4)~(6)~(9) - 7、2(處理值)
(5)~(2)~(7)~(3)~(8)~(4)~(6)~(9) - 7、3(處理值)
(5)~(2)~(3)~(7)~(8)~(4)~(6)~(9) - 7、8(處理值)
(5)~(2)~(3)~(7)~(8)~(4)~(6)~(9) - 8、4(處理值)
(5)~(2)~(3)~(7)~(4)~(8)~(6)~(9) - 8、6(處理值)
(5)~(2)~(3)~(7)~(4)~(6)~(8)~(9)
(5)~(2)~(3)~(7)~(4)~(6)~(8)~(9) - 5、2(處理值)
(2)~(5)~(3)~(7)~(4)~(6)~(8)~(9) - 5、3(處理值)
(2)~(3)~(5)~(7)~(4)~(6)~(8)~(9) - 5、7(處理值)
(2)~(3)~(5)~(7)~(4)~(6)~(8)~(9) - 7、4(處理值)
(2)~(3)~(5)~(4)~(7)~(6)~(8)~(9) - 7、6(處理值)
(2)~(3)~(5)~(4)~(6)~(7)~(8)~(9)
(2)~(3)~(5)~(4)~(6)~(7)~(8)~(9) - 2、3(處理值)
(2)~(3)~(5)~(4)~(6)~(7)~(8)~(9) - 3、5(處理值)
(2)~(3)~(5)~(4)~(6)~(7)~(8)~(9) - 5、4(處理值)
(2)~(3)~(4)~(5)~(6)~(7)~(8)~(9) - 5、6(處理值)
(2)~(3)~(4)~(5)~(6)~(7)~(8)~(9)
function swap(arr, i, j) {
    let tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

function bubbleSort(arr) {
    for (let i = 0; i < arr.length; i++) {
        let swap = false;
        for (let j = 0; j < arr.length - i; j++) {
            if (arr[j] > arr[j + 1]) {
                let tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
                swap = true;
            }
        }
        if (!swap) {
            break;
        }
    }
}

swap:檢查是否已經完成排序,如果都沒有執行交換,代表已完成可以提前結束排序。

插入排序法 ( Insertion Sort )

時間複雜度 ( Time Complexity )

  • Best Case:Ο(1)
  • Worst Case:Ο(n2)
  • Average Case:Ο(n2)
(8)~(5)~(7)~(2)~(3)~(9)~(4)~(6) - 8(處理值)
(8)~(5)~(7)~(2)~(3)~(9)~(4)~(6) - 5(處理值)
(5)~(8)~(7)~(2)~(3)~(9)~(4)~(6)
(5)~(8)~(7)~(2)~(3)~(9)~(4)~(6) - 7(處理值)
(5)~(7)~(8)~(2)~(3)~(9)~(4)~(6)
(5)~(7)~(8)~(2)~(3)~(9)~(4)~(6) - 2(處理值)
(5)~(7)~(2)~(8)~(3)~(9)~(4)~(6)
(5)~(2)~(7)~(8)~(3)~(9)~(4)~(6)
(2)~(5)~(7)~(8)~(3)~(9)~(4)~(6)
(2)~(5)~(7)~(8)~(3)~(9)~(4)~(6) - 3(處理值)
(2)~(5)~(7)~(3)~(8)~(9)~(4)~(6)
(2)~(5)~(3)~(7)~(8)~(9)~(4)~(6)
(2)~(3)~(5)~(7)~(8)~(9)~(4)~(6)
(2)~(3)~(5)~(7)~(8)~(9)~(4)~(6) - 4(處理值)
(2)~(3)~(5)~(7)~(8)~(4)~(9)~(6)
(2)~(3)~(5)~(7)~(4)~(8)~(9)~(6)
(2)~(3)~(5)~(4)~(7)~(8)~(9)~(6)
(2)~(3)~(4)~(5)~(7)~(8)~(9)~(6)
(2)~(3)~(4)~(5)~(7)~(8)~(9)~(6) - 6(處理值)
(2)~(3)~(4)~(5)~(7)~(8)~(6)~(9)
(2)~(3)~(4)~(5)~(7)~(6)~(8)~(9)
(2)~(3)~(4)~(5)~(6)~(7)~(8)~(9)
function swap(arr, i, j) {
    let tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

function insertion(arr) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = i; j >= 0; j--) {
            if (arr[j + 1] < arr[j]) {
                swap(arr, j, j + 1)
            } else {
                continue;
            }
        }
    }
}

選擇排序法 ( Selection Sort )

搜尋最小值,與第一值交換位置,再找第二個最小值,與第二個值交換位置,以此類推,直到排序完成。

時間複雜度 ( Time Complexity )

  • Best Case:Ο(n2)
  • Worst Case:Ο(n2)
  • Average Case:Ο(n2)

空間複雜度 ( Space Complexity )

  • θ(1)
(8)~(5)~(7)~(2)~(3)~(9)~(4)~(6) - 2(處理值)
(2)~(5)~(7)~(8)~(3)~(9)~(4)~(6)
(2)~(5)~(7)~(8)~(3)~(9)~(4)~(6) - 3(處理值)
(2)~(3)~(7)~(8)~(5)~(9)~(4)~(6)
(2)~(3)~(7)~(8)~(5)~(9)~(4)~(6) - 4(處理值)
(2)~(3)~(4)~(8)~(5)~(9)~(7)~(6)
(2)~(3)~(4)~(8)~(5)~(9)~(7)~(6) - 5(處理值)
(2)~(3)~(4)~(5)~(8)~(9)~(7)~(6)
(2)~(3)~(4)~(5)~(8)~(9)~(7)~(6) - 6(處理值)
(2)~(3)~(4)~(5)~(6)~(9)~(7)~(8)
(2)~(3)~(4)~(5)~(6)~(9)~(7)~(8) - 7(處理值)
(2)~(3)~(4)~(5)~(6)~(7)~(9)~(8)
(2)~(3)~(4)~(5)~(6)~(7)~(9)~(8) - 8(處理值)
(2)~(3)~(4)~(5)~(6)~(7)~(8)~(9)
function swap(arr, i, j) {
    let tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

function selection(arr) {
    let tmp = [];
    for (let i = 0; i < arr.length; i++) {
        let min = i;
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[min] > arr[j]) {
                min = j;
            }
        }
        if (i != min) {
            swap(arr, min, i);
        }
    }
}

0 意見:

張貼留言