js常见排序算法实现

1.冒泡排序

原理：对数组进行遍历，根据相邻两个元素大小进行交换，每一次遍历都将最小值推至最前方，然后对剩下的值再次进行比较

时间复杂度：O(n^2)

空间复杂度：O(1)

稳定性：稳定

// 冒泡排序
function bubbleSort(arr) {
    let len = arr.length - 1, tmp
    for (let i = 0; i < len; i++) {
        for (let j = 0; j < len - i; j++) {
            if (arr[j] > arr[j + 1]) {
                tmp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = tmp
            }
        }
    }
    return arr
}

2.快速排序

原理：从数组中取一个基准值，将剩下的值与基准值比较，小于的放到左边，大于的放到右边，并对左右两边进行快速排序，重复直到左右两边只剩一个元素，最后合并

平均时间复杂度O(nlogn)

最坏时间复杂度：O(n^2)

空间复杂度：O(nlogn)

稳定性：不稳定

// 快速排序
function quickSort(arr) {
    let len = arr.length
    if (len < 2) {
        return arr;
    }
    let index = Math.floor(len / 2);
    let pindex = arr.splice(index, 1)[0]; // 去除基准值
    let left = [], right = [];
    arr.forEach(item => {
        if (item > pindex) {
            right.push(item);
        } else {
            left.push(item);
        }
    })
    return quickSort(left).concat([pindex], quickSort(right))
}

3.插入排序

原理：将数组分成两个，一个是已排序，一个是待排序，将待排序中的元素与已排序的元素进行比较并插入到适当位置

最好时间复杂度：O(n)，当数组已经由小到大排序好

最坏时间复杂度：O(n^2)，当数组是由大到小排序，与冒泡排序相同

空间复杂度：O(1)

稳定性：稳定

// 插入排序
function insertSort(arr) {
    let len = arr.length;
    let prev, cur;
    for (let i = 1; i < len; i++) {
        prev = i - 1;
        cur = arr[i];
        while(prev >= 0 && arr[prev] > cur) {
            arr[prev + 1] = arr[prev];
            prev--;
        }
        arr[prev + 1] = cur;
    }
    return arr;
}

4.希尔排序

原理：将整个数组通过设置步长分为一个个分块，对每个分块进行序列化，最后进行一次插入排序

时间复杂度：O(nlogn)~O(n²)，一般为O(n^1.5)，数组有序程度越高，排序越快

空间复杂度：O(1)

稳定性：不稳定

// 希尔排序
function shellSort(arr) {
    let len = arr.length;
    let tmp;
    let gap = Math.floor(len / 2);
    while(gap > 0) {
        for (let i = gap; i <len; i++) {
            for (let j = i; j >= gap && arr[j] < arr[j - gap]; j -= gap) {
                tmp = arr[j];
                arr[j] = arr[j - gap];
                arr[j - gap] = tmp;
            }
        }
        gap = Math.floor(gap / 2);
    }
    return arr;
}

5.选择排序

原理：从数组第一个元素开始，与后面所有元素进行比较，如果有比其小的值，则交换两者位置

时间复杂度：O(n^2)

空间复杂度：O(1)

稳定性：不稳定

// 选择排序
function selectSort(arr) {
    let len = arr.length;
    let index, tmp;
    for (let i = 0; i < len; i++) {
        index = i;
        for (let j = i + 1; j < len; j++) {
            if (arr[index] > arr[j]) {
                index = j;
            }
        }
        tmp = arr[index];
        arr[index] = arr[i]
        arr[i] = tmp
    }
    return arr
}

6.归并排序

原理：将数组拆分成短序列进行排序，然后把各个有序的短序列合并成一个

时间复杂度：O(nlogn)

空间复杂度：O(1)

稳定性：稳定

// 归并排序
function mergeSort(arr) {
    if (arr.length < 2) {
        return arr;
    }
    let mid = Math.floor(arr.length / 2);
    let left = arr.slice(0, mid);
    let right = arr.slice(mid);

    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
    console.log(right);
    let arr = [];
    while(left.length && right.length) {
        if (left[0] <= right[0]) {
            arr.push(left.shift());
        } else {
            arr.push(right.shift());
        }
    }

    while(left.length) {
        arr.push(left.shift());
    }
    while(right.length) {
        arr.push(right.shift());
    }
    return arr
}