一道快排的考研真题

Question

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

原题目：
已知关键字集合{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老师如果有空的话帮我看看，谢谢！

Answer 1

liuyubobobo 2021-08-13 06:14:15

你的代码是正确的。

但是，这种考试题的问题在于，考纲中的标准代码到底是什么。以快速排序为例，课程中给出了三种不同的 partition，对于同一个数据，给出的结果可能是不同的（都满足标定点左侧和右侧的范围要求）。如果你可以用自己写的代码来说明为什么是这个结果，这个代码没有问题。

继续加油！：）

• 提问者 ych_1997 #1

  谢谢老师！还有个问题，一种partition是否也对应着一种递归实现？如果对应的话，他们的第一趟排序结果是否一致？

• liuyubobobo 回复 提问者 ych_1997 #2

  没有理解什么意思？通常我们不会递归的实现 partition

• 提问者 ych_1997 回复 liuyubobobo #3

  因为考纲里出现了非递归实现，虽然我也觉得很写法不太自然。对于同一个数据，递归和非递归的快排实现，排序的第一趟结果可能会不同吗？（都满足标定点左侧和右侧的范围要求）

点开查看后面2条评论