-
堆排序
鎖定
堆排序堆的操作
在堆的數據結構中，堆中的最大值總是位於根節點（在優先隊列中使用堆的話堆中的最小值位於根節點）。堆中定義以下幾種操作：
- 最大堆調整（Max Heapify）：將堆的末端子節點作調整，使得子節點永遠小於父節點
- 創建最大堆（Build Max Heap）：將堆中的所有數據重新排序
- 堆排序（HeapSort）：移除位在第一個數據的根節點，並做最大堆調整的遞歸運算 [1]
堆排序實現示例
堆排序C語言
#include <stdio.h>
#include <stdlib.h>
void swap(int* a, int* b)
{
int temp = *b;
*b = *a;
*a = temp;
}
void max_heapify(int arr[], int start, int end)
{
//建立父節點指標和子節點指標
int dad = start;
int son = dad * 2 + 1;
while (son <= end) //若子節點指標在範圍內才做比較
{
if (son + 1 <= end && arr[son] < arr[son + 1])
//先比較兩個子節點大小，選擇最大的
son++;
if (arr[dad] > arr[son]) //如果父節點大於子節點代表調整完畢，直接跳出函數
return;
else //否則交換父子內容再繼續子節點和孫節點比較
{
swap(&arr[dad], &arr[son]);
dad = son;
son = dad * 2 + 1;
}
}
}
void heap_sort(int arr[], int len)
{
int i;
//初始化，i從最後一個父節點開始調整
for (i = len / 2 - 1; i >= 0; i--)
max_heapify(arr, i, len - 1);
//先將第一個元素和已排好元素前一位做交換，再重新調整，直到排序完畢
for (i = len - 1; i > 0; i--)
{
swap(&arr[0], &arr[i]);
max_heapify(arr, 0, i - 1);
}
}
int main() {
int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
int len = (int) sizeof(arr) / sizeof(*arr);
heap_sort(arr, len);
int i;
for (i = 0; i < len; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
堆排序C++
#include <iostream>
#include <algorithm>
using namespace std;
void max_heapify(int arr[], int start, int end)
{
//建立父節點指標和子節點指標
int dad = start;
int son = dad * 2 + 1;
while (son <= end) //若子節點指標在範圍內才做比較
{
if (son + 1 <= end && arr[son] < arr[son + 1]) //先比較兩個子節點大小，選擇最大的
son++;
if (arr[dad] > arr[son]) //如果父節點大於子節點代表調整完畢，直接跳出函數
return;
else //否則交換父子內容再繼續子節點和孫節點比較
{
swap(arr[dad], arr[son]);
dad = son;
son = dad * 2 + 1;
}
}
}
void heap_sort(int arr[], int len)
{
//初始化，i從最後一個父節點開始調整
for (int i = len / 2 - 1; i >= 0; i--)
max_heapify(arr, i, len - 1);
//先將第一個元素和已經排好的元素前一位做交換，再從新調整(剛調整的元素之前的元素)，直到排序完畢
for (int i = len - 1; i > 0; i--)
{
swap(arr[0], arr[i]);
max_heapify(arr, 0, i - 1);
}
}
int main()
{
int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
int len = (int) sizeof(arr) / sizeof(*arr);
heap_sort(arr, len);
for (int i = 0; i < len; i++)
cout << arr[i] << ' ';
cout << endl;
system("pause");
}堆排序Java語言
/**
* 選擇排序-堆排序
* @param array 待排序數組
* @return 已排序數組
*/
public static int[] heapSort(int[] array) {
//這裏元素的索引是從0開始的,所以最後一個非葉子結點array.length/2 - 1
for (int i = array.length / 2 - 1; i >= 0; i--) {
adjustHeap(array, i, array.length); //調整堆
}
// 上述邏輯，建堆結束
// 下面，開始排序邏輯
for (int j = array.length - 1; j > 0; j--) {
// 元素交換,作用是去掉大頂堆
// 把大頂堆的根元素，放到數組的最後；換句話説，就是每一次的堆調整之後，都會有一個元素到達自己的最終位置
swap(array, 0, j);
// 元素交換之後，毫無疑問，最後一個元素無需再考慮排序問題了。
// 接下來我們需要排序的，就是已經去掉了部分元素的堆了，這也是為什麼此方法放在循環裏的原因
// 而這裏，實質上是自上而下，自左向右進行調整的
adjustHeap(array, 0, j);
}
return array;
}
/**
* 整個堆排序最關鍵的地方
* @param array 待組堆
* @param i 起始結點
* @param length 堆的長度
*/
public static void adjustHeap(int[] array, int i, int length) {
// 先把當前元素取出來，因為當前元素可能要一直移動
int temp = array[i];
for (int k = 2 * i + 1; k < length; k = 2 * k + 1) { //2*i+1為左子樹i的左子樹(因為i是從0開始的),2*k+1為k的左子樹
// 讓k先指向子節點中最大的節點
if (k + 1 < length && array[k] < array[k + 1]) { //如果有右子樹,並且右子樹大於左子樹
k++;
}
//如果發現結點(左右子結點)大於根結點，則進行值的交換
if (array[k] > temp) {
swap(array, i, k);
// 如果子節點更換了，那麼，以子節點為根的子樹會受到影響,所以，循環對子節點所在的樹繼續進行判斷
i = k;
} else { //不用交換，直接終止循環
break;
}
}
}
/**
* 交換元素
* @param arr
* @param a 元素的下標
* @param b 元素的下標
*/
public static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
堆排序Python語言
def big_endian(arr,start,end): root=start child=root*2+1 #左孩子 while child<=end: #孩子比最後一個節點還大，也就意味着最後一個葉子節點了，就得跳出去一次循環，已經調整完畢 if child+1<=end and arr[child]<arr[child+1]: #為了始終讓其跟子元素的較大值比較，如果右邊大就左換右，左邊大的話就默認 child+=1 if arr[root]<arr[child]: #父節點小於子節點直接交換位置，同時座標也得換，這樣下次循環可以準確判斷：是否為最底層， #是不是調整完畢 arr[root],arr[child]=arr[child],arr[root] root=child child=root*2+1 else: break def heap_sort(arr): #無序區大根堆排序 first=len(arr)//2 - 1 for start in range(first,-1,-1): #從下到上，從左到右對每個節點進行調整，循環得到非葉子節點 big_endian(arr,start,len(arr)-1) #去調整所有的節點 for end in range(len(arr)-1,0,-1): arr[0],arr[end]=arr[end],arr[0] #頂部尾部互換位置 big_endian(arr,0,end-1) #重新調整子節點的順序，從頂開始調整 return arr def main(): l=[3,1,4,9,6,7,5,8,2,10] print(heap_sort(l)) if __name__=="__main__": main()
堆排序PHP語言
function hsort(array &$arr, $len){
$idx = $len - 1;
//創建堆操作，並使得堆有序
for($k=floor($len/2); $k>=0; $k--){
sink($arr, $k, $idx);
}
//排序操作
while($idx>0){
//獲取最大值操作
list($arr[0], $arr[$idx]) = [$arr[$idx], $arr[0]];
$idx--;
//堆調整下沉
sink($arr, 0, $idx);
}
}
//堆調整下沉，小數字下沉
function sink(array &$arr, $low, $high){
//從$low開始找子節點
while($low*2+1<=$high){
//獲取low的直接左子節點
$j = $low*2+1;
//判斷$low位置節點子節點中的較大子節點
if($j<$high && $arr[$j]<$arr[$j+1]){
$j++;
}
if($arr[$low]>$arr[$j]){
break;
}
//交換low節點和子節點的值
list($arr[$low], $arr[$j]) = [$arr[$j], $arr[$low]];
//繼續排查下沉後子節點是否需要進行下沉操作
$low = $j;
}
}
$a = [4,3,6,7,5,1,9,0,2];
hsort($a, count($a));
print_r($a);
