我們一起聊聊C#堆排序算法
作者：大姚
堆排序是一種高效的排序算法，通過構(gòu)建最大堆和反復(fù)調(diào)整堆的操作，實現(xiàn)對數(shù)組的排序。其時間復(fù)雜度為O(nlogn)，并且具有較好的穩(wěn)定性和空間效率。
前言
堆排序是一種高效的排序算法，基于二叉堆數(shù)據(jù)結(jié)構(gòu)實現(xiàn)。它具有穩(wěn)定性、時間復(fù)雜度為O(nlogn)和空間復(fù)雜度為O(1)的特點。
堆排序?qū)崿F(xiàn)原理
- 構(gòu)建最大堆：將待排序數(shù)組構(gòu)建成一個最大堆，即滿足父節(jié)點大于等于子節(jié)點的特性。
- 將堆頂元素與最后一個元素交換：將最大堆的堆頂元素與堆中的最后一個元素交換位置，將最大元素放到了數(shù)組的末尾。
- 重新調(diào)整堆：對剩余的n-1個元素進行堆調(diào)整，即將堆頂元素下沉，重新形成最大堆。
- 重復(fù)步驟2和3，直到堆中的所有元素都被排列好。
堆排序代碼實現(xiàn)
public static void HeapSort(int[] array)
{
int arrayLength = array.Length;
//構(gòu)建最大堆
for (int i = arrayLength / 2 - 1; i >= 0; i--)
Heapify(array, arrayLength, i);
//依次取出堆頂元素，并重新調(diào)整堆
for (int i = arrayLength - 1; i >= 0; i--)
{
//將堆頂元素與當前最后一個元素交換
int temp = array[0];
array[0] = array[i];
array[i] = temp;
//重新調(diào)整堆
Heapify(array, i, 0);
}
}
private static void Heapify(int[] arr, int n, int i)
{
int largest = i; //假設(shè)父節(jié)點最大
int left = 2 * i + 1; //左子節(jié)點
int right = 2 * i + 2; //右子節(jié)點
//如果左子節(jié)點大于父節(jié)點，則更新最大值
if (left < n && arr[left] > arr[largest])
largest = left;
//如果右子節(jié)點大于父節(jié)點和左子節(jié)點，則更新最大值
if (right < n && arr[right] > arr[largest])
largest = right;
//如果最大值不是當前父節(jié)點，則交換父節(jié)點和最大值，并繼續(xù)向下調(diào)整堆
if (largest != i)
{
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
Heapify(arr, n, largest);
}
}
public static void HeapSortRun()
{
int[] array = { 19, 27, 46, 48, 50, 2, 4, 44, 47, 36, 38, 15, 26, 5, 3, 99, 888, 0, -1 };
Console.WriteLine("排序前數(shù)組：" + string.Join(", ", array));
HeapSort(array);
Console.WriteLine("排序后數(shù)組：" + string.Join(", ", array));
}運行結(jié)果
圖片
總結(jié)
堆排序是一種高效的排序算法，通過構(gòu)建最大堆和反復(fù)調(diào)整堆的操作，實現(xiàn)對數(shù)組的排序。其時間復(fù)雜度為O(nlogn)，并且具有較好的穩(wěn)定性和空間效率。但是由于其涉及大量的元素交換操作，所以在實際應(yīng)用中，可能不如快速排序等算法效率高。
責任編輯：武曉燕
來源：
追逐時光者
