堆排序

堆排序通過使用給定數組的元素創建最小堆或最大堆來處理元素。 最小堆或最大堆表示數組的順序，其中根元素表示數組的最小或最大元素。 在每個步驟中，堆的根元素被刪除並存儲到已排序的數組中，堆將再次堆積。

堆排序基本上遞歸地執行兩個主要操作。

• 使用數組ARR的元素構建堆H。
• 重複刪除階段1中形成的堆的根元素。

複雜度

演算法

HEAP_SORT(ARR, N)

第1步 : [構建堆 H]
    重複 i=0 到 N-1
    CALL INSERT_HEAP(ARR, N, ARR[i])
    [結束迴圈]
第2步 : 反復刪除根元素

    當 N > 0 時，重複執行
    CALL Delete_Heap(ARR,N,VAL)
    SET N = N+1
    [結束迴圈]
第3步: 結束

使用C語言實現堆排序演算法，代碼哪下所示 -

#include<stdio.h>
int temp;

void heapify(int arr[], int size, int i)
{
    int largest = i;
    int left = 2*i + 1;
    int right = 2*i + 2;

    if (left < size && arr[left] >arr[largest])
        largest = left;

    if (right < size && arr[right] > arr[largest])
        largest = right;

    if (largest != i)
    {
        temp = arr[i];
        arr[i]= arr[largest];
        arr[largest] = temp;
        heapify(arr, size, largest);
    }
}

void heapSort(int arr[], int size)
{
    int i;
    for (i = size / 2 - 1; i >= 0; i--)
    heapify(arr, size, i);
    for (i=size-1; i>=0; i--)
    {
        temp = arr[0];
        arr[0]= arr[i];
        arr[i] = temp;
        heapify(arr, i, 0);
    }
}

void main()
{
    int arr[] = {1, 10, 2, 3, 4, 1, 2, 100,23, 2};
    int i;
    int size = sizeof(arr)/sizeof(arr[0]);

    heapSort(arr, size);

    printf("printing sorted elements\n");
    for (i=0; i<size; ++i)
        printf("%d\n",arr[i]);
}

執行上面示例代碼，得到以下結果：

printing sorted elements

1
1
2
2
2
3
4
10
23
100

使用C#語言實現堆排序代碼如下所示 -

using System;
public class HeapSorting {
static void heapify(int[] arr, int size, int i)
{
    int largest = i;
    int left = 2*i + 1;
    int right = 2*i + 2;
    int temp;
    if (left < size && arr[left] > arr[largest])
        largest = left;

    if (right < size && arr[right] > arr[largest])
        largest = right;

    if (largest != i)
    {
        temp = arr[i];
        arr[i]= arr[largest];
        arr[largest] = temp;
        heapify(arr, size, largest);
    }
}

static void heapSort(int[] arr, int size)
{
    int i;
    int temp;
    for (i = size / 2 - 1; i >= 0; i--)
    heapify(arr, size, i);
    for (i=size-1; i>=0; i--)
    {
        temp = arr[0];
        arr[0]= arr[i];
        arr[i] = temp;
        heapify(arr, i, 0);
    }
}

    public void Main()
    {
        int[] arr = {1, 10, 2, 3, 4, 1, 2, 100, 23, 2};
        int i;
        heapSort(arr, 10);
        Console.WriteLine("printing sorted elements");
        for (i=0; i<10; ++i)
            Console.WriteLine(arr[i]);
    }
}

執行上面示例代碼，得到以下結果：

printing sorted elements

1
1
2
2
2
3
4
10
23
100