一.堆排序的基本介绍 1.堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度都为O(nlogn)，同时是一种不稳定的排序。 2.堆是具有以下性质的完全二叉树：每个节点的值都是大于或等于其左右孩子结点的值，称为大顶堆，没有要求结点的左孩子的值和右孩子的值的大小关系。每个节点的值都是小于或等于其左右孩子结点的值，称为小顶堆。 3.一般升序采用大顶堆，降序采用小顶堆。
二.堆排序的基本思想（大顶堆为例） 1.将待排序的序列构建成一个大顶堆，此时整个序列的最大值就是根节点 2.将其与末尾元素进行交换，此时末尾就是最大值 3.然后将剩余的n-1个元素重新构成一个堆，这样就会得到n个元素的次小值。反复执行就能得到一个有序序列。
三.代码实现 第一步：先实现一个将数组（二叉树）调整成一个大顶堆的函数
//将一个数组（二叉树）调整成一个大顶堆 /* * 功能：完成将以i对应的非叶子结点的树调整成大顶堆 * i 表示非叶子结点在数组中索引 * length 表示对多少个元素继续调整，length是在逐渐的减少 * */ public static void adjustHeap(int arr[],int i ,int length){ int temp = arr[i]; //先取出当前元素的值，保存在临时标量 //开始调整 //说明 //1.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; //i指向k，继续循环比较 }else { break; } } //当for循环结束后，我们已经将以i为父节点的树的最大值，放在了最顶（局部） arr[i]=temp; //将temp值放在调整后的位置 }第二步：完成堆排序的三个步骤
public static void heapSort(int arr[]){ int temp = 0; System.out.println("堆排序！！"); //分步完成 // adjustHeap(arr, 1, arr.length); // System.out.println("第一次"+ Arrays.toString(arr)); // // adjustHeap(arr, 0, arr.length); // System.out.println("第二次"+ Arrays.toString(arr)); //最终代码 //1.将无序序列构建成一个堆，根据升序降序的需求选择大顶堆或者小顶堆 for (int i = arr.length/2-1; i >=0 ; i--) { adjustHeap(arr,i,arr.length); } System.out.println(Arrays.toString(arr)); /* * 2.将堆顶元素与末尾元素交换，将最大元素“沉”到数组末端； * 3.重新调整结构。使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整＋交换步骤，直到整个序列有序 * */ for (int j = arr.length-1; j > 0 ; j--) { //交换 temp = arr[j]; arr[j] = arr[0]; arr[0] = temp; adjustHeap(arr,0,j); System.out.println(Arrays.toString(arr)); } }