Быстрая сортировка со средним элементом в качестве оси

Question

Я пытаюсь найти какое-либо объяснение того, как Быстрая сортировка работает со средним элементом как осью, но я не смог найти ни одного.То, что я пытаюсь найти, - это какая-нибудь демонстрация того, как числа сортируются шаг за шагом, потому что это действительно сложное понимание алгоритмов.Спасибо.

Answer 1

Вертикальные черты расположены вокруг оси:

 61 11 93 74 75 21 12|55|81 19 14 86 19 79 23 44
 44 11 23|19|14 21 12 19                        
 19|11|12 14                                    
 11                                             
    19|12|14                                    
    12                                          
      |19|14                                    
       14                                       
          19                                    
             19|21|23 44                        
            |19|21                              
             19                                 
                21                              
                  |23|44                        
                   23                           
                      44                        
                         81 55 75|86|74 79 93 61
                         81 55|75|61 74 79      
                         74|55|61               
                         55                     
                           |74|61               
                            61                  
                               74               
                                  75|81|79      
                                 |75|79         
                                  75            
                                     79         
                                        81      
                                          |93|86
                                           86   
                                              93
 11 12 14 19 19 21 23 44 55 61 74 75 79 81 86 93

На основании этого варианта схемы разбиения Hoare:

void QuickSort(int a[], int lo, int hi) {
    int i, j, p;
    if (lo >= hi)
        return;
    i = lo - 1;
    j = hi + 1;
    p = a[(lo + hi)/2];
    while (1)
    {
        while (a[++i] < p) ;
        while (a[--j] > p) ;
        if (i >= j)
            break;
        swap(a+i, a+j);
    }
    QuickSort(a, lo, j);
    QuickSort(a, j + 1, hi);
}

Обратите внимание, что точка может заканчиваться либо слева, либоправая часть после шага раздела.

Answer 2

Быстрая сортировка выбирает значение поворота и перемещает меньшие элементы в начало массива, а большие элементы в конец.Это выполняется путем многократного сканирования с обоих концов до тех пор, пока не будет найдена и заменена пара большой / маленький.

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

Вспомните, что значение сводной оси можно выбрать произвольно, при условии, что существует хотя бы один элемент меньшего размера и один больший в массиве.