Go语言视频零基础入门到精通

javalearner

思想最重要，结合图形来分析就简单了： 实现的是小顶堆排序算法,大堆思路差不多： java代码： package org.forever.music.dao;
/** 就地堆排序 */
public class HeapSort {
        public int size;// 记录规模
        // 构造方法
        public HeapSort() {
                size = 0;
        }
        // 建堆方法，只需线性时间建好
        public void buildHeap(int[] num) {
                size = num.length;// 获取堆的规模
                for (int i = num.length / 2 - 1; i >= 0; i--) {// 对前一半的节点，
                        percolateDown(num, i);// 进行下滤操作
                }
        }
        // 给定数组交换两个数的位置
        public void swap(int[] num, int v, int u) {
                int temp = num[v];
                num[v] = num;
                num = temp;
        }
        // 对该数进行上滤操作，直到该数比父节点大就停止上滤
        public void percolateUp(int[] num, int index) {
                while (index != 0) {// 只要下标不为0
                        int parent = (index - 1) / 2;// 获取该数的父节点
                        if (num[index] < num[parent]) {// 和父节点进行比较
                                swap(num, index, parent);// 如果比父节点小，就交换两个的位置
                                index = parent;// 更新index的指向
                        }
                }
        }
        /******************************* 排序用的方法 ************************************/
        public int getSize() {
                return size;
        }
        // 判断该数是否有左节点
        public boolean hasLChildTwo(int index) {
                return index * 2 + 1 < size ? true : false;
        }
        // 判断该数是否有右节点
        public boolean hasRChildTwo(int index) {
                return index * 2 + 2 < size ? true : false;
        }
        // 对该数进行下滤操作，直到该数比左右节点都小就停止下滤
        public void percolateDown(int[] num, int index) {
                int min;// 设置最小指向下标
                while (hasLChildTwo(index)) {// 如果该数有左节点，则假设左节点最小
                        min = index * 2 + 1;// 获取左节点的下标
                        if (hasRChildTwo(index)) {// 如果该数还有右节点
                                if (num[min] > num[index * 2 + 2]) {// 就和左节点分出最小者
                                        min = index * 2 + 2;// 此时右节点更小，则更新min的指向下标
                                }
                        }
                        // 此时进行该数和最小者进行比较，
                        if (num[index] < num[min]) {// 如果index最小，
                                break;// 停止下滤操作
                        } else {
                                swap(num, index, min);// 交换两个数，让大数往下沉
                                index = min;// 更新index的指向
                        }
                }// while
        }
        /*********************************************************************/
        public static void main(String[] args) {
                int[] num = { 6, 4, 1, 2, 8, 4, 7, 3, 0, 9 };
                HeapSort heap = new HeapSort();
                heap.buildHeap(num);// 建立小顶堆
                for (int i = 0; i < num.length; i++) {
                        System.out.print(num + " ");
                }
                System.out.println();
                for (int i = num.length - 1; i >= 1; i--) {
                        heap.swap(num, 0, i);// 交换
                        heap.size--;// 每交换一次让规模减少一次
                        heap.percolateDown(num, 0);// 将新的首元素下滤操作
                }
                for (int i = 0; i < num.length; i++) {
                        System.out.print(num + " ");
                }
        }
}
                        [/code] 运行结果：
0 2 1 3 8 4 7 6 4 9
9 8 7 6 4 4 3 2 1 0 下面是例子的图形分析： 图1：
  图2：

  图3：

   

   
     
     
      
      

        
      

        
      
     
   

  


源码下载：http://file.javaxxz.com/2014/11/10/000219828.zip