Free考研资料

标题: 堆排序代码加注释JAVA（直接能跑！） [打印本页]

---

作者: Heavyliu    时间: 09-12-23 00:46
标题: 堆排序代码加注释JAVA（直接能跑！）
希望能给大家一点帮助 自己看了然后访写了之后对理解是有帮助的！

---

作者: Heavyliu    时间: 09-12-23 00:47
除了点意外 附件没有加上来  重发一个

---

作者: Heavyliu    时间: 09-12-23 00:49
/*堆排序（大根堆）  在这里需要强调的是，起排的的数列是从1号单元开始！
* 主要思想是，首先将数组对应的完全二叉树建立成为大根堆！   然后将大根堆的根节点和最后的叶子结点交换，再对新的完全
* 二叉树进行大根堆的调整， 反复进行，知道排序完成
*/
public class HeapSort {
  public static void main(String agrs[])
  {
          int []heapList;
          heapList = new int[] {0,7,9,2,8,1,4,6,3};   //初始化一个int类型的数组，数组对应一颗完全二叉树
          int length = heapList.length;
          
          //将此数组打印出来
          System.out.println(\"Now we get a array that is :\");
          for(int i=1;i<length;i++)
          {
             System.out.println(\"heapList[\"+i+\"]=\"+heapList);
          }       
          
          //+++++++++++++++++开始排序++++++++++++++++++++++++++++++++
          BuildHeap(heapList);      //将此数组建成大根堆，将此数组中的最大的元素，调整到根节点。
          for(int i=1;i<length;i++ )//数组在内存中是从0单元开始到length-1号单元，
          {                         //在这里方便编程,我们舍去0号单元的作用，把数组看成从1号单元开始存数！
                  //将根节点和最后一个叶子节点对调。
                  int temp = heapList[length-i];
                  heapList[length-i]=heapList[1];
                  heapList[1]= temp;//这个时候数组的末尾已经是最大的元素了
                  HeapAdjust(heapList,1,length-i-1); //这个地方length-i-1的减1是相当重要的
          }
          //++++++++++++++++排序结束+++++++++++++++++++++++++++++++++++++++
          
          //打印排序后的结果
          System.out.println(\"After the Heap sort,the sequence turned to be :\");
          for(int i=1;i<length;i++)
          {
             System.out.println(\"heapList[\"+i+\"]=\"+heapList);
          }
  }// main over
  
/*将数组L[1..n]建成一个大根堆，必须将它对应的完全二叉树中的每一个节点为根的子树调整为大根堆
  * 方法是依次将序号最大（也就是最后一个副分支）的子树分支（从序号为n/2的单元为根结点的分支开始）一直到根节点r[1]为止！
  */
  public static  void BuildHeap(int[] list )
  {
          int n = list.length;
          for(int i=n/2;i>0;i--)
          {
                  HeapAdjust(list,i,n-1);
          }
          
  }//BuildHeap
  
  
  /* 面对一棵完全二叉树与其相应的数组，其中根节点对应数组中下标为begin，树种的最后一个节点对应数组下标end
   * 调整此完全二叉树成为大根堆
   * ---此函数的操作对象是完全二叉树，每次函数结束，都能将此树换成大根堆
   */
  public static void HeapAdjust(int[] list, int begin, int end)   
  {
          int temp = list[begin];//将根节点取出来复制一份
          for(int i=2*begin;i<=end;i=2*i)//设i为begin的左孩子
          {
                  if(i<=end-1&&list<list[i+1])//如果左孩子<右孩子
                    i++;           //i变成右孩子的序号
                  if(temp>=list)//将根节点和比较大的孩子进行比较，若根节点比较大，则不用调整
                          break;       //跳出函数
                  else if(temp<list) //如果是根节点比较小，则将较大的孩子放到根的位置
                          list[begin]=list;
                  begin =i;  //然后在把目标放在原来较大孩子作为根节点的子树上，重复以上的操作，进行大小比较和调整
          }
          //经过一系列的调整，得到了最初的那棵树的根节点的最终位置
          list[begin]=temp;
  }//HeapAdjust
}

---

作者: 花花人    时间: 09-12-26 23:48
标题: 回复 #1 Heavyliu 的帖子
谢谢啦楼哦啦！

---

欢迎光临 Free考研资料 (http://test.freekaoyan.com/)

Powered by Discuz! X3.2