常用算法

void quickSort(int arr[],int low,int high){
    if(low>=high){
        //子序列只有一个元素
        return;
    }
    int pivot = partition(arr,low,high);
    quickSort(arr,low,pivot-1);//基准的左子序列排序
    quickSort(arr,pivot+1,high);//基准的右子序列排序
}
int partition(int arr[],int low,int high){
    int pivot = arr[low];
    while(low<high){
        while(low<high && arr[high]>=pivot) high--;//找到小于基准的元素，low<high为了考虑有序的情况
        arr[low] = arr[high];//进行前置
        while(low<high && arr[low]<=pivot) low++;//找到大于基准的元素
        arr[high] = arr[low];//进行后置
    }
    arr[low] = pivot;//基准位置
    return low;//返回基准位置
}

void mergeSort(int arr[]){//主函数
    int temp[] = new [arr.length];
    internalSort(arr,temp,0,arr.length-1);
}
void internalSort(int arr[],int temp[],int low,int high){//递归
    if(low<high){
        int middle = (low+high)/2;//基准
        internalSort(arr,temp,low,middle);//对左序列排序
        internalSort(arr,temp,middle+1,high);//对右序列排序
        mergeSortArray(arr,temp,low,middle,high);//合并左右有序序列
    }
}
void mergeSortArray(int arr[],int temp[],int low,int middle,int high){
    int left1 = low;
    int left2 = middle+1;
    int k = 0;
    while(left1<=middle && left2<=high){
        temp[k++] = arr[left1]<arr[left2]?arr[left1++]:arr[left2++];//将较小的那个放入到临时数组中
    }
    while(left1<=middle){//左子序列有剩余
        temp[k++] = arr[left1++];
    }
    while(left2<=high){//右子序列有剩余
        temp[k++] = arr[left2++];
    }
    for(int i=0;i<k;i++){//合并递归中的左右子序列到原数组中
        arr[low+i] = temp[i];//此处的low为待排序的子序列起始位置
    }
}

#include <iostream>
using namespace std;

class Heap{
    public:
        int arr[];
        Heap(int arr[]):arr(arr){}
        //交换大根堆的堆顶与最后一个元素，再调整堆为大根堆
        void sort(){
            int last = arr.length-1;
            //初始化大根堆
            for(int i=getParentIndex(last);i>=0;--i){
                adjustHeap(i,last);
            }
            //交换并调整堆
            while(last>=0){
                swap(0,last--);
                //这里是从上到下了，除了根元素其他元素都满足大根堆性质，此操作为下滤
                adjustHeap(0,last);
            }
        }
    private:
        int getLeftChildIndex(int parent){
            return 2*i+1;
        }
        int getRightChildIndex(int parent){
            return 2*i+2;
        }
        int getParentIndex(int child){
            return (i-1)/2;
        }
        int swap(int i,int j){
            int k = arr[i];
            arr[i] = arr[j];
            arr[j] = k;
        }
        //自下而上构建堆
        void adjustHeap(int parent,int last){
            int left,right,j;
            left = getLeftChildIndex(parent);
            while(left<=last){
                right = left+1;
                j = arr[left]>arr[right]?left:right;//取子节点中最大的
                if(arr[j]>arr[parent]){//与父节点比较
                    swap(j,parent);//大的上移，子节点不满足大根堆性质，即上滤
                    parent = j;//还要继续看交换后其是否大于左右子节点
                    left = getLeftChildIndex(parent);
                }else{
                    //子节点都小于父节点则不需要调整，到此为止
                    break;
                }
            }
        } 
};
template <typename T>
void printArray(T arr[]){
    //输出数组
    for(i=0,i<arr.length;++i){
        sout<< arr[i] <<" ";
    }
}
int main(){
    int arr[] = {3,5,6,7,1,9,3,2};
    Heap h(arr);
    h.sort();
    printArray(arr);
}