рекурсивный вызов по алгоритму быстрой сортировки - PullRequest
Новая
       30

рекурсивный вызов по алгоритму быстрой сортировки

3 голосов
/ 15 марта 2019

У меня есть массив как A[] = { 10, 5, 3, 9, 22, 24, 28, 27, 15 }, я хотел отсортировать этот массив, используя QuickSort.У меня есть метод быстрой сортировки: 

QuickSort(int[] num, int start, int end)
{
   if(start < end)
   {
      int pIndex = Partition(num, start, end); //Pivot Index
      QuickSort(num, start, pIndex-1);
      QuickSort(num, pIndex + 1, end);
   }
}

Здесь я предполагаю, что последний индекс используется как элемент сводки, т. Е. 15 - это первый элемент сводки на первой итерации.

ДляРазделение: 

public static int Partition(int[] arr, int start, int end)
{
    int pivot = arr[end];
    int i = start - 1;

    for (int j = start; j <= end - 1; j++)
    {
        if (arr[j] < pivot)
        {
            i++;
            Swap(arr, i, j);
        }
    }

    Swap(arr, i + 1, end);
    return i + 1;
}

Как и в QuickSort, я делю задачу на два набора: первый со всеми элементами, меньшими или равными центральной точке, а второй со всеми элементами, большими, чем центральной.

Итак, делая левый рекурсивный вызов, я получаю вывод как 

3 5 9 10 15 24 28 27 22

3 5 9 10 15 24 28 27 22

3 5 9 10 15 24 28 27 22

Теперь, моя путаница заключается в том, когда после сортировки элемента с левой стороны, как рекурсивный вызов смещается вправо?

Как оценивается pIndex + 1 = 5, т.е. QuickSort(num, pIndex + 1, end)?

Почему после первого правого рекурсивного вызова программа не оценивается как QuickSort(num, start, pIndex-1).

По существу, как работает рекурсивный вызов на QuickSort?

...