swap换过来在换回去没看懂这里为啥要返回j呢

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

慕虎7937911

2020-05-27

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

T v = arr[l];

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

swap( arr[l] , arr[j]);

return j;

}

写回答

1回答

liuyubobobo

2020-05-27

因为循环后，j 指向了标定点的位置。在 j 之前，所有的元素都小于 arr[j]；在 j 之后，所有的元素都大于 arr[j]。

实际使用一个测试用例试试看，这个算法运行完成以后，j 指向的是谁？为什么要返回 j？

或者反向的，你根据自己的想法或者逻辑，认为应该返回谁？然后实际使用一个小测试用例验证一下，看看返回的对不对？

继续加油！：）

算法与数据结构（C++版）面试/评级的算法复习技能包

课程专为：短时间内应对面试、升职测评等艰巨任务打造

11218 学习 · 1617 问题

查看课程

相似问题

老师： __partition2中最后 swap( arr[l] , arr[j] ) 这句是什么意思啊？

回答 1

关于swap交换

回答 1

__partition2中最后 swap( arr[l] , arr[j] ) ,return j;为什么是返回j

回答 1

为什么是 if( i > j ) break; 而不是if( i >=j ) break; ?

回答 2

为什么在我的电脑上运行快速排序要比归并排序要慢啊= =

回答 7

打开慕课网App查看更多内容