資料結構與算法Java實作-17堆排序

堆排序

package aStudy.day9;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * @author haoqi
 * @Date 2020/10/7 - 20:55
 *
 * 堆排序，（選擇排序，不穩定）
 */
public class data03 {
    public static void main(String[] args) {
        //要求将數組進行升序排序
//        int[] arr = {4, 6, 8, -1,20,5, 9};
//        heapSort(arr);

        //測試效率
        int[] arr = new int[80000];
        for (int i = 0; i < 80000; i++) {
            arr[i] = (int) (Math.random()*80000);
        }

        SimpleDateFormat format = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");

        Date date1 = new Date();
        String date1Str = format.format(date1);
        System.out.println(date1Str);

        heapSort(arr);

        Date date2 = new Date();
        String date2Str = format.format(date2);
        System.out.println(date2Str);

    }
    public static void heapSort(int[] arr){
        int temp = 0;
        System.out.println("進入大頂堆排序~~");

//        adjustHeap(arr,1,arr.length); //i--
//        System.out.println("1> "+ Arrays.toString(arr)); //1> [4, 9, 8, 5, 6]
//        adjustHeap(arr,0,arr.length); //排序好了
//        System.out.println("2> "+ Arrays.toString(arr)); //2> [9, 6, 8, 5, 4]

        //封裝
        int cnt = 0;
        for (int i = arr.length/2 -1; i>=0; i--){
            cnt++;
            adjustHeap(arr,i,arr.length);
//            System.out.println(cnt+"> "+ Arrays.toString(arr));
        }
        /*
		 * 2).将堆頂元素與末尾元素交換，将最大元素"沉"到數組末端;
　　			3).重新調整結構，使其滿足堆定義，然後繼續交換堆頂元素與目前末尾元素，反複執行調整+交換步驟，直到整個序列有序。
		 */
        for (int j = arr.length-1; j>=0; j--) {
            //temp
            temp = arr[j];
            arr[j] = arr[0]; //arr[0] 是堆頂元素最大值
            arr[0] = temp;
            adjustHeap(arr,0,j);
        }
//        System.out.println("\n交換後> "+ Arrays.toString(arr));

    }

    /**
     *
     * @param arr   要調整的數組
     * @param i     非葉子節點在數組中的索引
     * @param lenght    還需要調整的元素個數，length不斷減少
     */
    //将一個數組調整為一個大頂堆
    public static void adjustHeap(int[] arr, int i, int lenght){
        int temp = arr[i]; //定義臨時周遊儲存目前元素
        //ready go
        //k = i*2+1表示 i 節點的左子節點
        for (int k = i*2+1; k < lenght; k = k*2+1) {
            if (k+1 < lenght && arr[k] < arr[k+1]) //說明左子結點的值小于右子結點的值
                k++;
            if (arr[k] > temp){ //子節點大于父節點
                arr[i] = arr[k]; //則交換
                i = k; //注意：此時的 i 在k 的位置 繼續循環比較
            } else break;
        }
        //當for 循環結束後，我們已經将以i 為父結點的樹的最大值，放在了 最頂(局部)
        arr[i] = temp; //将 temp 放到最後的位置
    }

}

           

r 循環結束後，我們已經将以i 為父結點的樹的最大值，放在了 最頂(局部)

arr[i] = temp; //将 temp 放到最後的位置

}

}

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-cUCr9rsl-1602293336478)(C:\Users\haoqi\AppData\Roaming\Typora\typora-user-images\image-20201007212335219.png)]