java - ADVANCE_QUICKSORT : print every step of partition/insertion

Question

我自己学习并编写了 QuickSort()、Partition() 和 InsertionSort() 代码，因此能够正确运行代码并对数组进行排序，但是如果我想在 java 中打印并显示 SORT 的每个步骤怎么办算法呢？

***需求:

***使用QuickSort结合InsertionSort来提高效率。如果左/右子数组除以pivot的元素个数小于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()

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()