排序算法 - 掘金

学习5种排序算法：

1：快速排序
2：归并排序
3：堆排序
4：冒泡排序
5：选择排序

总结

算法	时间复杂度	空间复杂度	稳定	步骤	应用	原地
快速排序	O(nlogn)/最坏 O(n2)	开辟新数组法O(n)/原地 O(logn)	不稳定	分治法，选取基数，将数组分成两部分，递归进行此操作		in-place/out-place
归并排序	O(nlogn)	O(n)	稳定	分治法，先将数组分割，然后排序，进而集成在一起	速度仅次于快速排序，一般用于总体无序，但是各子项相对有序的数列	out-place
选择排序	O(n2)	O(1)	不稳定	每次遍历找到最小值，放入左侧，依次对未排序的部分重复此操作	不占用额外空间，对空间复杂度要求较高，并且数据规模不大时候可以使用	in-place
冒泡排序	O(n2)	O(1)	稳定	比较相邻元素，如果第一个比第二个大，就交换位置，一直到最后，第二遍重复此操作(除了最后一个)	对空间复杂度要求较高，并且数据规模不大时候，需要稳定排序可以使用	in-place
堆排序	建堆O（n)，总体O(nlog n)	O(1)	不稳定	接住数据结构堆，堆是一个近似完全二叉树的结构，堆具有子节点均比父节点大/小的性质,1:建立大顶堆。2：拿出堆顶元素，将堆末尾元素拿到堆顶3：调整堆，4：重复2，3步	时间复杂度同快速排序、归并排序，特长是使用很少空间，适合相对有序的序列排序	in-place

上面 table 居然还需要滚动。。。给个图吧，方便点

1.归并排序

// 排序 并 合并
function merge (leftArr, rightArr) {
    let result = [];
    while (leftArr.length > 0 && rightArr.length > 0) {
        if(leftArr[0]<=rightArr[0]){
            result.push(leftArr.shift());
        } else {
            result.push(rightArr.shift());
        }
    }
    if(leftArr[0] || rightArr[0]) {
        result.push(leftArr[0] || rightArr[0]);
    }
    return result;
}
// 分割
function mergeSort(arr) {
    // 边界判断
    if (arr.length < 2) {
        return arr;
    }
    // 进行分割，将数组从中间分割成两部分
    const middleIndex = Math.floor(arr.length / 2);
    let left = arr.slice(0, middleIndex);
    let right = arr.slice(middleIndex);
    return merge(mergeSort(left), mergeSort(right));
}

mergeSort([32,12,56,78,76,45,36]);

2.选择排序

// 选择排序
function selectSort(arr){
    for(let j=0; j<arr.length; j++){
        let max = arr[j];
        let maxIndex = j;
        for (let i = j; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
                maxIndex = i;
            }
        }
        const temp = arr[j];
        arr[j] = arr[maxIndex];
        arr[maxIndex] = temp;
    }
    return arr;
}
selectSort([32,12,56,78,76,45,36, 45]);

3.冒泡排序

function bubbleSort(arr) {
    for (let i = arr.length - 1; i >= 0; i--) {
        for (let j = 0; j < i + 1; j++) {
            if (arr[j] > arr[j + 1]) {
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    return arr;
}
bubbleSort([32,12,56,78,76,45,36, 45]);

4.快速排序

in-place

要点：最后一个元素作为 pivot，需要记下分割的 storeIndex，并初始化为-1

// 快速排序  in-place法
function quickSortInPlace(arr, left=0, right= arr.length-1){
    if(left < right){
        let storeIndex = left - 1
        for(let i=left; i<=right; i++){
            // 最后一个元素作为 pivot
            if(arr[i]<=  arr[right]){
                storeIndex++
                let temp = arr[storeIndex]
                arr[storeIndex] = arr[i]
                arr[i] = temp
            }
        }
        quickSortInPlace(arr, left, storeIndex-1)
        quickSortInPlace(arr, storeIndex+1, right)
    }
    return arr
}
let test = [5,6,9,1,4,9,67,4,0];
quickSortInPlace(test)

开辟新数组法

// 快速排序  开辟新数组法
function quickSort(arr) {
    if (arr.length < 2) {
        return arr;
    }
    const pivotIndex = Math.floor(arr.length / 2);
    const pivot = arr.splice(pivotIndex, 1)[0];
    let left = [];
    let right = [];
    arr.forEach(item => {
        if (item < pivot) {
            left.push(item);
        } else {
            right.push(item);
        }
    });
    return quickSort(left).concat(pivot, quickSort(right));
}
let test = [5,6,9,1,4,9,67,4,0];
quickSort(test)

堆排序

利用堆这种数据结构来实现的一种排序算法；堆是一种近似完全二叉树的数据结构，并且具有子节点均大于(或者小于)父节点的性质

堆排序的步骤

1.建立大顶堆
2.堆顶元素放直最后，堆未元素放置堆顶
3.调整堆
4.重复2.3步骤

function heapSort(arr) {
  function sort() {
        // 构建大顶堆
        for (let i = Math.floor(arr.length / 2) - 1; i >= 0; i--) {
            heapify(i, arr.length - 1);
        }
        // 将堆顶元素放直最后，然后重新调整堆
        for (let j = arr.length - 1; j >= 0; j--) {
            // 将堆顶元素放直最后
            swap(0, j);
            // 调整堆，从第一个，调整到最后的 j
            heapify(0, j);
        }
        return arr;
    }
    function swap(i, j) {
        let tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    function heapify(start, end) {
        let dad = start;
        let leftSon = dad * 2 + 1;
        let rightSon = dad * 2 + 2;
        // 记录最大孩子的 index
        let maxSon = leftSon;
        // 没有子节点，无需调整
        if (leftSon >= end) {
            return;
        }
        // 找到最大孩子
        if (rightSon < end && arr[maxSon] < arr[rightSon]) {
            maxSon = rightSon;
        }
        // 最大孩子与 dad 比大小
        if (arr[maxSon] > arr[dad]) { // 如果孩子大，需要换位置
            swap(maxSon, dad);
            heapify(maxSon, end);
        }
    }
    sort();
}

let a = [3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6];
heapSort(a);