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

Question

我尝试制作一个快速排序方法，其唯一参数是 MyVector（这只是一个法线向量），但该方法没有按预期工作，我不确定为什么。

预期输出应该是

索引0处的元素是：7 索引 0 处的元素为：10 索引 0 处的元素是：28

但是我得到的是

索引0处的元素是：41524 索引 1 处的元素为：26432 索引 2 处的元素是：51244

驱动程序类（示例）

    MySort.QuickSort(testing);
    System.out.println("The element at index 0 is: "+testing.elementAt(0));
    System.out.println("The element at index 1 is: "+testing.elementAt(1));
    System.out.println("The element at index 2 is: "+testing.elementAt(2));

MySort 类

public static void QuickSort(MyVector vec){
    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);   // set pivot, could use median of 3 here
    int i = loSize-1;
    int j = hiSize+1;
    while (true){
        while ((int)vec.elementAt(i) < p) {
        ++i;
        }
        while ((int)vec.elementAt(j) > p) { ;    // decrease j until a[j] <= pivot
        --j;
        }
        if (i >= j)             // break if indices meet or cross
            break;
        swap((int)vec.elementAt(i), (int)vec.elementAt(j));
    }
    QuickSort(lo);        
    QuickSort(hi); 
      }
public static void swap(int a, int b) {
    int temp;
    temp = a;
    a=b;
    b=temp;
}

Answer 1

首先，这个...

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;
}

是错误的。您交换值，但永远不会交换

Vector

中的元素，而且由于 Java 的工作方式，一旦方法存在，交换就会丢失

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

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)

值应将范围括在您要搜索的

Vector

上（即，从索引

lo

到索引

hi

）。

p(ivot)

代表您想要用来确定如何最好地执行排序的核心逻辑的“基本”比较值。

我想重写它，但说实话，逻辑是错误的。您应该从仅接受

sort

的

Vector

方法开始，然后调用一个单独的

sort

方法，该方法接受

Vector

和

lo

（默认为

0

）和

hi

（默认为

Vector#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 中的快速排序算法实现
• 快速排序算法

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