Skip to content

Instantly share code, notes, and snippets.

@swshan
Created June 20, 2017 09:22
Show Gist options
  • Save swshan/05854bba3c6719c4962e5722bc3a7bd8 to your computer and use it in GitHub Desktop.
Save swshan/05854bba3c6719c4962e5722bc3a7bd8 to your computer and use it in GitHub Desktop.
堆排序 摘自维基百科
package main;
import java.util.Arrays;
public class heapSort {
private int[] arr;
public HeapSort(int[] arr){
this.arr = arr;
}
public void sort() {
/*
* 第一步将数组堆化
*/
int len = arr.length - 1;
int beginIndex = (len - 1) >> 1;
for (int i = beginIndex; i>= 0; i--) {
maxHeapify(i, len);
}
for (int i = len; i > 0; i--) {
swap(0, i);
maxHeapify(0, i - 1);
}
}
private void swap(int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
private void maxHeapify(int index, int len) {
int li = (index << 1) + 1; //左子节点索引
int ri = li + 1; // 右子节点索引
int cMax = li; //子节点值最大索引
if (li > len) return;
if (ri <= len && arr[ri] > arr[li]) //先判断左右子节点 哪个较大
cMax = ri;
if (arr[cMax] > arr[index]) {
swap(cMax, index);
maxHeapify(cMax, len);
}
}
public static void main(String[] args) {
int[] arr = new int[]{3,5,3,0,8,6,1,5,8,6,2,4,9,4,7,0,1,8,9,7,3,1,2,5,9,7,4,0,2,6};
new HeapSort(arr).sort();
System.out.println(Arrays.toString(arr));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment