Đang tải…
Đang tải…
Xây max-heap rồi liên tục đưa gốc (lớn nhất) về cuối và khôi phục heap — tại chỗ và O(n log n) trong mọi trường hợp.
Xây dựng max-heap.
1void heapSort(int[] arr) {2 int n = arr.length;3 for (int i = n/2-1; i >= 0; i--) siftDown(arr, i, n); // xây max-heap4 for (int end = n-1; end > 0; end--) { // thu nhỏ heap5 int temp = arr[0]; arr[0] = arr[end]; arr[end] = temp; // lớn nhất về cuối6 siftDown(arr, 0, end); // khôi phục heap7 }8}9void siftDown(int[] arr, int root, int end) {10 while (2*root+1 < end) { // khi còn con11 int child = 2*root+1;12 if (child+1 < end && arr[child+1] > arr[child]) child++; // chọn con lớn hơn13 if (arr[root] >= arr[child]) break; // đúng thứ tự heap14 int temp=arr[root]; arr[root]=arr[child]; arr[child]=temp; root=child; // hoán đổi xuống15 }16}