专栏首页stream process堆排序算法的java实现

堆排序算法的java实现

堆积排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,可以利用数组的特点快速定位指定索引的元素。堆排序是不稳定的排序方法,辅助空间为O(1), 最坏时间复杂度为O(nlog2n) ,堆排序的堆序的平均性能较接近于最坏性能。

中心思想是在使用数组存储的完全二叉树内从下往上每次构造大顶堆或者小顶堆,然后将找出来的堆顶数字放到数组结尾,剩下数组继续构造堆结构。

主要是参考了网上比较常见的两种堆排序的java实现,自己加了一些注释

实现1

采用递归,每次父节点与最大子节点交换后递归构造被交换后的子树

    public static void heapSort(int[] array) {
        if (array == null || array.length <= 1) {
            return;
        }

        buildMaxHeap(array);

        System.out.println("buildMaxHeap " + Arrays.toString(array));

        for (int i = array.length - 1; i >= 1; i--) {
            exchangeElements(array, 0, i);

            maxHeap(array, i, 0);

            System.out.println("maxHeap " + Arrays.toString(array) + " i is "
                    + i);
        }

    }



    private static void buildMaxHeap(int[] array) {
        if (array == null || array.length <= 1) {
            return;
        }

        int half = array.length / 2 - 1;
        // 根据二叉树性质,深度为k的二叉树至多有2的k次方-1个结点(k≥1)
        // 所以如果最末尾节点为右节点,array.length为奇数,那么上一层父节点的编号应该为(array.length-1)/2=array.length/2
        // 所以如果最末尾节点为左节点,array.length为偶数,那么上一层父节点的编号也为array.length/2
        // 由于数组下标从0开始,所以应该要在堆对应的编号基础上-1

        // 从下往上把比较中最大的值往顶上冒,冒过后要把被换下来的值对应的子树再做一遍堆调整。
        for (int i = half; i >= 0; i--) {
            maxHeap(array, array.length, i);
        }
    }

    private static void maxHeap(int[] array, int heapSize, int index) {
        // 堆编号x ,数组编号index ,a=index+1;
        // 所以左节点数组编号=2a-1=index * 2 + 1
        // 右节点数组编号=2a+1-1=index * 2 + 2

        int left = index * 2 + 1;
        int right = index * 2 + 2;

        int largest = index;
        if (left < heapSize && array[left] > array[index]) {
            largest = left;
        }

        if (right < heapSize && array[right] > array[largest]) {
            largest = right;
        }

        if (index != largest) {
            exchangeElements(array, index, largest);// 将子节点更大的值换到父节点

            System.out.println("maxHeap " + Arrays.toString(array)
                    + " index is " + index + " left is " + left + " right is "
                    + right + " largest is " + largest + " heapSize is "
                    + heapSize);

            maxHeap(array, heapSize, largest);// 原有父节点的值放到了子节点后可能不满足堆的性质,需要调整修改后largest节点对应的子树
        }
    }

    private static void exchangeElements(int[] array, int index1, int index2) {
        int temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
    }

实现2

while循环,同样父子节点交换后记录被换过的子节点位置,使用while (2 * k + 1 <= lastIndex)循环判断对应的子树是否符合堆性质并调整

    public static void heapSort2(int[] array) {
        for (int i = 0; i < array.length; i++) {
            maxHeap2(array, array.length - 1 - i);
            exchangeElements(array, 0, array.length - 1 - i);
            System.out.println(Arrays.toString(array));
        }

    }

    private static void exchangeElements(int[] array, int index1, int index2) {
        int temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
    }

    private static void maxHeap2(int[] data, int lastIndex) {

        //lastIndex= array.length - 1
        //所以(lastIndex+1)/2-1等于上层最后一个有子节点的节点在数组中的索引
        //(lastIndex+1)/2-1=(lastIndex-1)/2
        for (int i = (lastIndex - 1) / 2; i >= 0; i--) {
            // 保存当前正在判断的节点
            int k = i;
            
        
            
            // 若当前节点的左节点存在
            while (2 * k + 1 <= lastIndex) {//
                
                // biggerIndex总是记录较大节点的值,先赋值为当前判断节点的左子节点
                int biggerIndex = 2 * k + 1;
                if (biggerIndex < lastIndex) {
                    // 若右子节点存在,比较左右子节点大小,右节点不存在biggerIndex为左节点
                    if (data[biggerIndex] < data[biggerIndex + 1]) {
                        // 若右子节点值比左子节点值大,则biggerIndex记录的是右子节点的值
                        biggerIndex++;
                    }
                }
                if (data[k] < data[biggerIndex]) {
                    // 若当前节点值比子节点最大值小,则交换2者得值,交换后将biggerIndex值赋值给k
                    exchangeElements(data, k, biggerIndex);
                    k = biggerIndex; //k记录了原来的父节点被换到了什么位置,原来的父节点下来后不一定比子节点更大
                    //while循环继续去判断它对应的子树符不符合堆的性质并调整
                    System.out.println("k is "+k+" "+Arrays.toString(data));
                    
                } else {
                    //父节点已经比子节点大了,不需要调整
                    break;
                }
                
                //System.out.println();
            }
        }

    }

参考资料

http://blog.csdn.net/apei830/article/details/6584645

http://blog.csdn.net/kimylrong/article/details/17150475

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 二路归并排序的java实现

    转载请注明出处 http://www.cnblogs.com/dongxiao-yang/p/6410775.html

    sanmutongzi
  • PriorityBlockingQueue优先队列的二叉堆实现

    转载请注明原创地址http://www.cnblogs.com/dongxiao-yang/p/6293807.html

    sanmutongzi
  • Java GC CMS 日志分析

    https://blogs.oracle.com/poonam/entry/understanding_cms_gc_logs

    sanmutongzi
  • python--几种快速排序的实现以及运行时间比较

    快速排序的基本思想:首先选定一个数组中的一个初始值,将数组中比该值小的放在左边,比该值大的放在右边,然后分别对左边的数组进行如上的操作,对右边的数组进行如上的操...

    绝命生
  • php实现快速排序算法

    每次排序的时候设置一个基准点,将小于等于基准点的数全部放到基准点的左边,将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样只能在...

    benny
  • 常用七种排序的python实现

    算法复杂度分为时间复杂度和空间复杂度。其中, 时间复杂度是指执行算法所需要的计算工作量;而空间复杂度是指执行这个算法所需要的内存空间。

    用户1432189
  • PHP数组array类常见操作示例

    array_diff(arr1,arr2);//计算数组的差集(对比返回在 array1 中但是不在 array2 及任何其它参数数组中的值。)

    砸漏
  • python 快排算法

    先说两句题外话,一般意义上的栈有两层含义,一层是后进先出的数据结构栈,一层是指函数的内存栈,归根结底,函数的内存栈的结构就是一个后进先出的栈。汇编代码中,调用一...

    葫芦
  • 跟我学习php数组常用函数-下篇

    如果是递归的,结果:array('hobby' => array('a' => 'ping-pong', 'b' => 'basketball'));

    _simple
  • jQuery ajax+PHP实现的级联下拉列表框功能示例

    本文实例讲述了jQuery ajax+PHP实现的级联下拉列表框功能。分享给大家供大家参考,具体如下:

    砸漏

扫码关注云+社区

领取腾讯云代金券