学步园

堆排序，时间复杂度是O(nlogn)，原地排序

重点是堆（最大堆，最小堆）这种数据结构。一个堆在逻辑上是一颗完全二叉树样的东东，最大堆的特点是父结点的值比两个子结点的值要大，此外没有其它特点了，最小堆的定义类似。

这章讲了用最大堆来排序，然后讲了用堆来实现优先队列。由于实现堆的时间犯了点小错误，调试了大半个小时，因此优先队列的代码还没来得及实现呢，明天补上吧。

下面是堆排序的内容。

这里是用数组来实现堆的，关于再者的关系，我觉得下面这个图应该表达得很清楚。当然了，下面的代码数组的下标是从0开始的。

整个堆排序的算法，核心在于maxHeapity(int i) 这个函数，它的作用是保持下标为i的结点和它的两个子结点之间的最大堆的性质（即结点i的值要比它的两个子结点的值要大）。

堆排序的算法思想是：

1. 给定一个待排序的数组，在它上面建一个最大堆。
2. 这时，根结点的值一定是最大的，因此，把它与数组的最后一个元素交换。交换之后，数组的最大值就存在于最后一个位置了。
3. 但是对于根结点与它的两个子结点，它们之间可能违背了最大堆的性质，因此，需要调用一次maxHeapity(int 0)，以保持最大堆的性质。
4. 在此之后，当前的根结点的值又是当前的最大值（除了刚才的最大值之外的）。因此，将它与数组的倒数第二个元素进行交换，并重复第3步。
5. 这样一直循环，直到数组中第二小的元素处于第二个位置上为止。此时最小的元素一定在第一个位置上
6. 
   

Java code：

Java code：<br /> view plaincopy to clipboardprint?<br /> package com.zy.sortalgorithms;<br /> public class HeapSort implements SortAlgorithm {<br /> private int[] arr;<br /> private int heapSize; //堆的大小，注意与数组的长度区分开来，其实就是用来维持 堆的最后一个结点 在数组中的下标的<br /> @Override<br /> public void sort(int[] a) {<br /> // TODO Auto-generated method stub<br /> int len = a.length;<br /> arr = a;<br /> heapSize = len-1;<br /> //执行堆排序<br /> heapSort();<br /> }<br /> //取得结点i的父结点<br /> public int parent(int i) {<br /> return (i-1)/2;<br /> }<br /> //取得结点i的左孩子<br /> public int left(int i) {<br /> return 2*i+1;<br /> }<br /> //取得结点i的右孩子<br /> public int right(int i) {<br /> return 2*i + 2;<br /> }<br /> //建立最大堆<br /> public void buildMaxHeap(){<br /> for(int i=heapSize/2; i>=0; i--)<br /> {<br /> maxHeapity(i);<br /> }<br /> }<br /> //让i结点及其子结点保持最大堆的性质<br /> public void maxHeapity(int i) {<br /> int l = left(i);<br /> int r = right(i);<br /> int largest = i;<br /> //取得｛结点i，i的左孩子，i的右孩子｝三者当中的最大值的下标，赋给largest<br /> if(l<=heapSize&&arr[l]>arr[i])<br /> {<br /> largest = l;<br /> }<br /> if(r<=heapSize&&arr[r]>arr[largest])<br /> {<br /> largest = r;<br /> }<br /> //如果largest不等于i，则将i与largest两者的值交换，以保持最大堆的性质<br /> if(largest!=i)<br /> {<br /> int temp = arr[i];<br /> arr[i] = arr[largest];<br /> arr[largest] = temp;<br /> maxHeapity(largest); //同时递归处理largest结点.<br /> } </p> <p> }<br /> //真正执行排序的地方<br /> public void heapSort() {<br /> buildMaxHeap(); //先建起最大堆<br /> int temp;<br /> for(int i=heapSize; i>0; i--) {<br /> //将根结点元素与最后一个结点（注意不是数组的最后一个元素，最后一个结点的下标由heapSize维持）<br /> temp = arr[0];<br /> arr[0] = arr[i];<br /> arr[i] = temp;<br /> //将最后一个结点的下标--<br /> heapSize--;<br /> //维持根结点处的最大堆性质<br /> maxHeapity(0);<br /> }<br /> }<br /> }<br />