题解 | #数组排序#

数组排序

https://www.nowcoder.com/practice/18ea36ef9b0c470e9db7681eced6e8df

<!DOCTYPE html>

<html lang="en">
<head>
    <meta charset="UTF-8">
</head>
<body>
<button class='up'>销量升序</button>
<button class='down'>销量降序</button>
<ul></ul>


<script>
    function render(cups) {
        const ulDOM = document.querySelector('ul');
        let content = '';
        cups.forEach(item => {
            content += `<li>${item.name}</li>`;
        })
        ulDOM.innerHTML = content;
    }
    const cups = [
        { type: 1, price: 100, color: 'black', sales: 3000, name: '牛客logo马克杯' },
        { type: 2, price: 40, color: 'blue', sales: 1000, name: '无盖星空杯' },
        { type: 4, price: 60, color: 'green', sales: 200, name: '老式茶杯' },
        { type: 3, price: 50, color: 'green', sales: 600, name: '欧式印花杯' }
    ]
    const ul = document.querySelector('ul');
    const upbtn = document.querySelector('.up');
    const downbtn = document.querySelector('.down');
    // 补全代码
    // 初始化
    render(cups)

    // 升序排序
    upbtn.onclick = function() {
        heapSort(cups, 'asc', (a, b) => a.sales - b.sales);
        // cups.sort((a, b) => a.sales - b.sales);
        render(cups);
    }

    // 降序排序
    downbtn.onclick = function() {
        heapSort(cups, 'desc', (a, b) => b.sales - a.sales);
        // cups.sort((a, b) => b.sales - a.sales);
        render(cups);
    }

    // 堆排序
    function heapSort(arr, way= 'asc', compartor = (a, b) => a - b) {
        const compartorFn = (i, j) => compartor(arr[i], arr[j]);
        const N = arr.length;
        for(let i = Math.floor(N / 2) - 1; i >= 0; i--) {
            if(way === 'asc') {
                adjustMaxHeap(arr, i, N, compartorFn);
            } else if(way === 'desc') {
                adjustMinHeap(arr, i, N, compartorFn);
            }
        }
        for(let i = 1; i < N; i++) {
            swap(arr, 0, N - i);
            if(way === 'asc') {
                adjustMaxHeap(arr, 0, N - i, compartorFn);
            } else if(way === 'desc') {
                adjustMinHeap(arr, 0, N - i, compartorFn);
            }
        }
    }

    // 调整小根堆
    function adjustMinHeap(arr, i, N, compartorFn) {
        const left = 2 * i + 1;
        const right = 2 * i + 2;
        if(left >= N) return;
        let lower = left;
        if(right < N && compartorFn(right, left) > 0) {
            lower = right;
        }
        if(compartorFn(lower, i) < 0) return;
        swap(arr, lower, i);
        adjustMinHeap(arr, lower, N, compartorFn);
    }

    // 调整大根堆
    function adjustMaxHeap(arr, i, N, compartorFn) {
        const left = 2 * i + 1;
        const right = 2 * i + 2;
        if(left >= N) return;
        let bigger = left;
        if(right < N && compartorFn(right, left) > 0) {
            bigger = right;
        }
        if(compartorFn(bigger, i) < 0) return;
        swap(arr, bigger, i);
        adjustMaxHeap(arr, bigger, N, compartorFn);
    }

    // 交换
    function swap(arr, i, j) {
        [arr[j], arr[i]] = [arr[i], arr[j]];
    }
</script>
</body>
</html>