[数据结构与算法]java堆排序算法

java堆排序算法

排序思想
1.首先将待排序的数组构造成一个大根堆，此时，整个数组的最大值就是堆结构的顶端

2.将顶端的数与末尾的数交换，此时，末尾的数为最大值，剩余待排序数组个数为n-1

3.将剩余的n-1个数再构造成大根堆，再将顶端数与n-1位置的数交换，如此反复执行，便能得到有序数组

• 注意:
  • 升序用大根堆，降序就用小根堆(默认为升序)
  • 堆排序是不稳定的排序，空间复杂度为O(1),平均的时间复杂度为O(nlogn),最坏情况下也稳定在O(nlogn)

代码示例:

public class HeapSort {
	public static void main(String[] args) {
		int arr[] = { 555, -3, 7, 62, 54, 10, 86, 2, 5, -6, 9, 24 };
		System.out.println("排序前" + Arrays.toString(arr));
		heapSort(arr);
		System.out.println("排序后" + Arrays.toString(arr));
	}

	public static void heapSort(int array[]) {
		// 构建一个大顶堆，从array.length/2 - 1 最后一个非叶子结点开始
		for (int i = array.length / 2 - 1; i >= 0; i--) {
			adjustHeap(array, i, array.length);
		}
		for (int len = array.length - 1; len > 0; len--) {
			// 大顶堆的根元素与数组末尾元素交换
			int temp = array[0];
			array[0] = array[len];
			array[len] = temp;

			// 交换后的末尾元素忽略(len--) 不再参与堆结构的调整
			// 重新调整堆结构
			adjustHeap(array, 0, len);
		}
	}

	/**
	 * 完成将以i对应的非叶子结点的树调整成大顶堆
	 */
	public static void adjustHeap(int[] array, int i, int length) {
		// 先把当前元素取出来，因为当前元素可能要一直移动
		int temp = array[i];
		// 2*i+1表示结点i的左子树
		for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {
			if (k + 1 < length && array[k] < array[k + 1]) {
				k++;// 让k先指向子节点中最大的节点
			}
			if (array[k] > temp) {// 如果发现结点(左右子结点)大于根结点，则进行值的交换
				array[i] = array[k];// 把较大的值赋值给父节点
				// array[k] = temp; // 这里没必要换
				i = k;// 子结点更换了，以子结点为根的子树会受到影响，指针移向子节点，循环对子结点所在的树继续进行判断
			} else {
				break;// 不用交换，直接终止循环
			}
		}
		array[i] = temp;// 将temp值放到最终的位置
	}

}

参考：

• 堆排序（超详细图解 java版）
  https://blog.csdn.net/Javascript_tsj/article/details/124051388
• 堆排序_百度百科
  https://baike.baidu.com/item/%E5%A0%86%E6%8E%92%E5%BA%8F/2840151
• java实现10种排序算法
  https://blog.csdn.net/weixin_44531966/article/details/116464294
• 十大经典排序算法总结
  https://blog.csdn.net/meibenxiang/article/details/92796909
• 堆排序及复杂度分析
  https://blog.csdn.net/qq_23936173/article/details/87611687