美文网首页
堆排序算法

堆排序算法

作者: cc卡耐基 | 来源:发表于2020-02-05 12:26 被阅读0次

    最近又要回顾一下各类排序算法,堆排序,一个时间复杂度不太稳定的算法,根据完全二叉树的特性来建立算法过程。

    步骤

    1. 调整一轮大顶堆,把最大值调至顶部节点。此时所有叶子节点应该都小于其父节点(父节点大于子节点的调整)
    2. 将顶部节点(最大值)与最后叶子节点替换
    3. 排序指针指向倒数第二个叶子节点,继续调整一轮大顶堆
    4. 重复2,3步骤

    简单来说,结果就是每轮把最大值调整到本轮里最后一个叶子节点,来完成排序过程。

    上代码(java)

    public class HeapSort
    {
    
      public HeapSort(int[] list) {
        //{4,6,3,1,7,9,2,5,11,8,10}
        this.list = list;
      }
    
      public void execute() {
        int[] result = HeapSort.StartSort(this.list); //将初始化数组传入
        //this.show(result);
      }
    
      public static int[] StartSort(int[] array) {
            len = array.length;
            if (len < 1) return array;
            //1.构建一个最大堆
            buildMaxHeap(array);
            
            //打印出每步的构建过程
            for(int i : array) {
                System.out.print(i + ",");
            }
            System.out.println("");
            
            //2.循环将堆首位(最大值)与末位交换,然后在重新调整最大堆
            while (len > 0) {
                swap(array, 0, len - 1);
                len--;
                adjustHeap(array, 0);
                
                for(int i : array) {
                    System.out.print(i + ",");
                }
                System.out.println("");
            }
            return array;
        }
    
       public static void buildMaxHeap(int[] array) {
            //从最后一个非叶子节点开始向上构造最大堆
            for (int i = (len/2 - 1); i >= 0; i--) { 
                adjustHeap(array, i);
            }
        }
    
      public static void adjustHeap(int[] array, int i) {
            int maxIndex = i;
            
            int left_c = (i + 1) * 2 - 1;
            int right_c = (i + 1) * 2;
            
            //如果有左子树,且左子树大于父节点,则将最大指针指向左子树
            if ( left_c < len && array[left_c] > array[maxIndex]) {
                maxIndex = left_c;
            }
            
            //如果有右子树,且右子树大于父节点,则将最大指针指向右子树
            if ( right_c < len && array[right_c] > array[maxIndex]) {
                maxIndex = right_c;
            }
            
            //如果父节点不是最大值,则将父节点与最大值交换,并且递归调整与父节点交换的位置。
            if (maxIndex != i) {
                swap(array, maxIndex, i);
                adjustHeap(array, maxIndex);
            }
        }
    }
    

    代码参考
    https://www.cnblogs.com/guoyaohua/p/8600214.html
    这个作者的堆排序似乎有问题,adjustHeap函数,起始的左右节点的位置不对。导致有几位并没有排序成功。

    相关文章

      网友评论

          本文标题:堆排序算法

          本文链接:https://www.haomeiwen.com/subject/argjxhtx.html