java - java中的快速排序代码运行不正常?
问题描述
我现在被困在这个问题上......数组没有被正确排序并且结尾没有递减有人可以帮助我在这里犯什么错误吗?我尝试并寻找了几个小时,但无法准确找到错误。您可以在输出中清楚地看到 end 没有递减,并且数组的排序不正确,因为 17 是最后一个元素,而 45 是倒数第二个元素。还有 ArrayOutOfBounds 的错误。
代码:
public class Program{
public static void main(String[] args) {
int [] ar={4,5,6,3,10,12,45,17};
int l=0;
int h=ar.length-1;
quickSort(ar,l,h);
}
static void quickSort(int [] arr,int lb,int ub){
int z;
if(lb<ub){
z=partition(arr,lb,ub);
quickSort(arr,lb,z-1);
quickSort(arr,z+1,ub);
}
for(int i=0;i<arr.length;i++){
System.out.println(arr[i]);
}
}
static int partition(int [] a,int lb,int ub){
int pivot=a[lb];
int start=lb;
int end=ub;
//If I put end=ub-1 here then it shows index-1.
//so I have not options left to do that the Error is coming eitherway.
System.out.println("start is "+start);
System.out.println("End is "+end);
while(start<end){
while(a[start]<=pivot){
start++;
}
while(a[end]>pivot){
end--;
}
if(start<end){
int temp0=a[start];
int temp1=a[end];
a[start]=temp1;
a[end]=temp0;
}
}
int temp2=a[lb];
int temp3=a[end];
a[lb]=temp3;
a[end]=temp2;
return end;
}
}
output:
start is 0
End is 7
3
4
6
5
10
12
45
17
start is 2
End is 7
3
4
5
6
10
12
45
17
start is 4
End is 7
3
4
5
6
10
12
45
17
start is 5
End is 7
3
4
5
6
10
12
45
17
start is 6
End is 7
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 8 out of bounds for length 8
at Program.partition(Program.java:35)
at Program.quickSort(Program.java:16)
at Program.quickSort(Program.java:18)
at Program.quickSort(Program.java:18)
at Program.quickSort(Program.java:18)
at Program.quickSort(Program.java:18)
at Program.main(Program.java:9)
解决方案
class QuickSort
{
int partition(int arr[], int low, int high)
{
int pivot = arr[high];
int i = (low-1); // index of smaller element
for (int j=low; j<high; j++)
{
// If current element is smaller than the pivot
if (arr[j] < pivot)
{
i++;
// swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// swap arr[i+1] and arr[high] (or pivot)
int temp = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp;
return i+1;
}
void sort(int arr[], int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[pi] is
now at right place */
int pi = partition(arr, low, high);
// Recursively sort elements before
// partition and after partition
sort(arr, low, pi-1);
sort(arr, pi+1, high);
}
}
/* A utility function to print array of size n */
static void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i]+" ");
System.out.println();
}
// Driver program
public static void main(String args[])
{
int arr[] = {4,5,6,3,10,12,45,17};
int n = arr.length;
QuickSort ob = new QuickSort();
ob.sort(arr, 0, n-1);
System.out.println("sorted array");
printArray(arr);
}
}
输出:排序数组 3 4 5 6 10 12 17 45
上面的代码适用于您定义的数组,您可以使用此代码,如果您仍然对快速排序感到困惑,您可以在评论中提问。
推荐阅读
- blazor - Blazor 页面中的加载指示器
- azure - Powershell + Azure 应用服务 + Azure 容器注册表
- python-3.x - 什么是使用 if 函数终止脚本的脚本内代码(当值不为真时)?
- arcgis - 在鼠标位置 arcgis onlne 下的图层中查找多个特征
- python - 如何创建“if and”语句以在 Python 中使用 xlsxwriter 有条件地格式化一列单元格
- javascript - 如何检查表单中所需的单选和复选框输入,然后在选中或未选中时显示消息?
- linux - 为什么解压缩不会在 Docker 映像中停止
- git - 在创建 PR 合并从版本到主版本期间报告了错误的“文件已更改”的 github Web UI
- python - 如何旋转带注释的 seaborn 热图数据和图例?
- java - 如何在springframework中查找注释文档