算法读书笔记第2章-2

void ShellSort(int a[], int n)
{
    int h = 1;
    while(h < n/3){
        h = 3*h + 1;
    }
    while(h > 0){
        for(int i = h; i < n; ++i){
            for(int j = i; j >= h; j-=h){
                    if(a[j] < a[j-h])
                        swap(a[j],a[j-h]);
            }
        }
        h = h/3;
    }
}

void Merge(int a[], int l, int mid, int r)
{
    int i = 0;
    int p1= l;
    int p2 = mid+1;
    int help[maxn];
    while(p1<=mid && p2 <= r)
    {
        help[i++] = a[p1] < a[p2] ? a[p1++] : a[p2++];
    }
    while(p1 <= mid)
    {
        help[i++] = a[p1++];
    }

    while(p2 <= r)
    {
        help[i++] = a[p2++];
    }
    int k = 0;
    for(int i = l; i <= r; ++i)
    {
        a[i] = help[k++];
    }
}

void MergeSort(int a[],int l,int r)
{
    if(l == r)
        return ;
    int mid = l + (r-l)/2;
    MergeSort(a,l,mid);
    MergeSort(a,mid+1,r);
    Merge(a,l,mid,r);
} 

vector<int> Partition(int a[], int l, int r)
{
    vector<int> ans;
    int less = l-1;
    int more = r;
    int pos = l;
    while(pos < r)
    {
        if(a[pos] < a[r])
            swap(a[++less],a[pos++]);
        else if(a[pos] > a[r])
            swap(a[--more],a[pos]);
        else
            pos++;
    }
    swap(a[more],a[r]);
    ans.push_back(less+1);
    ans.push_back(more);
    return ans;
}

void QuickSort(int a[], int l, int r)
{
    if(l < r)
    {
        int pos =l+rand()%(r-l+1);
        swap(a[pos],a[r]);
        vector<int> p = Partition(a,l,r);
        QuickSort(a,l,p[0]-1);
        QuickSort(a,p[1]+1,r);
    }

}

void HeapInsert(int a[], int index){
    while(a[index] > a[(index-1)/2])
    {
        swap(a[index],a[(index-1)/2]);
        index = (index-1)/2;
    }
}

void Heapify(int a[], int index, int size){
    int left = index*2 + 1;
    while(left < size)
    {
        int largest  = left+1 < size && a[left+1] > a[left] ? left+1 : left;
        largest = a[largest] > a[index] ? largest : index;
        if(largest == index) break;
        swap(a[largest],a[index]);
        index = largest;
        left = index*2 + 1;
    }

}

void HeapSort(int a[],int n){
    for(int i = 0; i < n; ++i)
    {
        HeapInsert(a,i);
    }
    int size = n;
    swap(a[0],a[--size]);
    while(size > 0)
    {
        Heapify(a,0,size);
        swap(a[0],a[--size]);
    }
}