堆排序(java)
介绍
- 建立大顶堆
- 然后将堆的根节点取出(一般是与最后一个节点进行交换)
- 再将前length-1个数组重新建立大顶堆。不断重复
构建大顶堆图解
图是我用word画的,画的不好见谅
1.首先得到一个完全二叉树
2.选中第i/2个数
3.把此数与两个孩子作对比并将最大的数字放在此位置
4.然后不断向前寻找直到顶部
将根节点取出与最后一个数交换
最后将前length-1个数重新构建大顶堆不断循环
代码
/*** * 堆排序O(n*lgn) * @param data * @param i * @param j */ public static void swap(int[] data, int i, int j) { if (i == j) { return; } data[i] = data[i] + data[j]; data[j] = data[i] - data[j]; data[i] = data[i] - data[j]; } public int[] heapSort(int[] data) { for (int i = 0; i < data.length; i++) { createMaxdHeap(data, data.length - 1 - i); swap(data, 0, data.length - 1 - i); // print(data); } return data; } public static void createMaxdHeap(int[] data, int lastIndex) { for (int i = (lastIndex - 1) / 2; i >= 0; i--) { // 保存当前正在判断的节点 int k = i; // 若当前节点的子节点存在 while (2 * k + 1 <= lastIndex) { // biggerIndex总是记录较大节点的值,先赋值为当前判断节点的左子节点 int biggerIndex = 2 * k + 1; if (biggerIndex < lastIndex) { // 若右子节点存在,如果不存在此时biggerIndex应该等于 lastIndex if (data[biggerIndex] < data[biggerIndex + 1]) { // 若右子节点值比左子节点值大,则biggerIndex记录的是右子节点的值 biggerIndex++; } } if (data[k] < data[biggerIndex]) { // 若当前节点值比子节点最大值小,则交换2者得值,交换后将biggerIndex值赋值给k swap(data, k, biggerIndex); k = biggerIndex; } else { break; } } } }