时间戳

首页 > 解决方案 > 编写一个只有 1 个数组的 Java 快速排序函数

java - 编写一个只有 1 个数组的 Java 快速排序函数

问题描述

我是一名计算机科学专业的学生，​​对于一项作业，我的教授允许我们在线使用 QuickSort 程序中的代码，并将其与我们项目中的排序文件同步。我有以下完整：

public class QuickSort extends SortAlgorithm
{

        @Override
    public String getName()
    {
        return "Quick Sort";
    }

        @Override
    public void sort(int[] data)
    {
            // Using code from: https://www.programcreek.com/2012/11/quicksort-array-in-java/
            // Making their code work with mine
            int[] arr = data;
            int start = data[0];
            int end = data[1];

            int partition = partition(arr, start, end);

            if(partition-1>start) {
                 quickSort(arr, start, partition - 1);
            }

            if(partition+1<end) {
                 quickSort(arr, partition + 1, end);
            }
        }

        public static int partition(int[] arr, int start, int end){
        int pivot = arr[end];

        for(int i=start; i<end; i++){
            if(arr[i]<pivot){
                int temp= arr[start];
                arr[start]=arr[i];
                arr[i]=temp;
                start++;
            }
        }

        int temp = arr[start];
        arr[start] = pivot;
        arr[end] = temp;

        return start;
        }  
}

我唯一的问题是如何改变

if(partition-1>start)

和

if(partition+1>start)

以便他们与程序的其余部分一起工作。我对程序中的递归很好，但是原始代码使用了我不能在我的中使用的快速排序参数。关于如何解决它的任何建议？

编辑：我最终切换到一个稍微接近的程序。这是我到目前为止所拥有的：

@Override
    public void sort(int[] arr) {
            int left = arr[0];
            int right = arr[arr.length];

            quickSort(arr, left, right);

        }

        public void quickSort(int[] arr, int left, int right) {

        int pivotIndex = left + (right - left) / 2;
        int pivotValue = arr[pivotIndex];

        int i = left, j = right;

        while(i <= j) {

            while(arr[i] < pivotValue) {
                i++;
            }

            while(arr[j] > pivotValue) {
                j--;
            }

            if(i <= j) {
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
                i++;
                j--;
            }

            if(left < i) {
                quickSort(arr, left, j);
            }

            if(right > i) {
                quickSort(arr, i, right);
            }

        }

标签： java

解决方案

如果我没看错：

您的

public static int partitaion(int[] arr, int start, int end)

使用“int start”作为不会更改的参数。然后你返回这个 int 并把它交给“int partition”。

之后，您执行 if 语句：

例子：

int start = 1;
int partition = partition(arr, start, end);
// partition() returns start without a change
// if now replaced with the values
if ((1-1) > 1) { /* your code */ }

所以基本上你永远不会进入第一个 if 语句。我建议您不要复制代码，只需在 Google 上搜索 Quicksort 的工作原理。如果您的枢轴元素只是每个小数组的第一个，那真的很简单。

我相信您可以在一开始通过某种算法来计算原始数据所具有的数字所给出的数组的大小。

例子：

您的数组由 10 个元素组成

1 0 2 9 3 8 5 7 4 6

他们会这样排序：

1 0 2 9 3 8 5 7 4 6

0 1 2 9 3 8 5 7 4 6 // 1 sorted; 1 = pivot
  |
0 | 2 9 3 8 5 7 4 6 // 0 sorted; 0 = pivot... u get it
| |  
| | 2 9 3 8 5 7 4 6 // 2 sorted; 2 = pivot... u get it
| | |
| | | 3 8 5 7 4 6 9 // 9 sorted
| | |             |
| | | 3 8 5 7 4 6 | // 3 sorted
| | | |           |
| | | | 5 7 4 6 8 | // 8 sorted
| | | |         | |
| | | | 4 5 7 6 | | // 5 sorted
| | | |   |     | |
| | | | 4 | 7 6 | | // 4 sorted
| | | | | |     | |
| | | | | | 6 7 | | // 7 sorted
| | | | | |   | | | 
| | | | | | 6 | | | // 6 sorted
| | | | | | | | | |         
0 1 2 3 4 5 6 7 8 9 // all sorted

因此，为了在一个数组中发生这种情况，您需要 10 个空格和每个数字或迷你数组的分隔符。

所以：

{"","","","","","","","","","", "1","0","2","9","3","8","5","7","4","6"}

但是您最多需要 11 个分隔符：

{"","","","","","","","","","", "","1","","0","","2","","9","","3","","8","","5","","7","","4","","6","",}

如果您满足以下条件，完全取决于您：

  1. 明白我的意思
  2. 真的必须在一个数组中完成（没有更容易的方法）
  3. 可以使用我给定的信息

推荐阅读