快速排序算法有有关问题！求发现

快速排序算法有问题！求发现！

int partition(int array[], int n)
{
int lh, rh, pivot, temp;

pivot = array[0];
lh = 1;
rh = n - 1;

while (1) {
while (lh < rh && array[lh] < pivot)
++lh;
while (lh < rh && array[rh] >= pivot)
--rh;
if (lh == rh)
break;
temp = array[lh];
array[lh] = array[rh];
array[rh] = temp;
}
if (array[lh] >= pivot)
return 0;
array[0] = array[lh];
array[lh] = pivot;
return lh;
}

void QuickSort(int array[], int n)
{
int boundary;
if (n < 2)
return;
boundary = partition(array, n);
QuickSort(array, boundary);
QuickSort(array + boundary + 1, n - boundary - 1);
}

[解决办法]
你的快排参数有问题，你一直都是从0排到n这个是不对。其实下标和结束下标都是动态变化的，先由分治算法算出一个点n，然后分别排序改点的两侧 low - n-1 和 n+1 - high。你试试看这个：

int partition(int array[], int low,int high)
{
int pivot = array[low];

if (low>=high) return low;

while (low<high) {
while (low < high && array[high] >= pivot) --high;
array[low]=array[high];//算出high之后记得立刻赋值
while (low < high && array[low] <= pivot) ++low;
array[high]=array[low];
}
//array[0] = array[lh];这句话你写的，完全没必要，至少我没看懂。
array[low] = pivot;
return low;
}

void QuickSort(int array[], int low,int high)
{
int boundary;
if (low>=high)return;
boundary = partition(array, low , high);
QuickSort(array , low , boundary-1);//排low  -  boundary-1
QuickSort(array , boundary + 1, high );//排boundary+1 - high
}

查看更多 下一篇