堆排序

作者: 海是倒过来的天_67f2 | 来源:发表于2019-08-12 22:55 被阅读0次

    public class HeapSort {

        public static void main(String []args){

            int [] arr = {20,50,20,40,70,10,80,30,60};

            heapSort(arr);

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

        }

        private static void heapSort(int[] arr) {

            if (arr == null || arr.length<2){

                return;

            }

            //构建大顶堆

            for (int i = arr.length>>1; i >=0; i--) {

                adjustHead(arr,i,arr.length);

            }

            //交换顶部文件并调整堆结构

            for (int j = arr.length-1; j >0 ; j--) {

                adjustHead(arr,0,j);

                swap(arr,0,j);

            }

        }

        private static void swap(int[] arr, int i, int j) {

            int temp = arr[i];

            arr[i] = arr[j];

            arr[j] = temp;

        }

        private static void adjustHead(int[] arr, int i, int length) {

            int temp = arr[i];

            for (int j = i*2+1; j < length; j=j*2+1) {

                if (j+1<length && arr[j]<arr[j+1]){

                    j++;

                }

                if (arr[j]>temp){

                    arr[i] = arr[j];

                    i = j;

                } else {

                    break;

                }

            }

            arr[i] = temp;

        }

    //    private static void heapSort(int[] arr) {

    //

    //        //构建大顶堆

    //        for (int i = arr.length/2; i >=0; i--) {

    //            adjustHeap(arr,i,arr.length);

    //        }

    //        //交换堆顶元素与末尾元素,调整堆结构

    //        for (int j = arr.length-1; j >0 ; j--) {

    //            swap(arr, 0,j);

    //            adjustHeap(arr,0,j);

    //        }

    //    }

    //

    //    private static void swap(int[] arr, int i, int j) {

    //        int temp = arr[i];

    //        arr[i]= arr[j];

    //        arr[j]=temp;

    //    }

    //

    //    private static void adjustHeap(int[] arr, int i, int length) {

    ////        int temp = arr[i];

    ////        for (int k = i*2+1; k < length; k = k*2+1) {

    ////            if (k+1<length && arr[k]<arr[k+1]){

    ////                k++;

    ////            }

    ////            if (arr[k]>temp){

    ////                arr[i]= arr[k];

    ////                i = k;

    ////            } else {

    ////                break;

    ////            }

    ////        }

    ////        arr[i] = temp;

    //

    //        int temp = arr[i];

    //        for (int j = i*2+1; j < length; j=j*2+1) {

    //            if (j+1<length && arr[j]<arr[j+1]){

    //                j++;

    //            }

    //            if (arr[j]>temp){

    //                arr[i] = arr[j];

    //                i = j;

    //            } else {

    //                break;

    //            }

    //        }

    //        arr[i]= temp;

    //    }

    }

    相关文章

      网友评论

          本文标题:堆排序

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