问答题8题:请手写“堆排序”

难度:
更新时间:2021-07-18

参考答案:

算法简介

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

算法描述

具体算法描述如下:

  • 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆,此堆为初始的无序区;
  • 将堆顶元素R[1]与最后一个元素R[n]交换,此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n];
  • 由于交换后新的堆顶R[1]可能违反堆的性质,因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆,然后再次将R[1]与无序区最后一个元素交换,得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1,则整个排序过程完成。

代码实现

1/*方法说明:堆排序 2@param array 待排序数组*/ 3function heapSort(array) { 4 console.time('堆排序耗时'); 5 if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') { 6 //建堆 7 var heapSize = array.length, temp; 8 for (var i = Math.floor(heapSize / 2) - 1; i >= 0; i--) { 9 heapify(array, i, heapSize); 10 } 11 12 //堆排序 13 for (var j = heapSize - 1; j >= 1; j--) { 14 temp = array[0]; 15 array[0] = array[j]; 16 array[j] = temp; 17 heapify(array, 0, --heapSize); 18 } 19 console.timeEnd('堆排序耗时'); 20 return array; 21 } else { 22 return 'array is not an Array!'; 23 } 24} 25/*方法说明:维护堆的性质 26@param arr 数组 27@param x 数组下标 28@param len 堆大小*/ 29function heapify(arr, x, len) { 30 if (Object.prototype.toString.call(arr).slice(8, -1) === 'Array' && typeof x === 'number') { 31 var l = 2 * x + 1, r = 2 * x + 2, largest = x, temp; 32 if (l < len && arr[l] > arr[largest]) { 33 largest = l; 34 } 35 if (r < len && arr[r] > arr[largest]) { 36 largest = r; 37 } 38 if (largest != x) { 39 temp = arr[x]; 40 arr[x] = arr[largest]; 41 arr[largest] = temp; 42 heapify(arr, largest, len); 43 } 44 } else { 45 return 'arr is not an Array or x is not a number!'; 46 } 47} 48var arr=[91,60,96,13,35,65,46,65,10,30,20,31,77,81,22]; 49console.log(heapSort(arr));//[10, 13, 20, 22, 30, 31, 35, 46, 60, 65, 65, 77, 81, 91, 96] 50

算法分析

  • 最佳情况:T(n) = O(nlogn)
  • 最差情况:T(n) = O(nlogn)
  • 平均情况:T(n) = O(nlogn)
预览

小程序刷题更方便

预览

关注公众号获取最新面经

预览

加面试交流群

赞赏支持

预览

题库维护不易,您的支持就是我们最大的动力!