快速可视化？

Question

我对编程相当陌生，并希望使用3的中间分区和3的截止值对快速排序算法进行一些可视化表示。

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

例如，尝试对此数组应用快速排序: 2、6、3、1、6、5、2、4、8

对于三条规则的中间点，枢轴是最左边、中间和最右边元素的中间点.那么，2，6和8的中位数是6，现在是多少？

Answer 1

下一步是分区:当您选择了一个枢轴时，将所有小于枢轴的元素向左移动，将所有较大的元素移动到右侧。一旦完成，您可以分别在左边和右边排序。

在分区之前：

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

在对左边的<6进行分区之后，在右边的>=6：

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

若要对左侧和右侧进行排序，请在两边重复相同的过程。

我让您了解了分区过程的具体细节(真正的划分过程是以不同的顺序保留元素的)。

需要记住的问题：

• 分区后，两边必须至少保留一个元素，否则过程可以永远循环(更糟糕的是，剩下的唯一元素可以是枢轴)；
• 理想情况下，分区将数组分成两个大小大致相等的子数组；但也会出现非常不相等的大小，使得算法速度慢得多；三个启发式的中间值并不能完全避免这种现象；
• 该算法是以递归方式编写的(排序函数调用自己)。在对两个子数组进行排序时，从最小值开始，这样嵌套调用的数量就会减少。这一点很重要；
• 这个过程对于小型数组来说是过分的，这就是为什么最好切换到一个更简单的方法，比如在本例中的StraightInsertion或StraightSelection。

您可以将整个排序过程描述为二叉树，其中一个节点持有一个数组，其中的支点是可区分的，并且有两个儿子持有子数组。

​

​

Answer 2

2, 6 ,8的介质是6，现在是什么？

下一步是将数组划分为左半部分，包含小于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 3

您可以在核桃上看到交互式可视化并使用它。它使用Dijkstra分区(比枢轴小、相等、大)。