Я занимаюсь различными учебными материалами и статьями, которые обсуждают quicksort и quickselect, однако мое понимание их по-прежнему шаткое.
Учитывая эту структуру кода, мне нужно уметь понять и объяснить, как работает quickselect.
// return the kth smallest item
int quickSelect(int items[], int first, int last, int k) {
int pivot = partition(items, first, last);
if (k < pivot-first) {
return quickSelect(items, first, pivot, k);
} else if (k > pivot) {
return quickSelect(items, pivot+1, last, k-pivot);
} else {
return items[k];
}
}
Мне нужно немного помочь с разбивкой на псевдокод, и пока мне не предоставлен код функции раздела, я хотел бы понять, что он будет делать, если предоставлена функция quickselect.
Я знаю, как работает quicksort, а не быстро. Код, который я только что представил, представляет собой пример, который мы получили о том, как форматировать быстрый выбор.
EDIT: исправленный код
int quickSelect(int items[], int first, int last, int k)
{
int pivot = partition(items, first, last);
if (k < pivot-first+1)
{ //boundary was wrong
return quickSelect(items, first, pivot, k);
}
else if (k > pivot-first+1)
{//boundary was wrong
return quickSelect(items, pivot+1, last, k-pivot);
}
else
{
return items[pivot];//index was wrong
}
}
Судебная процедура: @Haitao