从快排看指针数组

2018-03-04

最近在刷题的时候遇到一个数组partition的坑，现记录下来。

三路快排的思想是用一个指针遍历，两个指针记录状态，思想简单但实现有一个坑点，那就是指针的边界问题处理，在书写数组程序的时候，一定要非常清楚指针的含义，搞清楚是开区间还是闭区间。

另外还要注意，分割元素的时候，与左边的元素进行交换，左指针和遍历指针要同时递增，与右边的元素进行交换，只有右指针递增。

闭区间的程序如下所示：

void __quickSort3Ways(int arr[], int l, int r){
    // 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
    swap( arr[l], arr[rand()%(r-l+1)+l ] );
    int v = arr[l];
    int lt = l;     // arr[l+1...lt] < v
    int gt = r + 1; // arr[gt...r] > v
    int i = l+1;    // arr[lt+1...i) == v
    while( i < gt ){
        if( arr[i] < v ){
            swap( arr[i], arr[lt+1]);
            i ++;
            lt ++;
        }
        else if( arr[i] > v ){
            swap( arr[i], arr[gt-1]);
            gt --;
        }
        else{ // arr[i] == v
            i ++;
        }
      swap( arr[l] , arr[lt] );
       __quickSort3Ways(arr, l, lt-1);
       __quickSort3Ways(arr, gt, r);
    }

在闭区间的情况下，左右两个指针指向最后一个元素，[lt+1,i)表示相等的元素，这个时候循环条件是i<gt ，意味着不用遍历到gt因为gt一定是大于分割元素的数值。

开区间的情况如下：

void QuickSort3(T arr[],int L,int R){	
	if(R<=L)
		return;
	srand(time(NULL));
	swap(arr[L],arr[rand()%(R-L+1)+L]);	
	int lt=L+1;//[L+1,lt)
	int gt=R;//[gt,R)
	int eq=L+1;	//[lt,eq)
	while(eq <= gt){
		if( arr[eq] < arr[L]){
			swap(arr[eq],arr[lt]);
			lt++;
			eq++;
		}
		else if( arr[eq] > arr[L]){
			swap( arr[eq] , arr[gt] );
			gt--;
		}
		else
			eq++;
	}	
	swap(arr[L],arr[lt-1]);
	QuickSort3(arr,L,lt-2);
	QuickSort3(arr,gt+1,R);
}

与之前程序区别就在循环条件和最后交换的元素上，由于是开区间，eq等于gt的时候需要继续进行判断，最后交换的也是lt前一个元素。

总结

数组的题目经常容易陷入边界问题的坑，这个时候最重要的是搞清楚变量定义的含义是什么，开区间和闭区间对应的循环条件和循环不变量意义都不相同，需要特别注意。