排序法

bubble sort(氣泡排序法)

function bubbleSort(arr) {


    for(var i = 0; i < arr.length; i++) {
        if(arr[i] > arr[i + 1]) {
            var tmp = arr[i + 1];
            arr[i + 1] = arr[i];
            arr[i] = tmp;
        }
    }

    var isOk = true;
    for(var j = 0; j < arr.length; j++) {
        if(arr[j] > arr[j + 1]) {
            isOk = false;
            break;
        }
    }

    return isOk ? arr : bubbleSort(arr);
}

console.log(bubbleSort([8, 2, -50, 5, 39, 7, 4, -1]));

insert sort(插入排序法)

function insertSort(arr) {
    var list = [];
    for(var i = 0; i < arr.length; i++) {
        var tmp = i;
        var value = arr[i];
        for(var j = 0; j < i; j++) {
            value = arr[i];
            if(list[j] < arr[i]) {
                tmp = j + 1;
            } else {
                tmp = j;
                break;
            }
        }

        list.splice(tmp, 0, value);
    }
    return list;
}

console.log(insertSort([8, 2, -50, 5, 39, 7, 4, -1]))

merge sort(合併排序法)

function mergeSort(arr) {
    if(arr.length === 1) return arr;

    function split(array) {
        if(array.length === 1) return array;

        var middle = Math.floor(array.length / 2);
        var left = array.slice(0, middle);
        var right = array.slice(middle);

        return merge(split(left), split(right));

    }


    function merge(left, right) {
        var list = [];
        var leftIndex = 0;
        var rightIndex = 0;

        while(leftIndex < left.length && rightIndex < right.length) {

            if(left[leftIndex] < right[rightIndex]) {
                list.push(left[leftIndex]);
                leftIndex++;
            } else {
                list.push(right[rightIndex]);
                rightIndex++;
            }
        }

        return list.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
    }

    return split(arr);
}

console.log(mergeSort([8, 2, 5, 200, -50, 1, 4, 3, -1]))

quick sort(快速排序法)

function quickSort(arr) {
    if(arr.length === 1) return arr;
    if(arr.length === 0) return [];

    var middleIndex = Math.floor(arr.length / 2);
    var left = [];
    var right = [];
    var pivot = arr.splice(middleIndex, 1)[0];

    for(var i = 0; i < arr.length; i++) {
        if(arr[i] > pivot) {
            right.push(arr[i])
        } else {
            left.push(arr[i])
        }
    }
    console.log(left, right)

    return quickSort(left).concat([pivot]).concat(quickSort(right));
}

console.log(quickSort([8, 2, 5, 200, -50, 1, 4, 3, -1]))

select sort (選擇排序法)

function selectionSort(arr) {
    for(var i = 0; i < arr.length; i++) {
        var temp = arr[i + 1];
        var index = i + 1;

        for (var j = i + 1; j < arr.length; j++) {
            if (temp > arr[j]) {
                temp = arr[j];
                index = j;
            }
        }

        if(temp < arr[i]) {
            arr[index] = arr[i];
            arr[i] = temp;
        }
    }
    
    return arr;
}

console.log(selectionSort([-1, 46, 16, 22, -50,12, 77, 29, 33]))