快速排序可视化？

Question

我对编程还很陌生，想要一些使用三中位数分区和 3 截止值的快速排序算法的直观表示。

我想看看整个迭代过程，因为 Java 算法对我来说很难理解。

例如，尝试对这个数组应用快速排序：[2, 6, 3, 1, 6, 5, 2, 4, 8]

使用三中值规则，基准点是最左边、中间和最右边元素的中值。所以2、6、8的中位数是6。现在怎么办？

Answer 1

So the medium of 2,6,8 is 6. What now?

下一步是将数组分成左半部分，包含小于 6 的元素，右半部分，包含等于或大于 6 的元素。然后我们对每一半调用快速排序。

下面的Java程序实现了快速排序，显示排序前后的每个子数组。它还显示中位数的选择。

import java.io.*;

public class Quicksort {
  void swap(int[] data, int i, int j) {
    int t = data[i];
    data[i] = data[j];
    data[j] = t;
  }

  void display(int[] data, int left, int right) {
    for (int i = 0; i < right; ++i) {
      System.out.print(i < left ? "  " : " "+data[i]);
    }
    System.out.println();
  }

  //--- in-place implementation with median-of-three pivot
  int quicksort(int[] data, int left, int right, int callId) {
    int saveCallId = callId;
    System.out.print(callId+". sorting:");
    display(data, left, right);
    if (left+1 >= right) {
      System.out.print("  "+saveCallId+". result:");
      display(data, left, right);
      return callId;
    }
    int ai = left, bi = (left+right)/2, ci = right-1, pos;
    int a = data[ai], b = data[bi], c = data[ci];
    if (a < b) {
      if (c < a) {
        pos = ai;
      } else if (c < b) {
        pos = ci;
      } else {
        pos = bi;
      }
    } else {
      if (c < b) {
        pos = bi;
      } else if (c < a) {
        pos = ci;
      } else {
        pos = ai;
      }
    }
    int pivot = data[pos];
    System.out.println("   median of ["+a+", "+b+", "+c+"] is "+pivot);
    swap(data, right-1, pos);
    int tail = left;
    for (int i = left; i != right-1; ++i) {
      if (data[i] < pivot) {
        swap(data, tail, i);
        ++tail;
      }
    }
    swap(data, right-1, tail);
    callId = quicksort(data, left, tail, ++callId);
    callId = quicksort(data, tail+1, right, ++callId);
    System.out.print("  "+saveCallId+". result:");
    display(data, left, right);
    return callId;
  }

  public static void main(String[] args) {
    int[] data = new int[]{ 2, 6, 3, 1, 6, 5, 2, 4, 8 };
    new Quicksort().quicksort(data, 0, data.length, 0);
  }
}

对于输入案例{ 2, 6, 3, 1, 6, 5, 2, 4, 8 }，输出为：

0. sorting: 2 6 3 1 6 5 2 4 8
   median of [2, 6, 8] is 6
1. sorting: 2 3 1 5 2 4
   median of [2, 5, 4] is 4
2. sorting: 2 3 1 2
   median of [2, 1, 2] is 2
3. sorting: 1
  3. result: 1
4. sorting:     2 3
   median of [2, 3, 3] is 3
5. sorting:     2
  5. result:     2
6. sorting:        
  6. result:        
  4. result:     2 3
  2. result: 1 2 2 3
7. sorting:           5
  7. result:           5
  1. result: 1 2 2 3 4 5
8. sorting:               6 8
   median of [6, 8, 8] is 8
9. sorting:               6
  9. result:               6
10. sorting:                  
  10. result:                  
  8. result:               6 8
  0. result: 1 2 2 3 4 5 6 6 8

Answer 2

下一步是划分：当你选择了一个枢轴后，将所有小于该枢轴的元素向左移动，将所有大于该枢轴的元素向右移动。完成后，您可以分别在左侧和右侧排序。

分区前：

[2,6,3,1,6,5,2,4,8]

分割后左边<6，右边>=6：

[2,3,1,5,2,4] [6,6,8]

要左右排序，两边重复同样的步骤。

我让你发现了分区过程的细节（真正的分区顺序不同）。

需要记住的问题：

分割后，两边必须至少保留一个元素，否则程序会一直循环下去（更糟的是，只剩下一个元素可能是主元）；
理想情况下，分区将数组拆分为大小大致相等的两个子数组；但是也会出现非常不相等的大小，使算法慢得多； median-of-three 启发式并没有完全避免这种现象；
算法是用递归的方式写的（排序函数调用自己）。对两个子数组进行排序时，从最小的开始，以使嵌套调用的数量最少。这很重要；
该过程对于小数组来说太过分了，这就是为什么建议切换到更简单的方法，例如在这种情况下使用 StraightInsertion 或 StraightSelection。

您可以将整个排序过程描绘成一棵二叉树，其中一个节点持有一个数组，区分主元，并且有两个儿子持有子数组。

Answer 3

您可以在 the walnut 看到交互式可视化并使用它。它使用 Dijkstra 分区（小于、等于、大于基准）。

快速排序可视化？

Quicksort visualization?

java

sorting

algorithm

visualization

quicksort