冒泡排序

function BubbleSort(arr) {
    var i = j = 0,
        total = arr.length;
    for (i; i < total; i++) {
        var flag = false;
        for (j; j < total; j++) {
            if (arr[j] > a[j + 1]) {
                var temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                flag = true;
            }
        }
        if (!flag) {
            return arr;
        }
    }
    return arr;
}

选择排序

function SelectSort(arr) {
    var i = 0,
        total = arr.length;

    for (i; i < total; i++) {
        var minIndex = i,
            minValue = arr[i];
        for (var j = i + 1; j < total; j++) {
            if (minValue > a[j]) {
                minIndex = j;
                minValue = arr[j];
            }
        }
        var temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}

插入排序

function insertSort(arr) {
    var i,
        prevIndex,
        current,
        len = arr.length
    for (i = 1; i < len; i++) {
        prevIndex = i - 1;
        current = arr[i];
        while (prevIndex >= 0 && arr[prevIndex] > current) {
            arr[prevIndex + 1] = arr[prevIndex];
            prevIndex--;
        }
        arr[prevIndex + 1] = current;
    }
    return arr;
}

归并排序

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

    var mid = Math.floor(a.length / 2),
        left = arr.slice(0, mid),
        right = arr.slice(mid);

    return merge(MergeSort(left), MergeSort(right))
}

function merge(left, right) {
    var arr = [];

    while(left.length > 0 && right.length > 0) {
        if (left[0] > right[0]) {
            arr.push(right.shift());
        } else {
            arr.push(left.shift());
        }

    } 
    return arr.concat(left, right);
}

快排

// 第一个版本
function quickSort(arr, left, right) {
    var partitionIndex,
        left = left ? left : 0,
        right = right ? right : arr.length - 1;

    if (left < right) {
        partitionIndex = partition(arr, left, right);
        quickSort(arr, left, partitionIndex);
        quickSort(arr, partitionIndex, right);
    }

    return arr;
}

function partition(arr, left, right) {
    var pivot = left,
        index = pivot + 1;

    for (var i = index; i < right; i++) {
        if (arr[i] < arr[pivot]) {
            swap(arr, i, index);
            index++;
        }
    } 
    swap(arr, pivot, index - 1);
    return index - 1;
}

function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = arr[i];
}
// 第二个版本
function quickSort(arr) {
    return sort(arr, 0, arr.length - 1);
    function swap(arr, i, k) {
        var temp = arr[i];
        arr[i] = arr[k];
        arr[k] = temp;
    }
    function sort(arr, start, end) {
        sort(arr, 0, arr.length - 1);
        return arr;
        function swap(arr, i, k) {
            var temp = arr[i];
            arr[i] = arr[k];
            arr[k] = temp;
        }
        function sort(arr, start, end) {
            if (start >= end) return;
            var pivot = arr[start],
                i = start + 1,
                k = end;
            while (true) {
                while (arr[i] < pivot) {
                    i++;
                }
                while (arr[k] > pivot) {
                    k--;
                }
                if (i >= k) {
                    break;
                }
                swap(arr, i, k);
            }
            swap(arr, start, k);
            sort(arr, start, Math.max(0, k - 1));
            sort(arr, Math.min(end, k + 1), end);
        }
    }
}

时间复杂度：

最好的情况是：nlogn,parttionIndex每次取中间值

最坏情况是:n^2,parttionIndex每次取n-1或1

空间复杂度：最好是logn，最坏是n

参考地址：https://blog.csdn.net/owen1190/article/details/76215932