东北大学842（12）——排序编程题

笔记所有内容参考《东大红皮书》《王道》《天勤》，由本人分析整理。
简单的，或者复杂且没考过的，都不写。

调整大根堆（只考过一次）

1. 大根堆实际上还是数组
2. 双亲结点，左孩子结点，右孩子结点为一组
3. 先寻找最后的一组
4. 每一次先比较两个孩子谁大
5. 然后较大的孩子与双亲比较
   1. 双亲大，就跳到下一组，直到根
   2. 孩子大，交换孩子，双亲。
      1. 检查受改变的孩子的组有没有变

//根节点为1；递归的方式好写
void AdjustDown(int A[], int length, int i) {
        if(2i >= length) {
            return;
        }
        int maxChildIdx = 2i;
        if(2i+1 < length && A[2i] > A[2i+1]) {
                maxChildIdx = 2i+1;
        }
        if(A[i] >= A[maxChildIdx]) {
            return;
        }
        if(A[maxChildIdx] > A[i]) {
                A[0] = A[i];
                A[i] = A[maxChildIdx];
                A[maxChildIdx] = A[0];
        }
        AdjustDown(A, length, maxChildIdx);
}

void AdjustHeap(int A[], int length) {
    for(int i = length / 2；i > 0; --i) {
        AdjustDown(A, length, i);
    }
}

快排模板（没考过，但是很好写）

1. 取第一个为标准
2. 把小于标准的，放前面；大于标准的放后面
3. 标准放回中间
4. 分成两部分递归

void QSort(int a[], int i, int j, int low, int high) {
    if(low >= high) {
        return;
    }
    int temp = a[low];
    while(low < high && temp <= a[high]) {
        --high;
    }
    if(low < high) {
        a[low] = a[high];
    }
    while(low < high && temp > a[low]) {
        ++low;
    }
    if(low < high) {
        a[high] = a[low];
    }
    a[low] = temp;
    QSort(a, i, j, i, low - 1);
    QSort(a, i, j, low + 1, j);
}