面试手撕堆排序

• 堆排序代码如下（注释见下）：

  1. 首先将待排序的数组构造成一个大根堆，此时，整个数组的最大值就是堆结构的堆顶

  2. 将堆顶的数与末尾的数交换，此时，末尾的数为最大值，剩余待排序数组个数为n-1

  3. 将剩余的n-1个数再构造成大根堆，再将堆顶数与n-1位置的数交换，如此反复执行，便能得到有序数组

  public class Main {void heapSort(int[] a, int n){for(int i = n / 2 - 1; i >= 0; i--){adjustHeap(a, i, n);}for(int i = n - 1; i > 0; i--){int temp = a[0];a[0] = a[i];a[i] = temp;adjustHeap(a, 0, i);}}void adjustHeap(int[] a, int i, int n){int largest = i;int l = 2* i + 1;int r = 2* i + 2;if(l < n && a[largest] < a[l]){largest = l;}if(r < n && a[largest] < a[r]){largest = r;}if(largest != i){int temp = a[largest];a[largest] = a[i];a[i] = temp;adjustHeap(a, largest, n);}}
  }
  

• 测试用例：

  public class Main {public static void main(String[] args) {int[] a = {8,4,5,7,1,3,6,2};int n = 8;heapSort(a, n);for(int i = 0; i < a.length; i++){System.out.print(a[i] + " ");}//System.out.println(Arrays.toString(a));//Arrays.toString()方法是方便数组类型输出,不用使用for遍历数组}static void heapSort(int[] a, int n){//1.建堆for(int i = n / 2 - 1; i >= 0; i--){//从第一个非叶节点开始，从下往上进行判断，每个节点都要维护堆的性质adjustHeap(a, i, n);}//2.排序for(int i = n - 1; i > 0; i--){//i必须>0，不能等于//交换堆顶元素和末尾元素int temp = a[0];a[0] = a[i];a[i] = temp;//维护剩余元素的堆的性质adjustHeap(a, 0, i);//0表示从堆顶元素开始维护，i表示剩余的元素个数，原来是n个，现在是n-1个，即i个}}//维护堆的性质（保证是一个大顶堆）static void adjustHeap(int[] a, int i, int n){//i为待维护的节点下标，n为数组长度int largest = i;//i节点为当前父节点int l = 2* i + 1;//左子节点int r = 2* i + 2;//右子节点//找出父节点，左子节点，右子节点中最大值的那个下标largestif(l < n && a[largest] < a[l]){//如果左子节点存在，且大于父节点largest = l;//交换下标}if(r < n && a[largest] < a[r]){//如果右子节点存在，且大于父节点largest = r;//交换下标}if(largest != i){//如果i位置的节点有孩子比他大//交换节点的值,让最大节点的值跑到父节点上，i节点的值跑到了左右孩子上int temp = a[largest];a[largest] = a[i];a[i] = temp;//递归处理每个子树，当前需要维护的节点下标为largestadjustHeap(a, largest, n);}}
  }
  

  输出结果
  （1）Arrays.toString(a)输出结果：
  
  （2）for循环输出结果：
  

成语解释