快排的代码将数组索引改为size_t出错
来源：
_T先生_
2017-01-17
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
实在看不出哪里出了错。求解答
写回答
1回答
-
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); }10
相似问题