1. Heap Sort

Heapsort refers to a sort algorithm designed by using heap data structure. Heap is a nearly complete binary tree structure, and also satisfies the property of heap: that is, the key value or index of the child node is always smaller (or larger) than its parent node.

1.1 Algorithm Description

  • The initial sequence of keywords to be sorted (R1,R2… .rn) is constructed into the big top heap, which is the initial unordered region;
  • By exchanging the top element R[1] with the last element R[n], a new unordered region (R1,R2… Rn-1) and a new ordered region (Rn), and R[1,2… n-1]<=R[n];
  • Since the new heap top R[1] after the swap may violate the heap properties, it is necessary to apply the current unordered region (R1,R2… Rn-1) adjusts to the new heap, and then swaps R[1] again with the last element of the unordered region to obtain the new unordered region (R1,R2… .Rn-2) and the new ordered region (Rn-1,Rn). This process is repeated until the number of elements in the ordered region is N-1, and the whole sorting process is complete.

1.2 GIF demonstration

1.3 Code Implementation

/// <summary>
///Heap sort
/// </summary>
public class Program {

    public static void Main(string[] args) {
        int[] array = { 43.69.11.72.28.21.56.80.48.94.32.8 };

        HeapSort(array);
        ShowSord(array);

        Console.ReadKey();
    }

    private static void ShowSord(int[] array) {
        foreach (var num in array) {
            Console.Write($"{num} ");
        }
        Console.WriteLine();
    }

    private static void HeapSort(int[] array) {
        MaxHeap(array);
        for (int i = array.Length - 1; i > 0; i--) {
            Swap(ref array[0].ref array[i]);
            Heapify(array, 0, i); }}private static void MaxHeap(int[] array) {
        for (int i = array.Length / 2 - 1; i >= 0; i--) { Heapify(array, i, array.Length); }}private static void Heapify(int[] array, int index, int size) {
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        int large = index;

        if (left < size && array[left] > array[large]) {
            large = left;
        }
        if (right < size && array[right] > array[large]) {
            large = right;
        }
        if(index ! = large) { Swap(ref array[index], refarray[large]); Heapify(array, large, size); }}private static void Swap(ref int first, ref int second) {
        intt = first; first = second; second = t; }}Copy the code

The time complexity of heapsort algorithm is easily proved as O(n*logn).