请稍等 ...
×

采纳答案成功!

向帮助你的同学说点啥吧!感谢那些助人为乐的人

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

我的思路是这样的,对一个数组原地做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);


正在回答 回答被采纳积分+3

1回答

liuyubobobo 2017-09-29 11:54:31

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

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,把你的算法和标准的堆排序算法比较一下看看:)

0 回复 有任何疑惑可以回复我~
  • 提问者 敲代码的猫 #1
    从非叶子节点做shiftDown和从第一个元素做shiftDown是不是得到的结果都是一样的,有什么区别呢
    回复 有任何疑惑可以回复我~ 2017-09-29 11:59:15
  • liuyubobobo 回复 提问者 敲代码的猫 #2
    你的算法的内层循环每次都重新将[i...n]的部分多次调用shiftDown方法整理成堆;4-6的代码每次只调用一次shiftDown即可维护堆的性质。请仔细比较一下两个代码的不同:)
    回复 有任何疑惑可以回复我~ 2017-09-29 12:11:07
  • 提问者 敲代码的猫 #3
    这个版本呢,老师。
    function heapSort(arr, n){
        for(let i = 0; i < n-1;i ++){
            shiftDown(arr, 0, n-i);
            [arr[0], arr[n-1-i]] = [arr[n-1-i], arr[0]]; // swap
        }
    }
    回复 有任何疑惑可以回复我~ 2017-09-29 12:55:45
问题已解决,确定采纳
还有疑问,暂不采纳
意见反馈 帮助中心 APP下载
官方微信