• 簡介

堆排序（英語：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ì)，因此需要對當(dāng)前無序區(qū)(R1,R2,......Rn-1)調(diào)整為新堆，然后再次將R[1]與無序區(qū)最后一個元素交換，得到新的無序區(qū)(R1,R2....Rn-2)和新的有序區(qū)(Rn-1,Rn)。不斷重復(fù)此過程直到有序區(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é)點指標(biāo)和子節(jié)點指標(biāo)
    int dad = start;
    int son = dad * 2 + 1;
    while (son <= end) { //若子節(jié)點指標(biāo)在范圍內(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、重復(fù)步驟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é)點指標(biāo)和子節(jié)點指標(biāo)
    int dad = start;
    int son = dad * 2 + 1;
    while (son <= end) { //若子節(jié)點指標(biāo)在范圍內(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、重復(fù)步驟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];

• 時間復(fù)雜度

最好、最壞和平均時間復(fù)雜度都為O(nlogn)。

• 算法穩(wěn)定性

不穩(wěn)定的排序算法

提供一個他人的更詳細(xì)的解讀堆排序