最直白的堆排序说明

一、定义

  • 堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。
  • 所以想要理解堆排序，就要想理解二叉堆，以及完全二叉树。
  • 关键在于把数组看成是完全二叉树

二、实现

  • 首先我们要获取最后一个非叶子节点，怎么获取呢？根据性质，假设从 1 开始排序，总共有 L 个节点，最后一个非叶子节点 P 的位置就等于(L/2)向下取整，这个节点的左节点是 2P,右子节点为（2P+1),只要记住这个，堆排序就差不多能写出来了。
  • 堆排序的每次遍历都是找到当前堆内的最大值，放在第一位。所以每一次循环后，我们为了方便，把这个处于第一位的最大值和最后一位的数字交换就行了，剔除这个所谓的有序的最后一位（我这里用个数组保存起来），再去不断找出剩下的数据里面的最大值，直至剩下最后一个就完成了排序
  • 上很糙的代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
var arr = [70,60,12,40,30,8,10];
heapSort(arr)

function heapSort(arr){
   buildHeap(arr);
}
function buildHeap(arr){
   var res = [];
   var i = Math.floor((arr.length-1)/2);
   for(i; i > 0;){ // 循环执行到剩下最后一个
       adjustHeap(arr, i);
       var temp = arr[0];
       arr[0] = arr[arr.length-1];
       arr[arr.length-1] = temp;
       res.push(arr.pop());
       i = Math.floor((arr.length-1)/2);
   }
   res.push(arr.pop())
   console.log(res);
}
function adjustHeap(arr, i){
   for(i; i>0; i--){
       // 每一个非叶子节点和左右子节点比较交换
       if(arr[2*i-1] && arr[2*i]){
           if (arr[2*i-1] > arr[i-1]){
               if(arr[2*i-1] > arr[2*i]){
                   var temp = arr[i-1];
                   arr[i-1] = arr[2*i-1];
                   arr[2*i-1] = temp;
               }else{
                   var temp = arr[i-1];
                   arr[i-1] = arr[2*i];
                   arr[2*i] = temp;
               }
           }else if(arr[2*i] > arr[i-1]){
               var temp = arr[i-1];
               arr[i-1] = arr[2*i];
               arr[2*i] = temp;
           }
       }else{
           var temp = arr[i-1];
           arr[i-1] = arr[2*i-1];
           arr[2*i-1] = temp;
       }
   }
}