復(fù)習(xí) 快排
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;
}
在本實(shí)現(xiàn) 里面， 直接使用了最后一個(gè)元素作為基準(zhǔn)。
在選擇基準(zhǔn)時(shí)其實(shí)是有多種方式的。1）選第一個(gè)，不推薦。2）算最后一個(gè)，不推薦。3）選首、尾、中的中間值。4）隨機(jī)選擇。
選擇后將跑一趟比較，結(jié)果是左側(cè)為小的數(shù)，右側(cè)為大的數(shù)，原理是i,j 當(dāng)數(shù)小于基準(zhǔn)是則與左右的i 對換，這樣保證了i左側(cè)小于p i 到j(luò) 之間是大小p 的。
對于p 無需再排了。
需要特別注意的是partition 里面的元素位置與quicksort 分段是有關(guān)系的。 如果在partition 里面處理了last 那么 在分段時(shí)其實(shí)last 就不用了。