mergeSort中为什么在比较中有一个L个位置的偏移，减去的话根据数组索引不是指向的偏移了L个位置

Question

  int i = l, j = mid+1;

    for( int k = l ; k <= r; k ++ ){

        if( i > mid )   { arr[k] = aux[j-l]; j ++;}

        else if( j > r ){ arr[k] = aux[i-l]; i ++;}

        else if( aux[i-l] < aux[j-l] ){ arr[k] = aux[i-l]; i ++;}

        else                          { arr[k] = aux[j-l]; j ++;}

    }

Answer 1

liuyubobobo 2016-12-10 06:02:22

因为mergeSort是对数组[l...r]这个区间进行归并操作。我们使用了一个临时的数组aux。而这个临时数组aux我们只开辟了r-l+1这么多的空间，索引是从0开始的。换句话说，aux[0...r-l+1]对应了arr[l...r]，他们之间存在一个l的偏移，所以我们在处理的时候就要考虑这个偏移啦。

• 提问者 ddtang #1

  非常感谢！