复习 快排
int buf[1024] = {0};
int partition(int first, int last)
{
int stand = buf[last];
int i =0, j=0;
//int e = last -1;
for (;j < last ; j++ )
{
if (buf[j] <= stand )
{
int temp = buf[j];
buf[j] = buf[i];
buf[i] = temp;
i++;
}
}
int temp = buf[last];
buf[last] = buf[i];
buf[i] = temp;
return i;
}
void myQuickSort(int begin, int end)
{
if (begin < end)
{
int pivot ;
pivot = partition(begin, end);
myQuickSort(begin, pivot -1 );
myQuickSort(pivot+1, end);
}
}
int main()
{
srand(time(0));
for (int i = 0; i < 1000; i++)
{
buf[i] = rand() * 2342111134 % 6589453 ;
}
myQuickSort(0,1023);
return 0;
}
在本实现 里面， 直接使用了最后一个元素作为基准。
在选择基准时其实是有多种方式的。1）选第一个，不推荐。2）算最后一个，不推荐。3）选首、尾、中的中间值。4）随机选择。
选择后将跑一趟比较，结果是左侧为小的数，右侧为大的数，原理是i,j 当数小于基准是则与左右的i 对换，这样保证了i左侧小于p i 到j 之间是大小p 的。
对于p 无需再排了。
需要特别注意的是partition 里面的元素位置与quicksort 分段是有关系的。 如果在partition 里面处理了last 那么 在分段时其实last 就不用了。