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

Question

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

Answer 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，把你的算法和标准的堆排序算法比较一下看看：）

• 提问者 敲代码的猫 #1

  从非叶子节点做shiftDown和从第一个元素做shiftDown是不是得到的结果都是一样的，有什么区别呢

• liuyubobobo 回复 提问者 敲代码的猫 #2

  你的算法的内层循环每次都重新将[i...n]的部分多次调用shiftDown方法整理成堆；4-6的代码每次只调用一次shiftDown即可维护堆的性质。请仔细比较一下两个代码的不同：）

• 提问者 敲代码的猫 #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
      }
  }

点开查看后面2条评论