老师看下我自己想的一个堆排序

来源：4-5 基础堆排序和Heapify

敲代码的猫

2017-09-29

我的思路是这样的，对一个数组原地做shiftDown操作，然后第一个元素就是有序的，然后再从第二个开始做shiftDown，第二个也是有序的，然后依次类推到最后整个数组就有序了，老师这种快吗？看下我代码可以优化吗

function shiftDown(arr, k, n, i){
//j和k是在新数组中的索引也就是减去排好序的元素重新生成的数组,他们加上i表示在原来数组中的位置
    while(2*k+1 < n-i){
        let j = 2*k+1;
        if(j+1+i < n && arr[j+1+i] > arr[j+i])
            j = j+1;
        if(arr[k+i] >= arr[j+i])
            break;
        [arr[k+i], arr[j+i]] = [arr[j+i], arr[k+i]];
        k = j;
    }
}

function heapSort(arr, n){
    for(let i = 0; i < n-1;i ++){
            // 这里的j是在新数组中的非叶子节点的位置，加上i表示在真实数组的位置。
        for(let j = Math.floor((n-i-2)/2); j >= 0; j --){
            shiftDown(arr, j, n, i);
        }
    }
}

let arr = [7,3,6,1,9,56,78,16,15,78,56,77,77];
console.log(arr);
heapSort(arr, arr.length);
console.log(arr);

写回答

1回答

liuyubobobo

2017-09-29

通过你的这个过程大概就能推导出时间复杂度了：

function heapSort(arr, n){
    for(let i = 0; i < n-1;i ++){
        for(let j = Math.floor((n-i-2)/2); j >= 0; j --){
            shiftDown(arr, j, n, i);
        }
    }
}

两层for循环的时间复杂度是n^2级别的；shiftDown的时间复杂度是logn级别的，所以整体时间复杂度是O(n^2*logn)级别的：）

看看4-6，把你的算法和标准的堆排序算法比较一下看看：）

liuyubobobo

敲代码的猫

先测一下这样是否真正完成了排序？：）

2017-09-29

共5条回复

算法与数据结构（C++版）面试/评级的算法复习技能包

课程专为：短时间内应对面试、升职测评等艰巨任务打造

11187 学习 · 1614 问题

查看课程

相似问题