QuickSort 不工作，认为交换是问题，免责声明我必须使用提供给我的快速排序方法

Question

try {
            for (i = 0; i < data.length; i++) {
                working[i] = data[i];
            }

            FileWriter fw3 = new FileWriter("quicksort.dat");

            long startTime3 = System.nanoTime();

            quickSort(working,0, working.length - 1);

            long endTime3 = System.nanoTime();

            long totalTime3 = endTime3 - startTime3;

            System.out.println("The time to complete the quick sort was :" + totalTime3 + " nano seconds");

            for (i = 0; i < working.length; i++) {
                fw3.write(Integer.toString(working[i]) + "\n");
            }
            System.out.println("The file has been sorted by quick sort and output to quicksort.dat \n");

            fw3.close();
        } catch (IOException e) {
            System.out.println(e);
        }




static void quickSort(int data[], int left, int right) {

        int i, j;
        int partition;
        if (right > left) {
            partition = data[right];
            i = left - 1;
            j = right;

            for (;;) {
                while (data[++i] < partition);
                while (data[--j] > partition);
                if (i >= j) {
                    break;
                }
                swap(data[i], data[j]);
                swap(data[i], data[right]);
                quickSort(data, left, i - 1);
                quickSort(data, i + 1, right);

            }
        }
    }

    static void swap(int left, int right) {
        int array[] = new int[19];
        int temp = array[left];
        array[left] = array[right];
        array[right]=temp;

这只是代码片段，整个程序是其他类型的。每次使用快速排序函数时，我都会收到一个越界错误。我使用 19 作为我的数组，因为那是文件的大小我已经尝试了 20 来查看它是否修复它但没有运气。

编辑：我在下面提供了更新的代码以反映所做的更改我仍然遇到越界错误。

    static void quickSort(int data[], int left, int right) {

    int i, j;
    int partition;
    if (right > left) {
        partition = data[right];
        i = left - 1;
        j = right;

        for (;;) {
            while (data[++i] < partition);
            while (data[--j] > partition);
            if (i >= j) {
                break;
            }
            swap(data, i, j);
            swap(data, i, right);
            quickSort(data, left, i - 1);
            quickSort(data, i + 1, right);

        }
    }
}


static void swap(int array[], int left, int right) {
     int temp = array[left];        
     array[left] = array[right];    
     array[right] = temp;          

}

Answer 1

您已将交换声明为：

void swap(int left, int right)

所以参数是数组的索引。

但是，你用 :

调用它

swap(data[i], data[j]);

因此您正在传递数组中的 VALUES。

尝试将调用更改为：

swap(i, j);

编辑添加：

必须指出的是，上述问题只是所提出的排序算法的一个问题。另一个问题是 swap 算法实际上并没有交换任何东西。它创建一个局部数组变量 array，对其进行操作，然后 returns（因此丢弃该局部变量）。

如果您的任务是输出一个排序的数字列表，并且必须使用提供的排序代码对数字进行排序 - 那么该任务是不可能的，因为提供的排序代码作为排序算法存在无可救药的缺陷；它不会排序（正如您自己发现的那样），并且与快速排序的正确实现相比存在明显的严重问题（例如，您可以与此处的答案进行比较：）

编辑以添加以下修改后的代码：

修改后的排序代码仍然无可救药地被破坏了。它不是 QuickSort 的正确实现，仍然无法正确排序。

例如，我试过运行最后一个元素是最大的 :

int data[] = {23, 8, 19, 35, 2, 12, 7, 64 };

结果：没有排序 - 该方法直接用 i==7 和 j==6 命中了 if (i >= j) {break;}，所以什么也没做。

相比之下，我上面链接的答案中的方法排序正确，因此您可以将给出的方法与该方法或其他已建立的文章进行比较（例如，在互联网上搜索 java quicksort, 周围有很多)

Answer 2

正如 'racraman' 已经指出的那样，排序肯定需要修复。

尝试 re-implementing 具有以下方法签名的排序函数。

void sort(int[] arr, int leftIndex, int rightIndex) {
// swap code goes here
}

QuickSort 不工作，认为交换是问题，免责声明我必须使用提供给我的快速排序方法

QuickSort not working, think swap is the issue, Disclaimer I must use the quicksort method provided to me

java

arrays

quicksort

swap