高手讲解下算法导论中...

Question

【堆排序法and线性时间排序】并写下java的代码，小弟初学的..添加个注释....谢谢了...

Answer 1

// 堆排序
public static void heapSort(int[] arr) {
for (int i = arr.length / 2; i >= 0; i--) {
maxHeap(arr, i, arr.length);
}
for (int i = arr.length - 1; i >= 1; i--) {
arr[0] ^= arr[i];
arr[i] ^= arr[0];
arr[0] ^= arr[i];
maxHeap(arr, 0, i);
}
} // 建最大堆
private static void maxHeap(int[] arr, int index, int end) {
int q;
while (index < end) {
q = 2 * index + 1;
if (q >= end)
break;
if ((q < end - 1 && (arr[q + 1] > arr[q])))
q = q + 1;
// 如果某一节点的值小于其子节点的最大值，将其交换
if (arr[q] > arr[index]) {
arr[q] ^= arr[index];
arr[index] ^= arr[q];
arr[q] ^= arr[index];
index = q;
} else {
break;
}
}
}