logo标签列表

快速排序解释

algorithmsortingquicksort
4
我正在学习快速排序，我在这里找到了解释算法的文章。
据我理解，但我在其中一个步骤有问题。
如果这个点上的数字76是7，请问有人能够正确地解释一下直到枢轴57保持在其正确位置的步骤是什么？

enter image description here

我认为如果读者首先查看幻灯片中解释的步骤会更有帮助，因为我发现有许多其他不同的方法来解释快速排序算法。
编辑后： 我猜最终的顺序会像这样：24 49 16 38 55 21 36 9 *7 *57 81 85 63 79 74 85 97 61 77 70 *68。（如nullpointer所述）
当蓝色找到右侧的最大元素68并跨越/遇到红色索引时，流程是否停止，并且跳过检查较小的元素？
你会跳过蓝色的7，停在红色的7上，比使用“76”多向右移动一个元素。 - BeyelerStudios
分区步骤的目的是确保所有小元素都位于大元素的左侧。小/大分类是通过与“枢轴”值进行比较来决定的。为了使算法进展，必须确保至少有一个小元素和一个大元素。 - user1196549
@YvesDaoust 正如您所提到的，应该有一个小的 AND 一个大的（需要两个数字），在上述情况下只剩下一个元素需要比较，那么流程会是什么样子呢？ - OnePunchMan
当只剩下一个元素时，划分是无意义的。 - user1196549
@YvesDaoust，您能告诉我根据幻灯片中所解释的流程，上一个问题的答案吗？我关心的是“跳过检查较小元素”的部分。 - OnePunchMan
2个回答
3

续上文...[* 蓝色指针; ** 红色指针; *** 空位] 中心点 = 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
@Tootsie_Roll编辑了答案...没有图表，但尝试提供更好的可视化。 - Naman
在您的流程中，您首先尝试找到较小的元素。优先查找较小元素或较大元素是否重要？ - OnePunchMan
不，它们都在同一步骤中搜索。 - Naman
我的重要疑问是，在我问题中提到的位置xxxx到左侧的9和68到xxxx空白已按枢轴排序。现在唯一剩下需要比较的位置是7的位置，所以根据您的说法，您需要在右侧已排序区域（即在68处）找到最大的元素？ - OnePunchMan
@OnePunchMan 这个回答解决了你的问题吗？ - Naman
显示剩余2条评论
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
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接