欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Java排序算法——堆排序

程序员文章站 2024-02-23 10:08:28
...

堆排序

package sort;

public class Heap_Sort {

	public static void main(String[] args) {
		// TODO 自动生成的方法存根
		Heap_Sort qs = new Heap_Sort();
		int[] Arr = {10,9,8,7,6,5,4,3,2,1};
		qs.heapSort(Arr);
		for(int i=0;i<Arr.length;i++){
			System.out.println(Arr[i]);
		}
	}
	
    //调整函数
	public void  headAdjust(int[] elements,int pos,int len){
      //将当前节点值进行保存
      int swap = elements[pos];

      //定位到当前节点的左边的子节点
      int child = pos * 2 + 1;

      //递归,直至没有子节点为止
      while(child < len){
        //如果当前节点有右边的子节点,并且右子节点较大的场合,采用右子节点和当前节点进行比较
        if(child + 1 < len && elements[child] < elements[child + 1]){
          child += 1;
        }

        //比较当前节点和最大的子节点,小于则进行值交换,交换后将当前节点定位于子节点上
        if(elements[pos] < elements[child]){
          elements[pos] = elements[child];
          pos = child;
          child = pos * 2 + 1;
        }
        else{
          break;
        }

        elements[pos] = swap;
      }
    }

    //构建堆
    public void buildHeap(int[] elements){
      //从最后一个拥有子节点的节点开始,将该节点连同其子节点进行比较,
      //将最大的数交换与该节点,交换后,再依次向前节点进行相同交换处理,
      //直至构建出大顶堆(升序为大顶,降序为小顶)
      for(int i=elements.length/2; i>=0; i--){
        headAdjust(elements, i, elements.length);
      }
    }

    public void heapSort(int[] elements){
      //构建堆
      buildHeap(elements);

      //从数列的尾部开始进行调整
      for(int i=elements.length-1; i>0; i--){
        //堆顶永远是最大元素,故,将堆顶和尾部元素交换,将
        //最大元素保存于尾部,并且不参与后面的调整
        //alert(elements);
        int swap = elements[i];
        elements[i] = elements[0];
        elements[0] = swap;
        //alert(elements);
        //进行调整,将最大的元素调整至堆顶
        headAdjust(elements, 0, i);
        //alert(elements);
      }
    }

}