堆排序(heap sort)

10大排序算法.png

堆排序可以认为是对选择排序的一种优化
最好最坏平均时间复杂度：O(nlogn) 空间复杂度：O(1) 属于不稳定排序

执行流程：
1.对序列进行原地建堆 (这一步做的好的话是O(n)级别复杂度)
2.重复执行以下操作，直到堆元素数量为1

• 交换堆顶元素与尾元素
• 堆的元素数量减1
• 对0位置进行一次siftDown操作 (logn级别操作)

public class HeapSort extends Sort {

 private int heapSize;

protected void sort() {
  heapSize = list.length;
  //原地建堆
for(int i = (heapSize>>1)-1; i >=0;i-- )
   siftDown(i);
}

while(heapSize > 1) {
    //交换堆顶元素和尾部元素，然后堆元素数量减一
    swap(0,--heapSize);
   //对0位置进行siftDown(恢复堆的性质)
   siftDown(0);
}

private void siftDown(int index) {
   
   Integer element = list[index];
   int half = heapSize>>1;
   
   while(index < half) {
    
      int childIndex = (index<<1) + 1;
      Integer child = list[childIndex];
      int rightIndex = childIndex + 1;
     if(rightIndex < heapSize && 
       cmp(list[rightIndex],child) > 0) {
          child = list[childIndex=rightIndex];
    }

   if(cmp(element,child) >= 0) break;
   list[index] = child;
   index = childIndex;
 }

  list[index] = element;
  
}

/**
返回值等于0 代表v1==v2
返回值小于0 代表v1 < v2
返回值大于0 代表v1 > v2
*/
private int cmp( int v1, int v2){
    return v1 - v2;
}

//交换两个值
private void swap(int[] list ,int i1, int  i2) {
     int tmp = list[i1];
     list[i1] = list[i2];
     list[i2] = tmp;
}

}


}