我的快速排序方法未按预期工作

首先，这个...

swap((int)vec.elementAt(i), (int)vec.elementAt(j));
//...
public static void swap(int a, int b) {
    int temp;
    temp = a;
    a=b;
    b=temp;
}

是错误的。你交换了值，但你从不交换 中的元素，并且由于 Java 的工作方式，一旦方法存在，交换就会丢失Vector

相反，它应该更像是......

protected void swap(MyVector vector, int index1, int index2) {
    Integer value1 = vector.get(index1);
    Integer value2 = vector.get(index2);
    vector.set(index1, value2);
    vector.set(index2, value1);
}

接下来，这个...

MyVector lo = new MyVector();
MyVector hi = new MyVector();
int loSize = lo.size();
int hiSize = hi.size();
if (loSize >= hiSize)
    return;
int p = (int)vec.elementAt((loSize + hiSize) / 2);

没有任何意义。为什么要创建两个新的（我猜）空向量？这些将如何帮助你？？

和值应将范围括在要搜索的范围内（即，从索引到索引）。lo(w)hi(gh)Vectorlohi

then 表示要用于确定如何最好地执行排序的核心逻辑的“基本”比较值。p(ivot)

我会重写它，但老实说，逻辑是错误的。你应该从一个只接受 的方法开始，然后从中调用一个单独的方法，该方法接受 AND the （默认为 ） 和 （默认为 ） 值 - 这构成了递归的基础。sortVectorsortVectorlo0hiVector#size - 1

这意味着，当你完成一个传递时，你就会确定递归的下一阶段，比如......

if (low < j) {
    sort(vector, low, j);
}
if (i < high) {
    sort(vector, i, high);
}

现在，对我来说，我将从一个简单的类开始，它可以封装这个工作流并“隐藏”一些实现细节。你不需要“必须”这样做，但它会让你的一些工作更容易，因为你不需要不断地传递。Vector

下面的例子基本上创建一个 ，用一些整数填充它并随机化它。Vector

然后，它会对值进行排序并打印值。您应该注意的是，这不会进行“就地”替换，也就是说，排序将创建第一个副本的副本，然后对副本进行排序，将其返回给调用方。Vector

import java.util.Collections;
import java.util.Random;
import java.util.Vector;

public class Main {
    public static void main(String[] args) {
        Random rnd = new Random();
        Vector<Integer> master = new Vector<>(8);
        for (int index = 0; index < 8; index++) {
            master.add(index);
        }
        Collections.shuffle(master);

        Vector<Integer> sorted = QuickSort.sort(master);
        System.out.println("Unsorted = " + master);
        System.out.println("  Sorted = " + sorted);
    }

    public static class QuickSort {
        private Vector<Integer> master;

        private QuickSort(Vector<Integer> master) {
            // Make a shallow copy
            this.master = new Vector<>(master);
        }

        public static Vector<Integer> sort(Vector<Integer> master) {
            QuickSort quickSort = new QuickSort(master);
            return quickSort.sort();
        }

        protected Vector<Integer> sort() {
            sort(0, master.size() - 1);
            return master;
        }

        protected void sort(int low, int high) {
            int i = low, j = high;

            // Get the pivot element
            int pivot = low + (high - low) / 2;
            Integer value = master.get(pivot);

            System.out.println("low = " + low + "; high = " + high);
            // Divide into two lists
            while (i <= j) {

                while (master.get(i) < value) {
                    i++;
                }

                while (master.get(j) > value) {
                    j--;
                }

                if (i <= j) {
                    System.out.println("Swap " + master.get(i) + " <> " + master.get(j));
                    swap(i, j);
                    i++;
                    j--;
                }
            }

            // Recursion
            if (low < j) {
                sort(low, j);
            }
            if (i < high) {
                sort(i, high);
            }
        }

        protected void swap(int index1, int index2) {
            Integer value1 = master.get(index1);
            Integer value2 = master.get(index2);
            master.set(index1, value2);
            master.set(index2, value1);
        }
    }
}

我会考虑看看：

• QuickSort – 数据结构和算法教程
• Java 中的快速排序算法实现
• 快速排序算法

有关快速排序通常如何工作的更多详细信息