本文共 1283 字，大约阅读时间需要 4 分钟。

➢ 基本介绍

1. 堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为0(n log n),它也是不稳定排序。
2. 堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆，注意:没有要求结点的左孩子的值和右孩子的值的大小关系。
3. 每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆
4. 大顶堆举例说明
   
   大顶堆特点: arr[i]>=arr[2*i+1] && arr[i] >=arr[2*i+2] //i对应第几个节点，i从开始编号
   反之小顶锥就是小于。

➢ 基本思想

1. 将待排序序列构造成一个大顶堆。
2. 此时，整个序列的最大值就是堆项的根节点。
3. 将其与末尾元素进行交换，此时末尾就为最大值。
4. 然后将剩余n-1个元素重新构造成一个堆， 这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。
   

➢代码实现

1. 构建大顶锥

// 构建大顶锥 i:索引 length：多少元素需要调整，length--	public static void BigHeap(int[] arr, int i, int length) {
   		int temp = arr[i];		// 调整位置		// k = i * 2 + 1 k是i的左子节点		for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
   			if (k + 1 < length && arr[k] < arr[k + 1]) {
    // 左子节点的值小于右子节点的值				k++;			}			if (arr[k] > temp) {
    // 子节点大于父节点进行交换				arr[i] = arr[k];				i = k;			} else {
   				break;			}		}		arr[i] = temp;	}

详情见下图：

public static void heap(int[] arr) {
   		int temp = 0;		for (int i = arr.length / 2 - 1; i >= 0; i--) {
   			BigHeap(arr, i, arr.length);		}		for (int j = arr.length - 1; j > 0; j--) {
   			temp = arr[j];			arr[j] = arr[0];			arr[0] = temp;			BigHeap(arr, 0, j);		}	}

在main函数当中进行测试：

int arr[] = {
    4, 8, 9, 6, 2, 18, 51, 0, -4, 95, -78 };		heap(arr);		System.out.println(Arrays.toString(arr));

很显然：

转载地址：http://dgmzi.baihongyu.com/