JS实现归并排序和快速排序

归并排序（稳定算法）

思路

先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起。

复杂度

时间 O(nlogn)
空间 O(n)

实现

function mergeSort(arr) {
    if (arr.length === 1) return arr;
    const midIdx = Math.floor(arr.length / 2);
    return merge(mergeSort(arr.slice(0, midIdx)), mergeSort(arr.slice(midIdx)))
}

function merge(leftArr, rightArr) {
    let temp = [];
    while (leftArr.length > 0 && rightArr.length > 0) {
        if (leftArr[0] < rightArr[0]) {
            temp.push(leftArr.shift());
        } else {
            temp.push(rightArr.shift());
        }
    }
    return temp.concat(leftArr).concat(rightArr);
}
// var s = [32, 12, 56, 78, 76, 45, 36]
// var arr = mergeSort(s);
// console.log(arr);

快速排序（非稳定算法）

思路

如果要排序数组中下标从 p 到 r 之间的一组数据，我们选择 p 到 r 之间的任意一个数据作为 pivot（分区点）。我们遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间。

复杂度

时间 O(nlogn) 空间 O(1)

实现

function quickSort(arr) {
    quickSort_c(arr, 0, arr.length - 1);
}

function quickSort_c(arr, p, r) {
    if (p >= r) return;
    let q = partition(arr, p, r);
    quickSort_c(arr, p, q - 1);
    quickSort_c(arr, q + 1, r);
}

function partition(arr, p, r) {
    let i = j = p;
    while (j < r) {
        if (arr[j] < arr[r]) {
            swap(arr, j, i);
            i++;
        }
        j++;
    }
    swap(arr, i, r)
    return i
}

function swap(arr, i, r) {
    let temp = arr[i];
    arr[i] = arr[r];
    arr[r] = temp;
}

// var s = [32, 12, 56, 78, 76, 45, 36]
// quickSort(s);
// console.log(s);