快速排序解释

Question

我在学习快速排序，我发现算法解释了这里

据我所知，我有一个问题。

有人能恰当地解释一下，如果这张图中所示的数字76是7，那么在将支点57保持在正确位置之前，步骤是什么呢？

​

​

我认为如果读者首先看到幻灯片中解释的步骤会更有帮助，因为我发现还有许多其他不同的方法来解释快速排序算法。

编辑：，我猜最后的排序应该是

24 49 16 38 55 21 36 9 *57 81 85 63 79 74 85 97 61 77 70 *68(如无空指针所述)

当蓝色发现右边最大的元素68，跳过检查较小的元素作为蓝色交叉/满足红色指数时，流量是否停止了？

Answer 1

蓝色指针；**红色指针；*空白轴=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(so **)，大于它的左边的数是68(so *)。

 => 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

Answer 2

快速的变体：

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