我是一名CS学生，对于一项作业，我的教授允许我们在线使用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);
}
}
如果我没看错的话：
你
public static int partitaion(int[] arr, int start, int end)
使用"int start"作为不会更改的参数。然后你返回这个 int 并将其交给 "int 分区"。
之后，你做你的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","",}
如果您符合以下条件，则完全取决于您：
- 明白我的意思
- 真的必须在一个数组中完成它(没有更容易的方式(
- 可以使用我给定的信息