- 簡介
堆排序（英語：Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法癌淮。堆是一個近似完全二叉樹的結(jié)構(gòu)，并同時滿足堆積的性質(zhì)：即子結(jié)點的鍵值或索引總是小于（或者大于）它的父節(jié)點繁仁。
堆分為最大堆和最小堆，其實就是完全二叉樹。最大堆要求節(jié)點的元素都要不小于其孩子采够，最小堆要求節(jié)點元素都不大于其左右孩子，兩者對左右孩子的大小關(guān)系不做任何要求冰垄，其實很好理解蹬癌。有了上面的定義，我們可以得知虹茶，處于最大堆的根節(jié)點的元素一定是這個堆中的最大值逝薪。
- 算法原理
1、將初始待排序關(guān)鍵字序列(R1,R2....Rn)構(gòu)建成大頂堆蝴罪，此堆為初始的無序區(qū)
2董济、將堆頂元素R[1]與最后一個元素R[n]交換，此時得到新的無序區(qū)(R1,R2,......Rn-1)和新的有序區(qū)(Rn)
3要门、由于交換后新的堆頂R[1]可能違反堆的性質(zhì)虏肾，因此需要對當前無序區(qū)(R1,R2,......Rn-1)調(diào)整為新堆，然后再次將R[1]與無序區(qū)最后一個元素交換欢搜，得到新的無序區(qū)(R1,R2....Rn-2)和新的有序區(qū)(Rn-1,Rn)封豪。不斷重復此過程直到有序區(qū)的元素個數(shù)為n-1，則整個排序過程完成
- C語言實現(xiàn)
//最大堆調(diào)整（Max Heapify）：將堆的末端子節(jié)點作調(diào)整炒瘟，使得子節(jié)點永遠小于父節(jié)點
void maxHeapify(int numbers[], int start, int end) {
//建立父節(jié)點指標和子節(jié)點指標
int dad = start;
int son = dad * 2 + 1;
while (son <= end) { //若子節(jié)點指標在范圍內(nèi)才做比較
if (son + 1 <= end && numbers[son] < numbers[son + 1]) { //先比較兩個子節(jié)點大小吹埠，選擇最大的
son++;
}
if (numbers[dad] > numbers[son]) {//如果父節(jié)點大于子節(jié)點代表調(diào)整完畢，直接跳出函數(shù)
return;
}else { //否則交換父子內(nèi)容再繼續(xù)子節(jié)點和孫節(jié)點比較
int temp = numbers[son];
numbers[son] = numbers[dad];
numbers[dad] = temp;
dad = son;
son = dad * 2 + 1;
}
}
}
/**堆排序（HeapSort）：
1疮装、首先從最后一個父節(jié)點做最大堆調(diào)整缘琅，找出最大值，此時最大值位于根節(jié)點
2廓推、然后將最大值和已排好元素（依次找出的最大值排出的序列刷袍，如：6 3 9 23 12 8 [15 16 17 18]）前一位元素交換位置，再將除已排好元素外的其他元素(6 3 9 23 12 8)做最大堆調(diào)整樊展，找出最大值做个，此時最大值位于根節(jié)點
3、重復步驟2滚局，直至結(jié)束
*/
void heapSort(int numbers[], int length) {
//初始化居暖，i從最後一個父節(jié)點開始做最大堆調(diào)整,調(diào)整結(jié)束后根節(jié)點得到最大值
for (int i = length / 2 - 1; i >= 0; i--) {
maxHeapify(numbers, i, length - 1);
}
//先將第一個元素和已排好元素前一位做交換，再重新調(diào)整藤肢，直到排序完畢
for (int i = length - 1; i > 0; i--) {
int temp = numbers[0];
numbers[0] = numbers[i];
numbers[i] = temp;
maxHeapify(numbers, 0, i - 1);
}
}
//調(diào)用
int number[5] = {95, 45, 15, 78, 84};
heapSort(number, 5);
for (i = 0; i < 5; i++) {
printf("%d\n", number[i]);
}
- OC實現(xiàn)
//最大堆調(diào)整（Max Heapify）：將堆的末端子節(jié)點作調(diào)整太闺，使得子節(jié)點永遠小于父節(jié)點
- (void)maxHeapifyWithNumbers:(NSMutableArray *)numbers start:(int)start end:(int)end {
//建立父節(jié)點指標和子節(jié)點指標
int dad = start;
int son = dad * 2 + 1;
while (son <= end) { //若子節(jié)點指標在范圍內(nèi)才做比較
if (son + 1 <= end && [numbers[son] intValue] < [numbers[son + 1] intValue]) { //先比較兩個子節(jié)點大小，選擇最大的
son++;
}
if ([numbers[dad] intValue] > [numbers[son] intValue]) {//如果父節(jié)點大于子節(jié)點代表調(diào)整完畢嘁圈，直接跳出函數(shù)
return;
}else { //否則交換父子內(nèi)容再繼續(xù)子節(jié)點和孫節(jié)點比較
[numbers exchangeObjectAtIndex:son withObjectAtIndex:dad];
dad = son;
son = dad * 2 + 1;
}
}
}
/**堆排序（HeapSort）：
1省骂、首先從最后一個父節(jié)點做最大堆調(diào)整蟀淮，找出最大值，此時最大值位于根節(jié)點
2钞澳、然后將最大值和已排好元素（依次找出的最大值排出的序列怠惶，如：6 3 9 23 12 8 [15 16 17 18]）前一位元素交換位置，再將除已排好元素外的其他元素(6 3 9 23 12 8)做最大堆調(diào)整轧粟，找出最大值策治，此時最大值位于根節(jié)點
3、重復步驟2兰吟，直至結(jié)束
*/
- (void)heapSortWithNumbers:(NSMutableArray *)numbers {
//初始化通惫，i從最後一個父節(jié)點開始做最大堆調(diào)整,調(diào)整結(jié)束后根節(jié)點得到最大值
for (int i = (int)numbers.count / 2 - 1; i >= 0; i--) {
[self maxHeapifyWithNumbers:numbers start:i end:(int)numbers.count - 1];
}
//先將第一個元素和已排好元素前一位做交換，再重新調(diào)整混蔼，直到排序完畢
for (int i = (int)numbers.count - 1; i > 0; i--) {
[numbers exchangeObjectAtIndex:0 withObjectAtIndex:i];
[self maxHeapifyWithNumbers:numbers start:0 end:i - 1];
}
NSLog(@"%@",numbers);
}
//調(diào)用
NSMutableArray *array = [NSMutableArray arrayWithObjects:@(10),@(4),@(8),@(99),@(16),@(19),@(3), nil];
[self heapSortWithNumbers:array];
- 時間復雜度
最好履腋、最壞和平均時間復雜度都為O(nlogn)。
- 算法穩(wěn)定性
不穩(wěn)定的排序算法
提供一個他人的更詳細的解讀堆排序
