堆排序
将待排序序列构造成一个大顶堆,此时,整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换,此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆,这样会得到n个元素的次小值。如此反复执行,便得到一个有序序列。
public void sort(int[] arr) { int n = (arr.length - 1) / 2; for (int i = n; i >= 0; i--) { maxHeap(arr, i, arr.length - 1); } for (int i = arr.length - 1; i >= 0; i--) { //swap(arr, 0, i); int tmp = arr[0]; arr[0]=arr[i]; arr[i]=tmp; maxHeap(arr, 0, i); } } private void maxHeap(int[] arr, int i, int count) { int j = 2 * i + 1; int tmp = arr[i]; while (j < count) { if (j + 1 < count && arr[j] < arr[j + 1]) { j++; } if (arr[j] <= tmp) { break; } arr[i] = arr[j]; i = j; j = 2 * i + 1; } arr[i] = tmp; }