Heap sorting: Using large root heaps
All arrays are entered into the heap, then the heap is released from the heap and inserted back into the array from back to front, and the array is ordered from small to large.
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 View the maximum root (only see it without deletion, compared with 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 Pop the maximum root (popup means deletion, compared with seekMax) */ public T popMax() { swap(1, size--); shiftDown(1); return data[size + 1]; } /** * @param child The lower corner mark of the child node is child, and the lower corner table of the parent node is 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 lower corner mark of an element in the data array* @param b The lower corner mark of an element in the data array* @return The lower corner mark of which element is large*/ private int max(int a, int b) { if (data[a].compareTo(data[b]) < 0) {//If data[b] big return b;//Return b } else {//If data[a] big return a;//Return a } } /** * @param a lower corner mark of an element in the data array* @param b lower corner mark of an element in the data array* @param c lower corner mark of an element in the data array* @return The lower corner mark of an element in the data array*/ private int max(int a, int b, int c) { int biggest = max(a, b); biggest = max(biggest, c); return bigger; } /** * @param father The lower corner mark of the parent node is father, and the lower corner tables of the left and right two child nodes are: father*2 and father*2+1 */ public void shiftDown(int father) { while (true) { int lchild = father * 2;//Left child int rchild = father * 2 + 1;//Right child int newFather = father;//NewFather is about to be updated. Who is the lower corner mark of the parent, left and right nodes? If (lchild > size) {//If the father node has neither left child nor right child return; } else if (rchild > size) {//If the father node has only left child, no right child newFather = max(father, lchild); } else {//If the father node has both left child and right child newFather = max(father, lchild, rchild); } if (newFather == father) {//It means that father is larger than both child nodes, and the table name is already a big root heap, so there is no need to continue to adjust the return; } else {// Otherwise, you need to continue to adjust the heap until the big root heap condition is met swap(father, newFather);//Value exchange father = newFather;//Update the value of father, which is equivalent to continuing to adjust shiftDown(newFather) } } } public static <T extends Comparable<? super T>> void sort(T[] arr) { int len = arr.length; //In-heap MaxHeap<T> maxHeap = new MaxHeap<T>(len); for (int i = 0; i < len; i++) { maxHeap.insert(arr[i]); } //Out-heap 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 }}Heap sorting: Construct the heap on the array (maximum heap)
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, array heap 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 lower corner mark of an element in the data array* @param b lower corner mark of an element in the data array* @return Return which element is larger, the lower corner mark of which element is larger*/ private int max(int a, int b) { if (data[a].compareTo(data[b]) < 0) {//If data[b] big return b;//Return b } else {//If data[a] big return a;//Return a } } /** * @param a lower corner mark of an element in the data array* @param b lower corner mark of an element in the data array* @param c The lower corner mark of an element in the data array* @return The lower corner mark of which element is larger*/ 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;//It doesn't matter whether the assignment is assigned here. If the following return is changed to break, it must be assigned if (lchild > size) {//If there is no left and right children return; } else if (rchild > size) {//If there is no right child newFather = max(father, lchild); } else {//If there is a left and right children newFather = max(father, lchild, rchild); } if (newFather == father) {//If the original parent node is the largest of three, you don't need to continue to sort out the pile return; } else {//The parent node is not the largest, swap the older children and continue to adjust the downwards until the large root heap is satisfied swap(newFather, father); father = newFather;//Equivalent to shiftDown(newFather). If newFather turns out to be the left child of father, it is equivalent to 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 }}The above heap sorting example (Java array implementation) is all the content I share with you. I hope you can give you a reference and I hope you can support Wulin.com more.