一道快排的考研真题

来源：3-5 快速排序法 - Quick Sort

ych_1997

2021-08-13

今天遇到了一道考研真题，是某学校自主命题的。还没找到标准答案，只能在草稿纸上写写画画。我想要验证答案是否正确。

原题目：
已知关键字集合{11, 2, 16, 30, 8, 28, 4, 9, 20, 17}，若采用快速排序，且关键字按非递增排序，请给出以最后一个关键字为枢纽的第一趟排序结果。

这道题我翻译成课程的描述是：使用快速排序按从大到小排序。以最后一个元素为v，求第一趟快速排序的结果。
因为只用看第一趟，这是我改的partition实现：

int __partition(T arr[], int l, int r){

    T v = arr[r];

    int j = l-1; 
    for( int i = l; i < r ; i ++ )
        if( arr[i] > v ){
            j ++;
            swap( arr[j] , arr[i] );
        }

    swap( arr[r] , arr[j+1]);
   
    return j+1;
}

我觉得这个不在课程的答疑范围，但是实在没有资源问到标准答案，bobo老师如果有空的话帮我看看，谢谢！

写回答

1回答