#include <cstdio>

using namespace std;

class Sort{
public:
    int* arr;
    int arr_size;
    Sort(int* array,int size){
        arr = array;
        arr_size = size;
    }
    virtual void sort(){
        printf("请进行实例化并重写此方法！\n");
        return;
    };
};

class QuickSort:public Sort{
public:
    QuickSort(int* array,int size):Sort(array,size){}
    void sort(){
        sort(0,arr_size-1);
        return;
    }
private:
    //找到轴心下标的代码，其中数组已经被放到成员变量arr中，所以不用传入
    int pivot(int low,int high){
        //取区间下的第一个元素为轴心
        int tmp = arr[low];
        while(low<high){
            //轴心右侧的元素应该不小于轴心
            while(low<high&&arr[high]>=tmp) high--;
            //交换这个元素
            arr[low] = arr[high];
            //轴心左侧的元素应该小于轴心
            while(low<high&&arr[low]<tmp) low++;
            arr[high] = arr[low];
        }
        //此时low==high，所以用 arr[high] 也是一样的
        arr[low] = tmp;
        return low;
    }
    void sort(int low,int high){
        if(low<high){
            int p = pivot(low,high);
            sort(low,p-1);
            sort(p+1,high);
        }
    }
};

class HeapSort:public Sort{
public:
    HeapSort(int* array,int size):Sort(array,size){}
    void sort(){
        sort(0,arr_size-1);
    }
private:
    void swap(int &a,int &b){
        a = a^b;b = a^b;a = a^b;
    }
    //应该传入数组，起始位置，范围(排序过程中排好序的节点不必参与建堆)，但数组可以直接用arr
    void HeadAdjust(int root_pos,int high){
        //注意这里要控制子节点的最大范围，因为子节点的下标总是最大的
        for(int sub_node_pos = 2*root_pos + 1; sub_node_pos <= high; sub_node_pos = 2*root_pos + 1/*进入以最小值位置为根的子树*/){
            //大根堆中根节点始终大于左右子节点,从左右节点中挑出大的作为选择
            if(sub_node_pos<high&&arr[sub_node_pos]<arr[sub_node_pos+1]){
                sub_node_pos++;
            }
            //让较小值沉下去
            if(arr[root_pos]<arr[sub_node_pos]) {
                swap(arr[root_pos],arr[sub_node_pos]);
                //跟踪最小值的位置
                root_pos = sub_node_pos;
            }else{
                break;
            }
        }
    }
    void BuildHeap(int high){
        for(int root=(high-1)/2;root>=0;root--){
            HeadAdjust(root,high);
        }
    }
    void sort(int low,int high){
        BuildHeap(high);
        while(low<high){
            swap(arr[low],arr[high]);
            HeadAdjust(low,--high);
        }
    }
};

class MergeSort:public Sort{
public:
    MergeSort(int* array,int size):Sort(array,sort){}
    sort(){}
};


int main()
{
    int a[] = {1,8,6,5,7,3,2,9,0,4};
    int a_size = 10;
    Sort* s = new HeapSort(a,a_size);
    s->sort();
    for(int i=0;i<a_size;i++){
        printf("%d ",a[i]);
    }
    delete s;
    return 0;
}