算法--堆排序

1、基本概念

堆是二叉树的一种，堆中每个节点都大于其左右子节点称为大顶堆，如果每个节点都小于其左右节点的值则为小顶堆。

使用完全二叉树实现的堆有如下性质

1.2 思路 将待排序的序列构造成大顶堆，此时最大值就是堆的根元素。将它与末尾元素交换，然后将剩余的n-1个元素重新构造成大顶堆，然后再与n-1个元素交换。

2、实现：

public static void main(String[] args) { int[] src = { 3,2,1,4,5,6,7,16,15,14,13,12,11,10,8,9 }; heapSort(src); print(src); } public static void heapSort(int[] array) { if (array == null || array.length <= 1) return; //构建堆 buildMaxHeap(array); for (int i = array.length - 1; i >= 1; i--) { swap(array, 0, i); //对堆进行调整 maxHeap(array, i, 0); } } private static void buildMaxHeap(int[] array) { if (array == null || array.length <= 1) return; int half = array.length / 2; for (int i = half; i >= 0; i--) { maxHeap(array, array.length, i); } } //排大顶堆 private static void maxHeap(int[] array, int heapSize, int index) { int left = index * 2 + 1; int right = index * 2 + 2; int largest = index; //如果下标没越界 且左子节点的值大于当前节点 将下标赋给largest if (left < heapSize && array[left] > array[largest]) largest = left; if (right < heapSize && array[right] > array[largest]) largest = right; //如果需要交换 则进行交换 并递归 if (index != largest) { swap(array, index, largest); maxHeap(array, heapSize, largest); } } public static void swap(int arr[], int i, int j){ int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } public static void print(int src[]){ for (int i = 0; i < src.length; i++) { System.out.print(src[i] + " "); } System.out.println(); }

3、复杂度

构建堆复杂度为O(n)， 查找并交换操作，每次是O(logn), 总共n次 所以总的为O(nlogn)

参考： http://tianxingzhe.blog.51cto.com/3390077/1658816 http://www.iqiyi.com/w_19ru692clp.html