How to write a heap sort algorithm using C#

How to use C# to write a heap sort algorithm

Heap Sort (Heap Sort) is a sorting algorithm based on a complete binary heap, and its time complexity is O (nlogn). In this article, we will write the heap sort algorithm using C# and provide detailed code examples.

1. Build a heap

In the heap sorting algorithm, you first need to build a maximum heap (or minimum heap). The property of the max heap is that the value of the parent node is greater than or equal to the value of its child node, while the opposite is true for the min heap.

In order to build a maximum heap, we can use an array to represent the heap. The nodes of the heap are arranged in hierarchical order. Given a node index i, we can find the indexes of its parent and child nodes by:

• Parent node index = (i - 1) / 2
• Left child node Index = 2 * i 1
• Right child node index = 2 * i 2

Using these indexes, we can easily move around the heap and move large (or small) The element is pushed to the top of the heap.

The following is a sample code using C# to implement a maximum heap:

public void BuildMaxHeap(int[] arr, int n, int i)
{
    int largest = i; // 初始化最大元素的索引
    int left = 2 * i + 1; // 左子节点索引
    int right = 2 * i + 2; // 右子节点索引

    // 如果左子节点比父节点大，更新最大元素的索引
    if (left < n && arr[left] > arr[largest])
    {
        largest = left;
    }

    // 如果右子节点比父节点大，更新最大元素的索引
    if (right < n && arr[right] > arr[largest])
    {
        largest = right;
    }

    // 如果最大元素的索引不是父节点的索引，交换父节点和最大元素
    if (largest != i)
    {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;

        // 递归地建立最大堆
        BuildMaxHeap(arr, n, largest);
    }
}

2. Heap sort

After building the maximum heap, we can use heap sort Algorithm to sort an array. The idea of ​​heap sort is to continuously swap the largest element to the end of the array and reduce the range of the array to be sorted. The specific steps are as follows:

• Build the maximum heap
• Exchange the top element and the last element of the heap
• Re-adjust the heap
• Repeat the above steps until There is only one element left in the sorted array

The following is a sample code using C# to implement heap sort:

public void HeapSort(int[] arr)
{
    int n = arr.Length;

    // 构建最大堆
    for (int i = n / 2 - 1; i >= 0; i--)
    {
        BuildMaxHeap(arr, n, i);
    }

    // 交换堆顶元素和末尾元素，并重建最大堆
    for (int i = n - 1; i > 0; i--)
    {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        BuildMaxHeap(arr, i, 0);
    }
}

3. Test code

For To verify that our heap sort algorithm is correct, we can write some test code that sorts a randomly generated array and outputs the results to check. The following is an example of a heap sort test code written in C#:

int[] arr = { 12, 11, 13, 5, 6, 7 };
HeapSort(arr);

Console.WriteLine("排序后的数组：");
foreach (var element in arr)
{
    Console.Write(element + " ");
}

4. Summary

Through the above steps, we successfully wrote the heap sort algorithm using C#, Detailed code examples are provided. Heap sort is an efficient sorting algorithm that provides good performance in most cases. I hope this article will help you understand and implement the heap sort algorithm!

The above is the detailed content of How to write a heap sort algorithm using C#. For more information, please follow other related articles on the PHP Chinese website!