快速排序程序未正确输出

QuickSort Program Not Outputting Right

本文关键字:输出 程序 快速排序      更新时间:2023-09-26

我正在尝试制作一个快速排序程序,虽然我觉得它应该按需输出,但事实并非如此。我觉得问题在于我如何构建我的循环,但事实可能并非如此。正如你所看到的,跑步者的第一次测试按照我的意愿打印出来,一切最终都得到了解决。如有任何帮助,我们将不胜感激。


我的主要程序:

import static java.lang.System.*;
import java.util.Arrays;		
 //use Arrays.toString() to help print out the array
public class QuickSort
{
	private static int passCount;
	public static void quickSort(Comparable[] list)
	{
		passCount=0;
		quickSort(list, 0, list.length-1);
	}
	private static void quickSort(Comparable[] list, int low, int high)
	{
		if(low >= high) 
			return;
		int a = partition(list, low, high);
		quickSort(list, low, a-1);
		quickSort(list, a+1, high);
	}
	private static int partition(Comparable[] list, int low, int high)
	{
		int x = low + 1;
        int y = high;
        while(x <= y) 
        	{
            if(list[x].compareTo(list[low]) <= 0) 
            	{x++;}
            
            else if(list[y].compareTo(list[low]) > 0) 
            	{y--;}
            
            else if(y < x) 
            	{break;}
            	
            else
                exchange(list, x, y);
            }
            
            exchange(list, low, y);
			
			out.println("pass " + passCount++ + " " + Arrays.toString(list) + "'n");
            return y;
            
        }
        private static void exchange(Object[] list, int x, int y) {
            Object temporary = list[x];
            list[x] = list[y];
            list[y] = temporary;
        }
}

我的跑步者:

public class QuickSortRunner
{
	public static void main(String args[])
	{
		QuickSort.quickSort(new Comparable[]{9,5,3,2});
		System.out.println("'n");
		QuickSort.quickSort(new Comparable[]{19,52,3,2,7,21});
		System.out.println("'n");
		QuickSort.quickSort(new Comparable[]{68,66,11,2,42,31});
		System.out.println("'n");
	}
}
我的输出:

pass 0 [2, 5, 3, 9]
pass 1 [2, 5, 3, 9]
pass 2 [2, 3, 5, 9]
pass 0 [2, 7, 3, 19, 52, 21]
pass 1 [2, 7, 3, 19, 52, 21]
pass 2 [2, 3, 7, 19, 52, 21]
pass 3 [2, 3, 7, 19, 21, 52]
pass 0 [31, 66, 11, 2, 42, 68]
pass 1 [11, 2, 31, 66, 42, 68]
pass 2 [2, 11, 31, 66, 42, 68]
pass 3 [2, 11, 31, 42, 66, 68]

期望输出:

pass 0 [2, 5, 3, 9]
pass 1 [2, 5, 3, 9]
pass 2 [2, 3, 5, 9]
pass 0 [7, 2, 3, 52, 19, 21]
pass 1 [3, 2, 7, 52, 19, 21]
pass 2 [2, 3, 7, 52, 19, 21]
pass 3 [2, 3, 7, 21, 19, 52]
pass 4 [2, 3, 7, 19, 21, 52]
pass 0 [31, 66, 11, 2, 42, 68]
pass 1 [2, 11, 66, 31, 42, 68]
pass 2 [2, 11, 66, 31, 42, 68]
pass 3 [2, 11, 42, 31, 66, 68]
pass 4 [2, 11, 31, 42, 66, 68]

要跳过交换的x++y--需要在while循环中,这样交换只有在被调用时才会发生。