Быстрая сортировка объяснение

я учился быстрой сортировки, я обнаружил, что алгоритм объяснил here Быстрая сортировка объяснение

лучше всего моему пониманию, но у меня есть вопрос на одной ступени.

Может кто-то объяснил мне правильно, что бы шаги до шарнира удерживается на своем праве размещены, если число в этой точке, как показано на рисунке было ?

Я думаю, что было бы полезно, если читатель сначала увидеть шаги объяснены в слайдах, как я выяснил, есть много других иного подхода для объяснения алгоритма быстрой сортировки.

Editted: Я предположил, конечная последовательность будет, как

24 49 16 38 55 21 36 9 * 7 * 57 81 85 63 79 74 85 97 61 77 70 * 68. (как упоминалось с помощью nullpointer)

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

источник

2015-12-02 OnePunchMan

вы бы пропустить 7 с синий и останавливается на 7 с красным цветом, делая один элемент справа, чем с '76' – BeyelerStudios

Целью этапа разделения является установление того, что все маленькие элементы расположены слева от больших элементов. Малая/большая классификация определяется по сравнению с «опорным» значением. Чтобы алгоритм работал, нужно убедиться, что существует хотя бы один маленький и один большой элемент. –

@YvesDaoust, как вы упомянули, должен быть один маленький ** AND ** один большой (требуется два числа), каков будет поток в приведенном выше случае, так как остается только один элемент, который нужно сравнить. – OnePunchMan

Contd .. [* синий указатель; ** красный указатель; *** вакантными] Pivot = 57

=> 24 49 16 38 55 21 36 *68 7 **9 81 85 63 79 74 85 97 61 77 70 *** 

=> 24 49 16 38 55 21 36 *9 7 **68 81 85 63 79 74 85 97 61 77 70 ***

Я ожидаю, что вещи, пока это будет ясно, как они, как это. 9 и 68 заменены. Теперь следующее число меньше 57 с правого конца равно 7 (так **), а число больше, чем левое, - 68 (так *).

=> 24 49 16 38 55 21 36 9 **7 *68 81 85 63 79 74 85 97 61 77 70 ***

Но поскольку индексы не удовлетворяют условиям дальше, следовательно, число с красной стрелкой 68 будет перемещен на свободное место и 57 его позиции в середине. Поэтому последовательность должна быть:

=> 24 49 16 38 55 21 36 9 **7 *57 81 85 63 79 74 85 97 61 77 70 ***68

источник

2015-12-02 12:20:19 nullpointer

Не могли бы вы объяснить мне, как это объяснялось в слайдах.Я догадался, что последовательность будет такой, но как? – OnePunchMan

@Tootsie_Roll отредактировал ответ ... нет диаграмм, но попытался обеспечить лучший визуальный – nullpointer

В своем потоке вы сначала попытаетесь найти меньший элемент. В первую очередь имеет значение приоритет поиска элемента с меньшим элементом или первого элемента? – OnePunchMan

Разновидностью сортировки:

void swap(int *i, int *j) 
{ 
    int t = *i; 
    *i = *j; 
    *j = t; 
} 

void QuickSort(int a[], int lo, int hi) { 
    int i = lo, j = (lo + hi)/2, k = hi; 
    int pivot; 
    if (a[k] < a[i])   // median of 3 
     swap(a+k, a+i); 
    if (a[j] < a[i]) 
     swap(a+j, a+i); 
    if (a[k] < a[j]) 
     swap(a+k, a+j); 
    pivot = a[j]; 
    showa(lo, hi); 
    while (i <= k) {   // partition 
     while (a[i] < pivot) 
      i++; 
     while (a[k] > pivot) 
      k--; 
     if (i <= k) { 
      swap(a+i, a+k); 
      i++; 
      k--; 
      showa(lo, hi); 
     } 
    } 
    if (lo < k)     // recurse 
     QuickSort(a, lo, k); 
    if (i < hi) 
     QuickSort(a, i, hi); 
}

Выходной сигнал с '*' после выгружена номер:

57 70 97 38 63 21 85 68 76 9 81 36 55 79 74 85 16 61 77 49 24 
24*70 97 38 63 21 85 68 76 9 57*36 55 79 74 85 16 61 77 49 81* 
24 49*97 38 63 21 85 68 76 9 57 36 55 79 74 85 16 61 77 70*81 
24 49 16*38 63 21 85 68 76 9 57 36 55 79 74 85 97*61 77 70 81 
24 49 16 38 55*21 85 68 76 9 57 36 63*79 74 85 97 61 77 70 81 
24 49 16 38 55 21 36*68 76 9 57 85*63 79 74 85 97 61 77 70 81 
24 49 16 38 55 21 36 57*76 9 68*85 63 79 74 85 97 61 77 70 81 
24 49 16 38 55 21 36 57 9*76*68 85 63 79 74 85 97 61 77 70 81 
9*49 16 38 24*21 36 57 55*          
9 21*16 38 24 49*36 57 55          
9 21 16 24*38*49 36 57 55          
9 21 16 24              
9 16*21*24              
9 16               
9 16               
     21 24              
     21 24              
      36*49 38*57 55          
      36 38*49*57 55          
      36 38            
      36 38            
        49 55*57*          
        49 55 57          
          74*68 85 63 79 76*85 97 61 77 70 81 
          74 68 70*63 79 76 85 97 61 77 85*81 
          74 68 70 63 61*76 85 97 79*77 85 81 
          74 68 70 63 61 76 85 97 79 77 85 81 
          61*68 70 63 74*      
          61 68 63*70*74      
          61 63*68*       
          61 63 68        
            70 74      
            70 74      
              79*97 81*77 85 85* 
              79 77*81 97*85 85 
              79 77 81 97 85 85 
              77*79*    
              77 79    
                 85*85 97* 
                 85 85 97 
                 85 97 
                 85 97 
9 16 21 24 36 38 49 55 57 61 63 68 70 74 76 77 79 81 85 85 97

источник

2015-12-02 13:58:53 rcgldr

ответ

Смежные вопросы