我們一起聊聊C#堆排序算法
作者：大姚
堆排序是一種高效的排序算法，通過(guò)構(gòu)建最大堆和反復(fù)調(diào)整堆的操作，實(shí)現(xiàn)對(duì)數(shù)組的排序。其時(shí)間復(fù)雜度為O(nlogn)，并且具有較好的穩(wěn)定性和空間效率。
前言
堆排序是一種高效的排序算法，基于二叉堆數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)。它具有穩(wěn)定性、時(shí)間復(fù)雜度為O(nlogn)和空間復(fù)雜度為O(1)的特點(diǎn)。
堆排序?qū)崿F(xiàn)原理
- 構(gòu)建最大堆：將待排序數(shù)組構(gòu)建成一個(gè)最大堆，即滿(mǎn)足父節(jié)點(diǎn)大于等于子節(jié)點(diǎn)的特性。
- 將堆頂元素與最后一個(gè)元素交換：將最大堆的堆頂元素與堆中的最后一個(gè)元素交換位置，將最大元素放到了數(shù)組的末尾。
- 重新調(diào)整堆：對(duì)剩余的n-1個(gè)元素進(jìn)行堆調(diào)整，即將堆頂元素下沉，重新形成最大堆。
- 重復(fù)步驟2和3，直到堆中的所有元素都被排列好。
堆排序代碼實(shí)現(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--)
{
//將堆頂元素與當(dāng)前最后一個(gè)元素交換
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é)點(diǎn)最大
int left = 2 * i + 1; //左子節(jié)點(diǎn)
int right = 2 * i + 2; //右子節(jié)點(diǎn)
//如果左子節(jié)點(diǎn)大于父節(jié)點(diǎn)，則更新最大值
if (left < n && arr[left] > arr[largest])
largest = left;
//如果右子節(jié)點(diǎn)大于父節(jié)點(diǎn)和左子節(jié)點(diǎn)，則更新最大值
if (right < n && arr[right] > arr[largest])
largest = right;
//如果最大值不是當(dāng)前父節(jié)點(diǎn)，則交換父節(jié)點(diǎn)和最大值，并繼續(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));
}運(yùn)行結(jié)果
圖片
總結(jié)
堆排序是一種高效的排序算法，通過(guò)構(gòu)建最大堆和反復(fù)調(diào)整堆的操作，實(shí)現(xiàn)對(duì)數(shù)組的排序。其時(shí)間復(fù)雜度為O(nlogn)，并且具有較好的穩(wěn)定性和空間效率。但是由于其涉及大量的元素交換操作，所以在實(shí)際應(yīng)用中，可能不如快速排序等算法效率高。
責(zé)任編輯：武曉燕
來(lái)源：
追逐時(shí)光者
