计算快速排序比较 [英] counting quicksort comparisions
本文介绍了计算快速排序比较的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
嘿
i我仍然是编程的初学者,但我正在尝试编写一个计算快速排序计划中比较次数的程序
这是我的代码
hey
i am still a beginner at programming but i am trying to write a program that counts the number of comparisons in a quicksort program
this is my code
package algo_quicksort;
public class Algo_quicksort {
public static int partition(int[]A,int p,int r){
int x=A[p];
int i=p+1;
int temp;
for(int j=p+1;j<r;j++){
if(A[j]<x){//if A[j] is bigger than the pivot do nothing
temp=A[j];
A[j]=A[i];
A[i]=temp;
i++;
}
}
temp=A[p];
A[p]=A[i-1];
A[i-1]=temp;
return i-1;
}
public static long quickSort(int[]A,int startPos,int length){
if(length==1){
return 0;
}
else{
if(startPos<length){
int pivot= partition(A,0,length);
quickSort(A,startPos,pivot+1);
quickSort(A, pivot+2,length);
return length-startPos-1;
}
else{
return 0;
}
}
}
public static void main(String[] args) {
int a[]={3,2,4};
System.out.println("# of comparisons is: " +quickSort(a,0,a.length));
System.out.println("A[] after quicksort is: ");
for(int i=0;i<a.length;i++){
System.out.print(a[i]+" ");
}
}
}
它适用于任何大小的数组3或更少
但如果它比任何更大它在递归调用时给我一个stackoverflow异常
i尝试调试我的代码但是无法弄清楚它出错的地方
i会感激我得到的任何帮助^ _ ^
it works perfectly for any array of size 3 or less
but if it is any bigger than that it gives me a stackoverflow exception at the recursive call
i tried debugging my code but could not figure out where it's going wrong
i would appreciate any help i get ^_^
推荐答案
你的快速排序在很多地方都是错误的。你为什么不复制别人的快速实施方案: http://www.algolist.net/Algorithms/Sorting/Quicksort [ ^ ]
Your quicksort is simply buggy in many places. Why don't you copy someone else' quicksort implementation: http://www.algolist.net/Algorithms/Sorting/Quicksort[^]
>
这篇关于计算快速排序比较的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文