- import java.util.Arrays;
- /**
- * @author stefanie zhao
- */
- public class HeapSort {
- public static void heapSort(DataWrap[] data) {
- System.out.println("begin sort....");
- int arrayLength = data.length;
- // 循环建堆
- for (int i = 0; i < arrayLength - 1; i++) {
- buildMaxHeap(data, arrayLength - 1 - i);
- swap(data, 0, arrayLength - 1 - i);
- System.out.println(Arrays.toString(data));
- }
- }
- private static void buildMaxHeap(DataWrap[] data, int lastIndex) {
- // 从lastIndex处节点的父节点开始
- for (int i = (lastIndex - 1) / 2; i >= 0; i--) {
- int k = i;
- // 如果当前k节点的子节点存在
- while (k * 2 + 1 <= lastIndex) {
- // k节点的左子节点的索引
- int biggerIndex = 2 * k + 1;
- // 如果biggerIndex小于lastIndex,即biggerIndex+1
- // 代表k节点的右子节点存在
- if (biggerIndex < lastIndex) {
- // 如果右子节点的值较大
- if (data[biggerIndex].compareTo(data[biggerIndex + 1]) < 0) {
- biggerIndex++;
- }
- }
- // 如果k节点的值小于较大子节点的值
- if (data[k].compareTo(data[biggerIndex]) < 0) {
- swap(data, k, biggerIndex);
- // 将biggerIndex赋给k,开始while循环的下一次循环,重新保证k节点的值大于其左右子节点的值
- k = biggerIndex;
- } else {
- break;
- }
- }
- }
- }
- private static void swap(DataWrap[] data, int i, int j) {
- DataWrap tmp = data[i];
- data[i] = data[j];
- data[j] = tmp;
- }
- public static void main(String[] args) {
- DataWrap[] data = { new DataWrap(9, ""), new DataWrap(79, ""), new DataWrap(46, ""), new DataWrap(30, ""),
- new DataWrap(58, ""), new DataWrap(49, "") };
- System.out.println("before sort: \\n" + Arrays.toString(data));
- heapSort(data);
- System.out.println("after sort: \\n" + Arrays.toString(data));
- }
- }
- class DataWrap implements Comparable<DataWrap>{
- int data;
- String flag;
- public DataWrap(int data, String flag) {
- this.data = data;
- this.flag = flag;
- }
- @Override
- public String toString() {
- return data + flag;
- }
- @Override
- public int compareTo(DataWrap o) {
- return this.data > o.data ? 1 : (this.data == o.data ? 0 : -1);
- }
- }
- //该片段来自于http://www.codesnippet.cn/detail/2412201514301.html
来源: http://www.codesnippet.cn/detail/2412201514301.html