排序算法

一、排序

1. 冒泡排序

// 冒泡排序
    function maoPao(arr) {
        let len = arr.length;
        for (let i = 0; i < len; i++){
            for (let j = 0; j < len - i; j++){
                if (arr[j] > arr[j + 1]) {
                    [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
                }
            }
        }
        return arr;
    }
    arr = [1, 5, 2, 9, 7, 3];
    console.log(maoPao(arr));

• 性能：
  时间复杂度：平均时间复杂度是O(n^2)
  空间复杂度：由于辅助空间为常数，所以空间复杂度是O(1);

2. 快速排序

找到一个基数，将比基数小的值放在基数的左边，将比基数大的值放在基数的右边，之后进行递归那两组已经归类好的数组。

// 快排
function quickSort(arr, left, right) {
    if (left > right) {
        return;
    }
    let i = left;
    let j = right;
    let base = arr[left];

    while (i < j) {
        while (arr[j] >= base && i < j) {
            j--;
        }
        while (arr[i] <= base && i < j) {
            i++;
        }
        if (i < j) {
            [arr[i], arr[j]] = [arr[j], arr[i]];
        }
    }
    [arr[left], arr[i]] = [arr[i], arr[left]];
    quickSort(arr, left, j - 1);
    quickSort(arr, i + 1, right);
    return arr;
}
arr = [1, 5, 2, 9, 7, 3];
console.log(quickSort(arr, 0, arr.length - 1));

• 时间复杂度：平均时间复杂度O(nlogn)，只有在特殊情况下会是O(n^2)
  空间复杂度：O(logn)

3. 归并排序

将数组分割成两个数组，将相邻的两个数组进行排序，然后在每两对进行合并，不断重复，直至排序完。

// 归并排序
    function mergeSort(arr) {
        let len = arr.length;
        if (len < 2) {
            return arr;
        }

        let middle = parseInt(len / 2);
        let left = arr.slice(0, middle);
        let right = arr.slice(middle);

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

    function merge(left, right) {
        let i = 0;
        let j = 0;
        let result = [];
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                result.push(left[i]);
                i++;
            } else {
                result.push(right[j]);
                j++;
            }
        } 
        while (i < left.length) {
            result.push(left[i]);
            i++;
        }
        while (j < right.length) {
            result.push(right[j]);
            j++;
        }
        return result;
    }
    arr = [1, 5, 2, 9, 7, 3];
    console.log(mergeSort(arr));

• 时间复杂度：O(nlogn)
• 空间复杂度：O(n)

4. 选择排序

第一遍，从数组中选出最小的，与第一个元素进行交换；第二遍，从第二个元素开始，找出最小的，与第二个元素进行交换；依次循环，完成排序

// 选择排序
    function selectionSort(arr) {
        let len = arr.length;
        for (let i = 0; i < len; i++){
            let index = i;
            for (let j = i+1; j < len; j++){
                if (arr[index] > arr[j]) {
                    index = j;
                }
            }
            [arr[i], arr[index]] = [arr[index], arr[i]];
        }
        return arr;
    }
    arr = [1, 5, 2, 9, 7, 3];
    console.log(selectionSort(arr));

• 时间复杂度：O(n^2);
• 不稳定；
• 空间复杂度：O(1);

5. 插入排序

将当前元素插入到已经排序好的数组中。

// 插入排序
    function insertSort(arr) {
        for (let i = 0; i < arr.length; i++){
            let temp = arr[i];
            for (let j = 0; j < i; j++){
                if (temp < arr[j] && j === 0) {
                    arr.splice(i, 1);
                    arr.unshift(temp);
                    break;
                } else if (temp >= arr[j] && temp < arr[j + 1] && j < i - 1) {
                    arr.splice(i, 1);
                    arr.splice(j + 1, 0, temp);
                    break;
                }
            }
        }
        return arr;
    }
    arr = [1, 5,7, 2, 9, 7, 3];
    console.log(insertSort(arr));

• 时间复杂度：O(n^2);
• 空间复杂度：O(1);

6. 堆排序

//堆排序
    function heapSort(arr) {
        let len = arr.length;
        // 初始化大顶堆
        for (let i = Math.floor(len / 2 - 1); i >= 0; i--) {
            shiftDown(arr, i, len);
        }
        // 堆排序
        for (let i = Math.floor(len - 1); i > 0; i--) {
            [arr[0], arr[i]] = [arr[i], arr[0]];
            shiftDown(arr, 0, i);
        }
        return arr;
    }

    function shiftDown(arr, i, length) {
        let temp = arr[i];//当前父节点
        for (let j = 2 * i + 1; j < length; j = 2 * j + 1) {
            temp = arr[i];
            if (j + 1 < length && arr[j] < arr[j + 1]) {
                j++;
            }
            if (temp < arr[j]) {
                [arr[i], arr[j]] = [arr[j], arr[i]];
                i = j;
            } else {
                break;
            }
        }
    }
    arr = [1, 5, 7, 2, 9, 7, 3];
    console.log(heapSort(arr));