美文网首页
堆排序-不新建数组

堆排序-不新建数组

作者: 执着的人请保持微笑 | 来源:发表于2023-05-07 09:34 被阅读0次

//排序数组生成堆的方法

  void createPile(List sortArray, int childIndex)

  {

    int child = childIndex;

    int parent = (child-1) ~/ 2;

    while (child > 0) {

      if (sortArray[child] > sortArray[parent]) {

        int replaceObject = sortArray[child];

        sortArray[child] = sortArray[parent];

        sortArray[parent] = replaceObject;

        child = parent;

        parent = (child-1) ~/ 2;

      }else

      {

        break;

      }

    }

  }

  //删除堆定元素后从新创建堆的方法

  void sortPile(List sortArray, int totalSize, int rootIndex){

    int parent = rootIndex;

    int child = parent*2+1;//左孩子的下标

    //如果孩子节点下标大于父节点的,说明已经不满足条件了,已经成堆了

    while (child < totalSize) {

      //选出左右孩子中最小的那个

      if ((child + 1 < totalSize) && (sortArray[child+1] > sortArray[child])) {

        child ++;

      }

      //如果最小的孩子比父节点的小,需要交换位置

      if (sortArray[child] > sortArray[parent]) {

        int replaceObject = sortArray[child];

        sortArray[child] = sortArray[parent];

        sortArray[parent] = replaceObject;

        parent = child;//父节点交换到了孩子节点

        child = parent*2+1;//计算新的孩子节点

      }else

      {

        //不满足的话就跳出循环

        break;

      }

    }

  }

//待排序数组

          var sortArray = [1,2,5,1000,500,200,49,100,50,40,30,20];

          //打印待排序数组

          print(sortArray);

          for (var i = 0; i < sortArray.length; i++) {

            createPile(sortArray, i);//创建大顶堆

          }

          for (var i = 0; i < sortArray.length; i++) {

//把堆的第一个元素和最后一个元素交换位置,堆顶的最大元素放到了最后边

            int replaceObject = sortArray[0];

            int lastIndex = sortArray.length-1-i;

            sortArray[0] = sortArray[lastIndex];

            sortArray[lastIndex] = replaceObject;

//从新建大顶堆

            sortPile(sortArray, sortArray.length-i-1, 0);

          }

          print("排完序的数组${sortArray}");

相关文章

  • 排序

    原创 堆排序: 使用visit数组从本质出发获取大顶堆排序。

  • 新建数组,不指向旧数组

    避免影响到旧数组的方法 --by Affandi ⊙▽⊙

  • 堆排序 ---应用篇

    上篇堆排序介绍堆排序的基本过程,本文说下堆排序的应用实例。 大纲 创建Huffman树 合并K个有序数组 1. 创...

  • 堆排序

    堆排序算法利用堆的结构来执行快速排序。 为了实现从最低到最高排序,堆排序首先将未排序的数组转换为最大堆,以便数组中...

  • 数组-堆排序

    采用堆排序方式对数组进行排序 堆排序百科:堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法.堆...

  • 2018-06-30

    排序算法之堆排序 堆排序是利用堆的数据结构而设计的一种排序算法,堆排序是一种选择排序。可以利用数组的特点快速定位制...

  • 数组基础

    数组基础 新建数组 数组方法和属性 数组合并 数组常用方法

  • LeetCode912 使用堆排序解决

    堆排序 给你一个整数数组 nums,请你将该数组升序排列。示例 1:输入:nums = [5,2,3,1]输出:[...

  • 数组基础

    数组基础 新建数组 数组方法和属性 数组常用方法 数组的遍历方法

  • 前端面试题

    数组去重indexOf() 方法可返回某个指定的字符串值在字符串中首次出现的位置。新建一新数组,遍历传入数组,值不...

网友评论

      本文标题:堆排序-不新建数组

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