【數(shù)據(jù)結(jié)構(gòu)】將一組數(shù)據(jù)升序排序（利用堆排序）

堆排序相對(duì)冒泡排序、選擇排序效率很高，不再是O（n^2）.

假若將一個(gè)序列升序排序好，那么我們來考慮最大堆還是最小堆來排序。假若是最小堆的話，堆的頂端必定是堆中的最小值，這樣貌似可以。但是，如果是它的（一邊或）子樹左子樹的節(jié)點(diǎn)數(shù)據(jù)值大于（一邊或）右子樹的節(jié)點(diǎn)數(shù)據(jù)值，直接打印肯定是錯(cuò)誤的，而且對(duì)于此時(shí)的堆我們也無法操控來調(diào)整好正確的順序了。

那我們換成最大堆來實(shí)現(xiàn)升序想，當(dāng)我們把序列調(diào)整成為最大堆后，最大堆頂端的數(shù)據(jù)值是最大的，然后我們將這個(gè)最大值與堆的最后一個(gè)葉子節(jié)點(diǎn)值來進(jìn)行交換，再將交換后的頂端值進(jìn)行調(diào)整，換到合適的位置處……重復(fù)這樣的工作，注意：進(jìn)行第2次交換就要將頂端元素值與倒數(shù)第2個(gè)節(jié)點(diǎn)元素值交換了，且調(diào)整頂端元素位置也不能一直調(diào)整到size-1處。（因?yàn)椋簊ize-1處的值已經(jīng)是最大）

代碼如下：

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;

#include<assert.h>


void AdjustDown(int* a,int parent, int size)
{
    int child = 2 * parent + 1;
    while (child < size)
    {
        if (child + 1 < size && a[child] < a[child + 1])
        {
            ++child;
        }
        if (a[child]>a[parent])
        {
            swap(a[child], a[parent]);
            parent = child;
            child = 2 * parent + 1;
        }
        else
        {
            break;
        }
    }
}


void Print(int*a, int size)
{
    cout << "升序序列為："<<endl;
    for (int i = 0; i < size; i++)
    {
        cout << a[i] << "  ";
    }
    cout << endl;
}


void HeapSort(int* a,int size)
{
    assert(a);
    
    //建成最大堆
    for (int i = (size - 2) / 2; i >=0; i--)
    {
        AdjustDown(a,i, size);
    }

    //交換順序
    for (int i = 0; i < size; i++)
    {
        swap(a[0], a[size - i - 1]);
        AdjustDown(a, 0, size-i-1);
    }    
}

 
void Test()
{
    int arr[] = { 12, 2, 10, 4, 6, 8, 54, 67,100,34,678, 25, 178 };
    int size = sizeof(arr) / sizeof(arr[0]);
    HeapSort(arr, size);    
    Print(arr,size);
}


int main()
{
    Test();
    system("pause");
    return 0;
}

時(shí)間復(fù)雜度：

（n-2）/2*lgn+n*(1+lgn)--->O(n).