高级快速排序：打印每个分区/插入的步骤。

Question

我已经学会并编写了QuickSort()，Partition()和InsertionSort()算法，因此能够运行代码并正确地对数组进行排序，但是如果我想在Java中打印并展示每个排序算法执行的单个步骤怎么办？

***需求：

***使用QuickSort以结合InsertionSort来提高效率。 如果左/右子数组的元素数量除以枢轴小于3(A[0..n-1], n<=3)，

***=>使用InsertionSort()

输出结果应该像这样：

<BEFORE SORTING>:[10, 4, 2, 8, 7, 3, 5, 9, 6, 1]
use_partition:[1, 4, 2, 8, 7, 3, 5, 9, 6, 10]
use_partition:[1, 3, 2, 4, 7, 8, 5, 9, 6, 10]
use_insertion:[1, 2, 3, 4, 7, 8, 5, 9, 6, 10]
use_partition:[1, 2, 3, 4, 5, 6, 7, 9, 8, 10]
use_partition:[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
<AFTER SORTING>:[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

我想使用 Java 将步骤打印出来，使实现更加清晰。我的第一个想法是使用一些条件循环，是否有人知道在哪里可以找到相关文章？非常感谢。

---

对不起，这是我写的代码：

import java.util.Arrays;
public class Main{
   public static void main(String args[]){
      int[] array1 = {10, 4, 2, 8, 7, 3, 5, 9, 6, 1};
      int n1 = array1.length;
      System.out.print("Before sorting is: ");
      System.out.println(Arrays.toString(array1));
      System.out.print("After sorting is: ");
      Quicksort(array1, 0, n1-1);
      /*
      the display loop I need
      */
   } //end main()

    public static void Quicksort(int[] array, int start, int end){
        if(start<end){
            if(end-start <=3){
           InsertionSort(array, start, end);
        }else{
            int pivot = HoarePartition(array, start, end); 
            Quicksort(array, start, pivot); 
            Quicksort(array, pivot+1, end);}    
        }
        }
    } //end Quicksort()

    public static void swapIJ(int[] array, int i, int j){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    } //end swapIJ

    public static int HoarePartition(int[] array, int start, int end){
        int pivot = array[start];
        int i = start -1 ;
        int j = end + 1;
        while(true){
            do{i++;}while(array[i] < pivot);
            do{j--;}while(array[j] > pivot);

            if(i>=j)
               return j;
            swapIJ(array, i, j);
        } //end while
    } //end HoarePartition()

    public static void InsertionSort(int[] array) {
       for(int i = 1; i < array.length; i++) {
           int temp = array[i];
           int j = i - 1;
        
           while(j >= 0 && array[j] > temp) {
               array[j + 1] = array[j];
               j--;
           }
           array[j + 1] = temp;
       } //end for
    } //end InsertionSort()

- ian

Answer 1

根据评论的建议，您可以在每次调用quicksort方法时放置System.out.println(Arrays.toString(array))。这将打印您的数组在每次排序迭代时的状态。

例如，在您的代码中，可以将其放置在HoarePartition方法返回之前。

public static int HoarePartition(int[] array, int start, int end) {
    int pivot = array[start];
    int i = start - 1;
    int j = end + 1;
    while (true) {
        do {
            i++;
        } while (array[i] < pivot);
        do {
            j--;
        } while (array[j] > pivot);

        if (i >= j) {
            //Printing the array status after the updates and right before returning
            System.out.println(Arrays.toString(array));
            return j;
        }
        swapIJ(array, i, j);
    } //end while
} //end HoarePartition()

- Dan

---

谢谢！我想现在我对于在哪里放置toString()方法有了一些想法，我正在尝试着去实践它。 - ian