堆排序(JAVA)
原理：
基本原理也是選擇排序，只是不在使用遍歷的方式查找無序區間的最大的數，而是通過堆來選擇無序區間的最大的數，
注意： 排升序要建大堆；排降序要建小堆，
性能分析：
時間復雜度：O( n * log (n) )
空間復雜度度：O(1)
穩定性：不穩定
實作：
public static void heapSort(int[] arr){
//1.先建立堆
createHeap(arr);
//2.需要回圈的取出堆頂元素，和最后一個元素交換位置并洗掉之
// 再從 0 位置進行調整
int heapSize = arr.length;
for(int i = 0; i < arr.length; i++){
//交換 0 號元素和堆的最后一個元素
swap(arr , 0 , heapSize - 1);
//把最后一個元素從堆上洗掉
heapSize--;
//從 0 號位置開始往下調整
shiftDown(arr,heapSize,0);
}
}
public static void createHeap(int[] arr){
for(int i = (arr.length - 1 - 1) / 2; i >= 0; i--){
shiftDown(arr,arr.length,i);
}
}
public static void shiftDown(int[] arr,int size, int index){
int parent = index;
int child = 2 * parent + 1;
while(child < size){
//先找出左右子樹比較大的
if(child + 1 < size && arr[child + 1] > arr[child]){
child = child + 1;
}
//再去比較 child 和 parent
if(arr[parent] < arr[child]){
swap(arr, parent , child);
}else{
break;
}
parent = child;
child = 2 * parent + 1;
}
}
public static void swap(int[] arr ,int x,int y){
int tmp = arr[x];
arr[x] = arr[y];
arr[y] = tmp;
}
實作main函式：
public static void main(String[] args) {
int[] arr = {1,3,5,7,2,9,6,3};
heapSort(arr);
System.out.println(Arrays.toString(arr));
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/275758.html
標籤：其他