void InterChange(int a[],int i,int j) {    int temp =  a[i];   a[i] = a[j];  a[j] = temp; }   int partition(int a[],int p,int q) {    int v = a[p],i = p,j = q;   do{        do i++;      while (a[i] < v);      do j--;     while (a[j] > v);     if (i < j)InterChange(a,i,j);      }while (i < j);    a[m] = a[j];a[j] = v;   return j; } void RQuickSort(int a[],int p,int q) { if (p < q) {   if (q-p > 5)InterChange(a,rand()%(q-p)+p,p);   int j = partition(a,p,q);   RQuickSort(p,j);  RQuickSort(j,q); } }   PS：随机排序算法的时间复杂度也是O(nlogn),但算法的平均性能是很好的。在解POJ1186题时，用分治＋二分查找算法，要用到排序，排序的对象最多有33万个，如果用qsort或sort可能会超时，但我用上面的RQuickSort就AC了。由此可见，当对象数目很多时，RQuickSort的性能要比qsort,sort要好。

评论