快排的代码将数组索引改为size_t出错

Question

typedef size_t Index; //typedef int Index;

// 对arr[l...r]部分进行partition操作
// 返回p,使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
Index __partition(int arr[], Index l, Index r){

	int v = arr[l];

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

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

	return j;
}

// 对arr[l...r]部分进行快速排序
void __quickSort(int arr[], Index l, Index r){

	if( l < r )
	{
		Index p = __partition(arr, l, r);
		__quickSort(arr, l, p-1 );
		__quickSort(arr, p+1, r);
	}
}

void quickSort(int arr[], Index n){

	__quickSort(arr, 0, n-1);
}


int main()
{
	int a[] = {6, 3, 4, 5, 8, 7, 10, 6, 3, 4, 5, 0, 8, 7};
	Index n = sizeof(a)/sizeof(a[0]);
	quickSort(a, n);

	return 0;
}

当数组索引相关的变量为int时，代码正确运行，当我把数组索引相关的变量为size_t类型时，运行出错，如下图

运行平台：win7 64bit，VS2008

实在看不出哪里出了错。求解答

Answer 1

liuyubobobo 2017-01-17 23:49:15

size_t是一个unsigned的类型，所以不能存放负数。

__quickSort(arr, l, p-1 );

这句话在p = 0时，p-1=-1，是负数，在size_t类型下就会出问题，导致越界。

可以多加一个判断躲开这个陷阱，我基于你的代码最终调试通过的代码如下。注意，不要有减法：） 有了这个判断，递归终止条件也不需要了：）

void __quickSort(int arr[], Index l, Index r) {
    Index p = __partition(arr, l, r);
    if( l + 1 < p ) __quickSort(arr, l, p - 1);
    if( p + 1 < r ) __quickSort(arr, p + 1, r);
}