復習 快排
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 就不用了。