排序算法（堆排序的实现和时间复杂度分析）排序算法：堆排序的实现和时

前置知识堆排序是将数组看成了一个二叉树，并且是一个完全二叉树，再进行排序
【排序算法（堆排序的实现和时间复杂度分析）】所以得知道完全二叉树的一些性质：设完全二叉树的层次为k，完全二叉树的节点数量在两种情况之间

节点数量最大为2k - 1，最后一层的节点是满的，有2k-1个节点
节点数量最小为2k-1，最后一层只有一个节点

除了最后一层外，第i层的节点数量永远是2i-1个。
以数组的下标当做节点的序号，即下标为i的元素对应二叉树的第i-1个节点，左右两个孩子的下标分别是(2*i+1)和（2*i+2）

数组下标从1开始的话，下标i对应第i个节点,并且左右孩子的下标是2*i和2*i+1

设计思路对于一个无序的完全二叉树，排序的思路是先得到最小的元素a，再将a从二叉树删除，再得到二叉树的最小元素b，依次得到有序的所有元素
首先，需要进行建成一个最小堆（最大堆）：从最后一个父节点（非叶子节点）开始，下沉所有父节点

最大堆：所有父节点的值比左右孩子大
最小堆：所有父节点的值比左右孩子小
下沉：父节点的值a，与左右孩子的值进行比较，不满足堆的定义就交换，交换后值为a的节点（不为叶子节点的话）作为父节点继续下沉，与它的孩子节点交换

遍历数组，所有父节点下沉完毕，第一个元素（堆顶节点）node1就是数组的最小（大）值
要得到所有排好序的元素，需要将元素一个个取出。首先取出node1：与堆的最后一个节点node2交换位置，然后从堆中删除node1

为了保持完全二叉树的性质，所以将元素放到最后一个节点再删除
删除不是从数组中删除，只是不将它看做二叉树的一部分

删除node1后，node2就是第一个节点，然后将node2下沉，因为当前只有node2节点不满足堆的定义，下沉后又恢复成堆，又可以取出第一个节点
从堆中不断取出第一个节点，一直到堆为空，陆续取出的节点便是排好序的数组
代码实现通过构建大根堆，再不断取出堆顶节点到数组尾部，实现从小到大的排序
父节点下沉的方式有循环和递归两种，在循环下沉中没有交换，而是使用了单向赋值，有一定的优化效果

import java.util.Arrays; import java.util.Random; public class HeadSort {public static void main(String[] args) { //测试代码 int[] arr = new int[20]; for (int i = 0; i < arr.length; i++) { arr[i] = new Random().nextInt() % 1000; } System.out.println(Arrays.toString(arr)); heapSort(arr); System.out.println(Arrays.toString(arr)); }public static int[] heapSort(int[] arr) {// 构建最大堆 buildHead(arr); // 每次将堆顶节点移到数组尾部，调整堆大小 for (int i = 0; i < arr.length; i++) {// 即将要被堆删除的节点序号 int last = arr.length - i - 1; swap(arr, 0, last); // 改变传递的len参数表示堆将节点删除 heapify1(arr, 0, last); } return arr; }public static void buildHead(int[] arr) { int len = arr.length; //在满二叉树中，叶子节点数量是非叶子节点的2倍+1 //第n-1层的最后一个节点就是len/2 for (int i = len / 2; i >= 0; i--) { heapify1(arr, i, len); } }//递归下沉方式 public static void heapify1(int[] arr, int parentIndex, int len) { // 左右孩子节点 int left = 2 * parentIndex + 1; int right = 2 * parentIndex + 2; // 该父节点没有左孩子 if (left >= len) { return; } int latest = left; /* 将节点进行下沉，如果进行了交换，还得继续下沉，一直到成为叶子节点 */ // 得出左右孩子中的最大值 if (right < len && arr[right] > arr[left]) { latest = right; } if (arr[latest] > arr[parentIndex]) { swap(arr, parentIndex, latest); heapify1(arr, latest, len); } }//循环下沉方式 public static void heapify2(int[] arr, int parentIndex, int len) {//先将父节点值保存下来，跟左右的孩子比较，如果大于，跳出循环，如果小于，进行交换 //交换之后节点继续下沉，一直到成为叶子节点 int tmp = arr[parentIndex]; int children = 2 * parentIndex + 1; while (children < len) {// 左孩子大于右孩子，用左孩子的值与父节点比较 if (children + 1 < len && arr[children + 1] > arr[children]) { children++; }/* 父节点大于孩子的值，不用交换使用的是tmp，而不是arr[parentIndex]，因为一直是单向赋值，没有交换直到确认tmp属于哪个节点，在循环外面将tmp赋值 */ if (tmp >= arr[children]) { break; }// 将孩子节点的值赋给父节点，孩子节点暂时不变 arr[parentIndex] = arr[children]; parentIndex = children; children = children * 2 + 1; } arr[parentIndex] = tmp; }private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } }

复杂度的计算设数组为满二叉树来计算复杂度：树有n个节点、有k层，满二叉树的定义有：2k-1 = n , k = log2(n+1)
第一阶段：构建堆，下沉所有父节点
首先在构建堆时，需要进行节点的下沉，计算最多下沉次数的时间
第k层的2^(k-1)个节点都是叶子节点，下沉0次
第k-1层的2^(k-2)个节点，下沉1次
。。。。。。
第2层的有2个节点，下沉k-2次
第1层的只有1个节点，下沉k-1次
总共下沉的时间复杂度为：s = 2^(k-2) * 1 + 2^(k-3) * 2 + ...+ 2^(1)*(k-2) + 2^(0)*(k-1)
然后使用神奇的数学知识算出这个s
首先2s = 2^(k-1)*1 + 2^(k-2) * 2 + 2^(k-3) * 3 +.... + 2^(2)*(k-2) + 2^(1)*(k-1)
刚才的s =2^(k-2) * 1 + 2^(k-3) * 2 + ... + 2^(2)*(k-3) + 2^(1)*(k-2) + 2^(0)*(k-1)
然后2s - s = 2^(k-1) + 2^(k-2) + ... 2^(2) + 2^(1) - 2^(0)*(k-1)= s
可以看出除了最后一项2^(0)*(k-1)外，前面k-1项一个以2位公比，2为首项的等比数列
使用等比数列求和公式：a1(1-q^n)/(1-q) ，得出 s = 2^(k) - 2 - 1*(k-1)=2^(k) - k - 1
又由上面的 2^(k) - 1 = n ， k = log2(n+1) 得出时间复杂度与数组长度n的关系：
s = n - log2(n+1)也就是 O(n)复杂度
第二阶段：陆续取出第一个元素，下沉新的堆顶节点
简单的看：
有n个节点需要取出，每次取出后新节点下沉 log2(n+1)，时间复杂度为O(nlogn)
复杂的看：
二叉树每次取出一个节点后，n减1，层次k可能会变化，第i个节点下沉的次数是 log2(n-i+1)
第一个元素下沉log2(n)次，最后一个元素下沉0次，需要下沉的元素有n-1个
得到总时间为：log2(n) + log2(n-1) + .... + log2(2) = log2(n!)
太复杂了感觉，就约等于O(nlogn)吧
所以总的时间复杂度为O(n) + O(nlogn) = O（nlogn）
循环下沉方式，空间复杂度为O(1）
使用递归下沉的话，每下沉一次都会调用一次函数，空间复杂度应该与时间复杂度一样。