快速排序（Quick sort）算法运行异常，输出结果不正确求调试

你的代码存在两个核心问题，导致排序结果错误：

问题1：分区函数的循环条件错误 #

在partition方法里，你误将索引值和pivot的数值做比较，正确逻辑应该是比较数组对应位置的元素和pivot的数值：

• 原错误代码：

  while (i <= pivot)  //Finding larger element than pivot
  ...
  while (j > pivot) //Finding smaller element than pivot
  

• 修正后：

  while (a.get(i) <= pivot)
  ...
  while (a.get(j) > pivot)
  

问题2：递归调用的范围错误 #

在QuickS方法中，左半部分递归应该排除已经归位的pivot（即p位置的元素），否则会重复处理导致逻辑混乱：

• 原错误代码：

  QuickS(low, p);
  

• 修正后：

  QuickS(low, p - 1);
  

修正后的完整代码 #

import java.util.*;

public class Quick_Sort {
    static Scanner s = new Scanner(System.in);

    private static ArrayList<Integer> a = new ArrayList<Integer>();
    
    static void fill() {
        int i;

        for (i = 0; i < 4; i++) {
            System.out.print("Enter number :");
            a.add(s.nextInt());
        }
        
        a.add(Integer.MAX_VALUE);
        System.out.print("\nBefore Sorting :");

        for (i = 0; i < a.size() - 1; i++) {
            System.out.print(a.get(i) + " ");
        }
    }


    static void swap(int i, int j) {
        int temp;

        temp = a.get(i);
        a.set(i, a.get(j));
        a.set(j, temp);
    }

    static int partition(int low, int high) {
        int i, j, pivot;

        i = low;
        j = high;

        pivot = a.get(low);
        do {
            do {
                i++;

            } while (a.get(i) <= pivot);  // 修正：比较数组元素与pivot

            do {
                j--;

            } while (a.get(j) > pivot); // 修正：比较数组元素与pivot

            if (i < j) {
                swap(i, j);  
            }

        } while (i < j);

        swap(low, j);    
        
        return j;
    }


    static void QuickS(int low, int high) {
        int p;

        System.out.println("low :" + low + " high :" + high);
        
        if (low < high) {
            p = partition(low, high);   

            System.out.println("mid :" + p);

            QuickS(low, p - 1); // 修正：左半部分递归范围排除pivot
            QuickS(p + 1, high);
        }
    }

    public static void main(String args[]) {
        int i;

        fill();
        QuickS(0, a.size() - 1);  // 建议改为动态获取数组长度，避免硬编码4
        
        System.out.print("\nAfter Sorting :");

        for (i = 0; i < a.size() - 1; i++) {
            System.out.print(a.get(i) + " ");
        }
    }
}

额外建议：main方法中调用QuickS时，使用a.size() - 1代替硬编码的4，这样即使修改输入元素数量，代码也能正常工作。

内容的提问来源于stack exchange，提问作者Jeet Narayan Chakraborty