我自己学习并编写了 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()
最佳答案
正如评论中所建议的,您可以在每次调用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()
关于java - ADVANCE_QUICKSORT : print every step of partition/insertion,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/72418761/