详解如何在Java中实现堆排序算法

package com.zhiyiyo.collection.sort;

import java.util.Arrays;

public class HeapSort extends BaseSort {

     @Override

     public void sort(Comparable[] array) {

         int N = array.length;

         // 创建最大堆

         for ( int i = N / 2 ; i >= 0 ; i--) {

             sink(array, i, N);

         }

         // 就地排序

         while (N > 0 ) {

             // 将最大的元素移动到数组的尾部，同时将未排序的长度-1

             swap(array, 0 , --N);

             // 调整最大堆

             sink(array, 0 , N);

         }

     }

     /**

      * 下沉元素

      *

      * @param array 数组

      * @param k     下沉的元素索引

      */

     private void sink(Comparable[] array, int k, int N) {

         while ( 2 * k + 1 < N) {

             int j = 2 * k + 1 ;

             if (j < N - 1 && less(array[j], array[j + 1 ])) j++;

             if (!less(array[k], array[j])) break ;

             swap(array, k, j);

             k = j;

         }

     }

}

package com.zhiyiyo.collection.sort;

/**

  * 数组排序抽象类

  */

public abstract class BaseSort {

     public abstract void sort(Comparable[] array);

     /**

      * 交换数组元素

      *

      * @param array 数组

      * @param a     数组下标 a

      * @param b     数组下标 b

      */

     protected static void swap(Comparable[] array, int a, int b) {

         Comparable tmp = array[a];

         array[a] = array[b];

         array[b] = tmp;

     }

     protected static boolean less(Comparable a, Comparable b) {

         return a测试数据pareTo(b) < 0 ;

     }

}

package com.zhiyiyo.collection.sort;

import org.junit.Test;

import java.util.Arrays;

public class HeapSortTest {

     @Test

     public void sort() {

         Integer[] array = { 5 , 10 , 9 , 6 , 8 , 7 , 2 , 1 , 4 , 3 };

         new HeapSort().sort(array);

         System.out.println(Arrays.toString(array));

     }

}