java - 编写仅包含 1 个数组的 Java QuickSort 函数

Question

我是一名计算机科学学生，在一项作业中，我的教授允许我们在线使用 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);
            }

        }

Answer 1

如果我没看错的话:

你的

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

使用“int start”作为不会更改的参数。然后返回这个 int 并将其交给“intpartition”。

之后执行 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 语句。我建议你不要复制代码，只需谷歌一下快速排序的工作原理即可。如果您的主元元素只是每个小数组的第一个，那么这确实很简单。

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

示例:

您的数组由 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. 可以使用我提供的信息