排序之堆排序

堆排序是树结构的一个实际应用

package tree;

import java.util.Arrays;

public class HeapSort {
	public static void main(String[] args) {
		// 数组升序排序
		int[] arr = {4,6,8,5,9};
		heapSort(arr);
	}
	// 编写一个堆排序的方法
	public static void heapSort(int arr[]){
		int temp=0;
		System.out.println("堆排序");

		
		for (int i=arr.length/2-1;i>=0;i--){
			adjustHeap(arr,i,arr.length);
		}
		System.out.println(Arrays.toString(arr));
		System.out.println("");
		// 将根节点(最大的数) 放到数组的最后位置 然后 将该数以前的数组再次构建成大顶锥 再交换 .... 再.. 在交换

		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));
	}



	
	public static void adjustHeap(int arr[], int i, int length){
		int temp = arr[i]; //先取出当前元素的值, 保存在临时变量
		// 开始调整
		// k = i * 2 + 1 指向 i的左子几节点 下一个  k = k * 2 +1 指向当前节点的左子节点(i的左子节点的下一个左子节点)
		for(int k = i * 2 + 1;k < length;k =k * 2 +1){
			if (k + 1 < length && arr[k] < arr[k + 1]){ // 说明左子节点的值 小于右子节点的值
				k++; // k指向右子节点
			}
			if (arr[k] > temp){ // 如果子节点大于父节点
				arr[i] = arr[k];
				i = k; // 把较大的值 付给当前节点 然后 i指向k 继续循环比较
			}else {
				break;
			}
		}
		//for循环结束后 将 以 i 为父节点的树 的最大值 放到了最顶上(局部)
		arr[i] = temp; // 将temp放在调整后的位置
	}
}

public static void main(String[] args) {
		// 数组升序排序

		int arr[]=new int[8000000];
		for (int i=0;i<8000000;i++){
			arr[i]=(int) (Math.random()*8000000);
		}
		Date date1 = new Date();
		SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
		String date1Str = simpleDateFormat.format(date1);
		System.out.println("排序前的时间是="+date1Str);
		//测试插入排序的性能
		heapSort(arr);
		Date date2 = new Date();
		String date2Str = simpleDateFormat.format(date2);
		System.out.println("排序后的时间是="+date2Str);


	}

输出：

 时间复杂度：O（nlogn）