堆排序——day6

25. April 2017 深度学习 0
//第六天,堆排序

import java.util.Arrays;

public class heapSort_day6 {

    static final int Max=10;

    private int[] arr;

    

    public heapSort_day6(int[] arr){

        this.arr = arr;

    }

    public void sort(){

        int len = arr.length - 1;

        int beginIndex = (len - 1) >> 1;

        for(int i = beginIndex; i >= 0; i--){

            maxHeapify(i, len);

        }

        for(int i = len; i > 0; i--){

            swap(0, i);

            maxHeapify(0, i - 1);

        }

    }

    

    private void swap(int i,int j){

        int temp = arr[i];

        arr[i] = arr[j];

        arr[j] = temp;

    }

    private void maxHeapify(int index,int len){

        int li = (index << 1) + 1; // 左子节点索引

        int ri = li + 1;           // 右子节点索引

        int cMax = li;             // 子节点值最大索引,默认左子节点。

        

        if(li > len) return;       // 左子节点索引超出计算范围,直接返回。

        if(ri <= len && arr[ri] > arr[li]) // 先判断左右子节点,哪个较大。

            cMax = ri;

        if(arr[cMax] > arr[index]){

            swap(cMax, index);      // 如果父节点被子节点调换,

            maxHeapify(cMax, len);  // 则需要继续判断换下后的父节点是否符合堆的特性。

        }

    }

    public static void main(String[] args) {

    int[] array1=new int[Max];

int i;

for(i=0;i<Max;i++){

array1[i]=(int)(100+Math.random()*100);//产生随机数组

}

        new heapSort_day6(array1).sort();        

        System.out.println(Arrays.toString(array1));

    }

    

}