Java Quicksort帮助。
|
我试图在Java中实现快速排序。但是，我遇到了奇怪的行为。我的算法适用于70项或更少的项目，但以上任何因素会使整个Java应用程序冻结。这是对函数调用的限制还是我正在使用的内存量？
我通常不使用quicksort，所以我的实现可能会有点差，但是我认为总体而言逻辑是正确的：
int data[];
public void QuickSort(int start, int end)
{
if(start == end || end < start || end > data.length)
{
return;
}
//find the pivot
int pivotPos = (int)(start + (end - start) / 2);
int temp;
//switch the pivot to the end
temp = data[pivotPos];
data[pivotPos] = data[end];
data[end] = temp;
int LowerPoint = start;
int HigherPoint = end - 1;
//loop through and move low values down
//and high values up
while(LowerPoint != HigherPoint)
{
while(data[LowerPoint] < data[end] && LowerPoint < HigherPoint)
{
LowerPoint++;
}
while(data[HigherPoint] > data[end] && LowerPoint < HigherPoint)
{
HigherPoint--;
}
if(LowerPoint != HigherPoint)
{
temp = data[HigherPoint];
data[HigherPoint] = data[LowerPoint];
data[LowerPoint] = temp;
}
}
//one last check to make sure we don\'t swap the pivot with a lower value
//if this value is lower than increment our pointers up so we guarentee
//the swap with a higher value
if(data[LowerPoint] < data[end])
{
LowerPoint++;
HigherPoint++;
}
//place the pivot back to the middle of the list
//by swapping it with the higher point
temp = data[HigherPoint];
data[HigherPoint] = data[end];
data[end] = temp;
this.QuickSort(0, LowerPoint - 1);
this.QuickSort(HigherPoint + 1, end);
}
没有找到相关结果
已邀请:
2 个回复
郡豪靠暖
this.QuickSort(0, LowerPoint - 1); this.QuickSort(HigherPoint + 1, end);涸坍饺
public static void quickSort(int[] data, int first, int n) { int p, n1, n2; if(n > 1) { p = partition(data, first, n); n1 = p - first; n2 = n - n1 - 1; quickSort(data, first, n1); quickSort(data, p+1, n2); } } public static void quickSort(int[] data) { quickSort(data, 0, data.length); } private static int partition(int[] A, int first, int n ) { int right = first + n - 1; int ls = first; int pivot = A[first]; for(int i = first+1; i <= right; i++) { if(A[i] <= pivot) // Move items smaller than pivot only, to location that would be at left of pivot { ls++; swap(A, i, ls); } } swap(A, first, ls); return ls; } private static void swap(int[] data, int pos1, int pos2) { int temp = data[pos1]; data[pos1] = data[pos2]; data[pos2] = temp; }