关于程序员:PAT归并排序与快速排序模板

1. 归并排序

const int maxn = 1010;

void merge(int A[], int left1, int right1, int left2, int right2){
    int i = left1, j = left2;
    int temp[maxn], len = 0;
    while(i <= right1 && j <= right2){if(A[i] < A[j]) temp[len++] = A[i++];
        else    temp[len++] = A[j++];
    }
    while(i <= right1)  temp[len++] = A[i++];
    while(j <= right2)  temp[len++] = A[j++];
    for(int i = 0; i < len; i++){A[left1+i] = temp[i];   // 右边记得加上偏移量 left1
    }
}

void mergeSort(int A[], int left, int right){if(left < right){// 此处用 if 即可，因为是递归模式，故不必 while
        int mid = (left + right) / 2;
        mergeSort(A, left, mid);
        mergeSort(A, mid+1, right);
        merge(A, left, mid, mid+1, right);
    }
}

2. 疾速排序

int Partition(int A[], int left, int right){int temp = A[left];
    while(left < right){while(left < right && temp < A[right])  right--;
        A[left] = A[right];
        while(left < right && temp >= A[left])   left++;
        A[right] = A[left];
    }
    A[left] = temp;
    return left;
}

void quickSort(int A[], int left, int right){if(left >= right)    return;    // 递归边界，退出递归
    int pos = Partition(A, left, right);
    quickSort(A, left, pos-1);
    quickSort(A, pos+1, right);
}