空间复杂度O(1),时间复杂度O(nlogn)的堆排序算法C++实现

1.堆排序理论

本方法采用最大堆结构，最大堆是一棵完全二叉树也是一棵最大树，最大树是指在树中，若一个结点有儿子结点则其关键字值都不小于其儿子结点的关键字值。
根据需要排序的序列list，
（1）把list创建为最大堆结构，这一步不用添加额外存储空间，以list本身为堆的存储结构，从首元素开始逐个将元素加入堆中，每加入一个就要重新调整为最大堆，这样直到最后一个元素加入调整成与原list对应的最大堆;
（2）取堆顶元素，也就是（1）调整后的list的首元素，使其与堆list的末尾元素交换，这样就形成了除去最大元素的一个新堆，调整新堆为新的最大堆，这一过程中就不再考虑交换到末尾的旧的最大堆的堆顶元素，调整后就形成了比原list缺省了最大元素的新最大堆，按照这个规则每次都取新的最大堆的堆顶元素与新的最大堆的末尾元素交换，然后调整为比上一最大堆少一个元素的新最大堆，直到所有list元素取完，原list就形成了一个升序的排列

2.C++ 代码实现：

堆操作：

/*****************************
filename: HeapManage.cpp
description: realize heap operate in CPP
                like, create heap , modify heap
author: warrior mail:[e-mail]
date:2016-2-20
log:
*****************************/

/****** include *******/
#include "heapManage.h"
using namespace std;
/****** define *********/
/****** variable ********/
/****** function *******/
/****************
description: sort a int list by heap sort
input:
    int * arrIN
    const int arrLength
output:
    none
****************/
void heapSort(int* arrIN, const int arrLength)
{
    int heapLength = arrLength;
    int tempItem;
    createHeap(arrIN, arrLength);
    for(int i=0; i<arrLength; i++)
    {
        deleteMaxHeap(arrIN, heapLength);
    }
    for(int i=0; i<arrLength; i++)
    {
        cout<<" ,"<<arrIN[i];
    }
    cout<<endl;
}
/****************
description: create heap by int list
input:
    int * arrIN
    int arrLength
output:
    none
****************/
void createHeap(int* arrIN, const int arrLength)
{
    int heapLength = 0;
    for(int i=0; i<arrLength; i++)
    {
        insertMaxHeap(arrIN, arrIN[i], heapLength);
    }
    for(int i=0; i<arrLength; i++)
    {
         cout<<" ,"<<arrIN[i];
    }
    printf("lala\n");
}
/****************
description: insert one item to max heap
input:
    int * Heap
    int dataIN
    int &heapLength
output:
    none
****************/
void insertMaxHeap(int* Heap, int dataIN, int &heapLength)
{
    int iterationLength;
    int parentItem;
    int sunItem;
    int tempItem;
    heapLength++;
    iterationLength = heapLength;
    Heap[iterationLength-1] = dataIN;
    if(iterationLength==1)
        return;
    else
    {
         while(iterationLength>1)
        {
            parentItem = Heap[iterationLength/2 - 1];
            sunItem = Heap[iterationLength-1];
            if(parentItem < sunItem)
            {
                tempItem = parentItem;
                parentItem = sunItem;
                sunItem = tempItem;
                Heap[iterationLength/2 - 1] = parentItem;
                Heap[iterationLength-1] = sunItem;
            }
            else
                break;
            iterationLength = iterationLength/2;
        }
    }
}
/****************
description: delete one item to max heap
input:
    int * Heap
    int &heapLength
output:
    none
****************/
void deleteMaxHeap(int* Heap, int &heapLength)
{
    int iterationLength;
    int parentItem;
    int sunItem;
    int tempItem;
    tempItem = Heap[0];
    Heap[0] = Heap[heapLength-1];
    Heap[heapLength-1] = tempItem;
    iterationLength = 1;
    heapLength--;
    while(iterationLength*2 <= heapLength)
    {
        if((iterationLength*2+1)<=heapLength)
        {
            if(Heap[iterationLength*2+1-1]>Heap[iterationLength*2-1])
            {
                if(Heap[iterationLength*2+1-1]>Heap[iterationLength-1])
                {
                    tempItem = Heap[iterationLength-1];
                    Heap[iterationLength-1] = Heap[iterationLength*2+1-1];
                    Heap[iterationLength*2+1-1] = tempItem;
                    iterationLength = iterationLength*2+1;
                }
                else
                    break;
            }
            else
            {
                if(Heap[iterationLength*2-1]>Heap[iterationLength-1])
                {
                    tempItem = Heap[iterationLength-1];
                    Heap[iterationLength-1] = Heap[iterationLength*2-1];
                    Heap[iterationLength*2-1] = tempItem;
                    iterationLength = iterationLength*2;
                }
                else
                    break;
            }
        }
        else
        {
            if(Heap[iterationLength*2-1]>Heap[iterationLength-1])
            {
                tempItem = Heap[iterationLength-1];
                Heap[iterationLength-1] = Heap[iterationLength*2-1];
                Heap[iterationLength*2-1] = tempItem;
                iterationLength = iterationLength*2;
            }
            else
                break;
        }
    }
    for(int i=0; i<heapLength; i++)
    {
        cout<<" ,"<<Heap[i];
    }
    cout<<"lulu"<<endl;

}

#ifndef _HEAPMANAGE_H_
#define _HEAPMANAGE_H_
/****** include *******/
#include <iostream>
#include <stdio.h>
/****** define *********/
/****** variable ********/
/****** function *******/
void heapSort(int* arrIN, const int arrLenght);
void createHeap(int* arrIN, const int arrLength);
void insertMaxHeap(int* Heap, int dataIN, int &heapLength);
void deleteMaxHeap(int* Heap, int &heapLength);
#endif // _HEAPMANAGE_H_

主函数：

#include "heapManage.h"

using namespace std;

int main()
{
    int arrIN[] = {98, 17, 38, 19, 22, 69, 45, 12, 65, 98};
    heapSort(arrIN, sizeof(arrIN)/sizeof(int));
    cout << "Hello world!" << endl;
    return 0;
}

3.总结

（1）最大堆的父节点与子节点间的关系挺有意思，依据这个关系很方便的进行堆调整
                i
             /     \
          2*i     2*i + 1
（2）C++ 函数参数引用传递方法与按值传递方法
    void fun1(int &variable);variable 参数变量可以在fun1中进行改变，并能体现在函数fun1的外部，原因就是函数参数的地址也指向了variable的地址，也就是不同的变量名指向了相同的地址;
    void fun2(int variable);variable 参数变量可以在fun2中进行改变，但不能体现在函数fun2的外部，原因就是参数传递过程是variable把自己的值传递给了函数的参数变量，两个变量指向的是不同的地址，函数内对variable的操作并不是函数外部的variable，因此不会影响到外部变量的值;
    void fun3(const int variable); fun3中参数是常参数传递格式，意义就是传入的参数相当于常数，在函数fun3中只能对其读取不能对其修改，除此之外const参数和普通按值传递的参数一样使用。