Algorithm - Heap Sort（Java）

短命女 2022-05-23 03:44 82阅读 0赞

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请点击[http://www.captainbed.net][http_www.captainbed.net]

package peace.learn.java.algorithm.sort;
 
 import java.util.Arrays;
 
 /**
 * @author Peace
 * 
 * Introduction:
 * Heap Sort is a kind of selection sort.
 * 
 * Basic Thought:
 * The trait of Heap Sort is:
 * In the sorting process,
 * treat the to-be-ordered sequence as the sequential storage structure
 * of a complete binary tree.
 * Take advantage of the inner relationships
 * of parent nodes and child nodes in the complete binary tree,
 * select the biggest (or smallest) record
 * from the current unordered sequence.
 * 
 * Algorithm:
 * 1. Adjust the to-be-ordered sequence to max root heap.
 * The top element is the biggest element in the max root heap.
 * 2. Swap the max root heap top element
 * with the last element of the unordered sequence,
 * and enlist the last position of unordered sequence
 * into the ordered sequence,
 * and then adjust the new unordered sequence to max root heap.
 * 3. Repeat the process until unordered sequence disappears.
 * 
 * Note:
 * At the beginning, all the sequence are unordered.
 * Every swapping, is swapping
 * the top element of max root heap into ordered sequence,
 * to guarantee the ordered sequence is ordered.
 * 
 * Complexity:
 * The time complexity of Heap Sort is O(nlog2n).
 */
 public class HeapSort {
 
 /**
 * Heap Sort
 *
 * @param a The array to be sorted
 */
 public static void heapSort(int[] a) {
 
 // Build max heap
 buildMaxHeap(a);
 
 // Print max heap
 System.out.println("Build max heap:");
 System.out.println(Arrays.toString(a));
 
 System.out.println("Each round of heap sorting:");
 for (int i = a.length - 1; i > 0; i--) {
 
 // Swap the max root heap top element with the last element of the unordered sequence
 int t = a[0];
 a[0] = a[i];
 a[i] = t;
 
 // Adjust the new unordered sequence to max root heap
 maxHeaping(a, 0, i);
 
 // Print max root heap after each sorting
 System.out.println(Arrays.toString(a));
 }
 }
 
 /**
 * Build max heap from bottom to top
 * 
 * By the characteristic of complete binary tree,
 * the child node's subscript starts from index = a.length / 2,
 * so adjust max heap from subscript = (a.length / 2) - 1.
 *
 * @param a The array to be sorted
 */
 private static void buildMaxHeap(int[] a) {
 for (int i = (a.length >>> 1) - 1; i >= 0; i--) {
 maxHeaping(a, i, a.length);
 }
 }
 
 /**
 * Adjust the specified node to heap
 *
 * @param a The array to be sorted
 * @param i The subscript of the specified node
 * @param heapSize The heap size, also the length of unordered sequence.
 */
 private static void maxHeaping(int[] a, int i, int heapSize) {
 
 // Left child node
 int left = (2 * i) + 1;
 
 // Right child node
 int right = 2 * (i + 1);
 
 // Temp variable, stores the large node.
 int large = i;
 
 // Comparing left child node
 if (left < heapSize && a[left] > a[large]) {
 large = left;
 }
 
 // Comparing right child node
 if (right < heapSize && a[right] > a[large]) {
 large = right;
 }
 
 // Swapping if child node is bigger than self, to make bigger element move upward.
 // And make the bigger element adjusted as heap to keep heap nature.
 if (large != i) {
 int t = a[i];
 a[i] = a[large];
 a[large] = t;
 
 maxHeaping(a, large, heapSize);
 }
 }
 
 /**
 * Test program
 *
 * @param args The arguments
 */
 public static void main(String[] args) {
 int[] arr = {11, 16, 22, -3, 99, 0, 16, 6, -1, 99};
 
 System.out.println("Before heap sort:");
 System.out.println(Arrays.toString(arr));
 
 System.out.println("In heap sort:");
 HeapSort.heapSort(arr);
 
 System.out.println("After heap sort:");
 System.out.println(Arrays.toString(arr));
 }
 
 }
 
 /* ------ Running Result ------
 Before heap sort:
 [11, 16, 22, -3, 99, 0, 16, 6, -1, 99]
 In heap sort:
 Build max heap:
 [99, 99, 22, 6, 16, 0, 16, -3, -1, 11]
 Each round of heap sorting:
 [99, 16, 22, 6, 11, 0, 16, -3, -1, 99]
 [22, 16, 16, 6, 11, 0, -1, -3, 99, 99]
 [16, 11, 16, 6, -3, 0, -1, 22, 99, 99]
 [16, 11, 0, 6, -3, -1, 16, 22, 99, 99]
 [11, 6, 0, -1, -3, 16, 16, 22, 99, 99]
 [6, -1, 0, -3, 11, 16, 16, 22, 99, 99]
 [0, -1, -3, 6, 11, 16, 16, 22, 99, 99]
 [-1, -3, 0, 6, 11, 16, 16, 22, 99, 99]
 [-3, -1, 0, 6, 11, 16, 16, 22, 99, 99]
 After heap sort:
 [-3, -1, 0, 6, 11, 16, 16, 22, 99, 99]
 */

[http_www.captainbed.net]: http://www.captainbed.net/troubleshooter