堆排序的思想就是, 构造一个大顶堆或者小顶堆, 然后把堆顶元素换到末尾, 调整堆, 重复. 把过程分解为两步, 第一步: 建堆. 第二步: 排序.
大顶堆对应升序; 小顶堆为降序.
代码如下:
- package heap;
- /*
- * 堆排序
- */
- import java.util.Arrays;
- public class HeapSort {
- public static void main(String[] args) {
- int[] arr = { 5, 7, 3, 4, 8, 9, 7, 6, 1 };
- heapSort(arr);
- System.out.println(Arrays.toString(arr));
- }
- private static void heapSort(int[] arr) {
- // 第一步 构造一个 堆
- for (int i = arr.length / 2 - 1; i>= 0; i--) {//arr.length/2-1 取最后一个非叶子结点
- // maxHeapify(arr, i, arr.length);// 大顶堆
- minheapifly2(arr, i, arr.length);// 小顶堆
- }
- // 第二步 排序 把最大的和末尾互换, 然后重建最大堆
- for (int i = arr.length-1; i>= 0; i--) {
- int temp = arr[0];
- arr[0] = arr[i];
- arr[i] = temp;
- minheapifly2(arr, 0, i);// 每次要调整的堆从根开始, 长度在递减
- }
- }
- /**
- *
- * @param arr 堆
- * @param i i 代表要调整的结点
- * @param length 堆长
- */
- // 关键环节 建堆 大堆
- private static void maxHeapify(int[] arr, int i, int length) {
- if (i>= length) {
- return;
- }
- int c1 = 2 * i + 1;// 左子树
- int c2 = 2 * i + 2;// 右子树
- int max = i;// 存最大值的索引
- if (c1 <length && arr[c1]> arr[max]) {
- max = c1;
- }
- if (c2 <length && arr[c2]> arr[max]) {
- max = c2;
- }
- if (max != i) {// 说明 max 的值有变动, 存在比根结点大的子树
- int temp = arr[i];
- arr[i] = arr[max];
- arr[max] = temp;
- maxHeapify(arr, max, length);// 关键的关键: 在本课树完成建堆以后, 对影响的子树进行调整 [防止本树合理后, 子树 bei 破坏] ,
- }
- }
- private static void minHeapifly(int[] arr, int i, int len) {
- if (i>= len) {// 设置递归出口
- return;
- }
- int c1 = 2 * i + 1;
- int c2 = 2 * i + 2;
- int min = i;// 先把索引 i 指向的元素值当作最小
- if (c1 <len && arr[c1] < arr[min]) {
- min = c1;
- }
- if (c2 < len && arr[c2] < arr[min]) {// 此时的 min 可能是 i, 也可能是 c1
- min = c2;
- }
- if (min != i) {
- // 把最小的交换到父节点
- int temp = arr[i];
- arr[i] = arr[min];
- arr[min] = temp;
- // 对受此次交换影响的子树, 重新建堆
- minHeapifly(arr, min, len);
- }
- }
- private static void minheapifly2(int[] arr, int i, int len) {
- if (i>= len) {// 设置递归出口
- return;
- }
- int c1 = 2 * i + 1;
- int c2 = 2 * i + 2;
- int min = i;// 先把索引 i 指向的元素值当作最小
- if (c1 <len) {
- if (arr[c1] < arr[c2]) {
- min = c1;
- } else {
- min = c2;
- }
- if (arr[min]> arr[i]) {
- min = i;
- }
- }
- if (min != i) {
- // 把最小的交换到父节点
- int temp = arr[i];
- arr[i] = arr[min];
- arr[min] = temp;
- // 对受此次交换影响的子树, 重新建堆
- minheapifly2(arr, min, len);
- }
- }
- }
堆排序
来源: http://www.bubuko.com/infodetail-3348790.html