堆排序：利用大根堆
數組全部入堆，再出堆從後向前插入回數組中，數組就從小到大有序了。
public class MaxHeap<T extends Comparable<? super T>> { private T[] data; private int size; private int capacity; public MaxHeap(int capacity) { this.data = (T[]) new Comparable[capacity + 1]; size = 0; this.capacity = capacity; } public int size() { return this.size; } public boolean isEmpty() { return size == 0; } public int getCapacity() { return this.capacity; } /** * @return 查看最大根(只看不刪, 與popMax對比) */ public T seekMax() { return data[1]; } public void swap(int i, int j) { if (i != j) { T temp = data[i]; data[i] = data[j]; data[j] = temp; } } public void insert(T item) { size++; data[size] = item; shiftUp(size); } /** * @return 彈出最大根(彈出意味著刪除, 與seekMax對比) */ public T popMax() { swap(1, size--); shiftDown(1); return data[size + 1]; } /** * @param child 孩子節點下角標是child，父節點下角表是child/2 */ public void shiftUp(int child) { while (child > 1 && data[child].compareTo(data[child / 2]) > 0) { swap(child, child / 2); child = child / 2; } } /** * @param a data數組中某個元素的下角標* @param b data數組中某個元素的下角標* @return 哪個元素大就返回哪個的下角標*/ private int max(int a, int b) { if (data[a].compareTo(data[b]) < 0) {//如果data[b]大return b;//返回b } else {//如果data[a]大return a;//返回a } } /** * @param a data數組中某個元素的下角標* @param b data數組中某個元素的下角標* @param c data數組中某個元素的下角標* @return 哪個元素大就返回哪個的下角標*/ private int max(int a, int b, int c) { int biggest = max(a, b); biggest = max(biggest, c); return biggest; } /** * @param father 父節點下角標是father,左右兩個孩子節點的下角表分別是：father*2 和father*2+1 */ public void shiftDown(int father) { while (true) { int lchild = father * 2;//左孩子int rchild = father * 2 + 1;//右孩子int newFather = father;//newFather即將更新，父、左、右三個結點誰大，newFather就是誰的下角標if (lchild > size) {//如果該father結點既沒有左孩子，也沒有右孩子return; } else if (rchild > size) {//如果該father結點只有左孩子，沒有右孩子newFather = max(father, lchild); } else {//如果該father結點既有左孩子，又有右孩子newFather = max(father, lchild, rchild); } if (newFather == father) {//說明father比兩個子結點都要大，表名已經是大根堆，不用繼續調整了return; } else {//否則，還需要繼續調整堆，直到滿足大根堆條件為止swap(father, newFather);//值進行交換father = newFather;//更新father的值，相當於繼續調整shiftDown(newFather) } } } public static <T extends Comparable<? super T>> void sort(T[] arr) { int len = arr.length; //入堆MaxHeap<T> maxHeap = new MaxHeap<T>(len); for (int i = 0; i < len; i++) { maxHeap.insert(arr[i]); } //出堆for (int i = len - 1; i >= 0; i--) { arr[i] = maxHeap.popMax(); } } public static void printArr(Object[] arr) { for (Object o : arr) { System.out.print(o); System.out.print("/t"); } System.out.println(); } public static void main(String args[]) { Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6}; printArr(arr);//3 5 1 7 2 9 8 0 4 6 sort(arr); printArr(arr);//0 1 2 3 4 5 6 7 8 9 }}堆排序：對數組進行構造堆(最大堆)
public class MaxHeap<T extends Comparable<? super T>> { private T[] data; private int size; private int capacity; public MaxHeap(int capacity) { this.capacity = capacity; this.size = 0; this.data = (T[]) new Comparable[capacity + 1]; } public MaxHeap(T[] arr) {//heapify,數組建堆capacity = arr.length; data = (T[]) new Comparable[capacity + 1]; System.arraycopy(arr, 0, data, 1, arr.length); size = arr.length; for (int i = size / 2; i >= 1; i--) { shiftDown(i); } } public int size() { return this.size; } public int getCapacity() { return this.capacity; } public boolean isEmpty() { return size == 0; } public T seekMax() { return data[1]; } public void swap(int i, int j) { if (i != j) { T temp = data[i]; data[i] = data[j]; data[j] = temp; } } public void insert(T item) { size++; data[size] = item; shiftUp(size); } public T popMax() { swap(1, size--); shiftDown(1); return data[size + 1]; } public void shiftUp(int child) { while (child > 1 && data[child].compareTo(data[child / 2]) > 0) { swap(child, child / 2); child /= 2; } } /** * @param a data數組中某個元素的下角標* @param b data數組中某個元素的下角標* @return 哪個元素大就返回哪個的下角標*/ private int max(int a, int b) { if (data[a].compareTo(data[b]) < 0) {//如果data[b]大return b;//返回b } else {//如果data[a]大return a;//返回a } } /** * @param a data數組中某個元素的下角標* @param b data數組中某個元素的下角標* @param c data數組中某個元素的下角標* @return 哪個元素大就返回哪個的下角標*/ private int max(int a, int b, int c) { int biggest = max(a, b); biggest = max(biggest, c); return biggest; } public void shiftDown(int father) { while (true) { int lchild = father * 2; int rchild = father * 2 + 1; int newFather = father;//這裡賦不賦值無所謂，如果把下面這個return改成break,那就必須賦值了if (lchild > size) {//如果沒有左、右孩子return; } else if (rchild > size) {//如果沒有右孩子newFather = max(father, lchild); } else {//如果有左、右孩子newFather = max(father, lchild, rchild); } if (newFather == father) {//如果原父結點就是三者最大，則不用繼續整理堆了return; } else {//父節點不是最大，則把大的孩子交換上來，然後繼續往下堆調整，直到滿足大根堆為止swap(newFather, father); father = newFather;//相當於繼續shiftDown(newFather)。假如newFather原來是father的左孩子，那就相當於shiftDown(2*father) } } } public static <T extends Comparable<? super T>> void sort(T[] arr) { int len = arr.length; MaxHeap<T> maxHeap = new MaxHeap<>(arr); for (int i = len - 1; i >= 0; i--) { arr[i] = maxHeap.popMax(); } } public static void printArr(Object[] arr) { for (Object o : arr) { System.out.print(o); System.out.print("/t"); } System.out.println(); } public static void main(String args[]) { Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6}; printArr(arr);//3 5 1 7 2 9 8 0 4 6 sort(arr); printArr(arr);//0 1 2 3 4 5 6 7 8 9 }}以上這篇堆排序實例(Java數組實現)就是小編分享給大家的全部內容了，希望能給大家一個參考，也希望大家多多支持武林網。