Java快速排序帮助

我想在java中实现快速排序。但是，我正在经历奇怪的行为。我的算法适用于70个或更少的项目，但以上任何项目都会使整个Java应用程序冻结。这是函数调用的限制还是我正在使用的内存量？Java快速排序帮助

我通常不使用快速排序，所以我的实现可能有点过，但我想一般的逻辑是正确的：

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); 

     }

任何帮助是极大的赞赏。

来源

2011-06-13 Dave

调试你的应用程序。使用IDE调试器。 – 2011-06-13 03:33:35

我认为这是作业，否则你会使用'Arrays.sort（）;' – 2011-06-13 08:08:17

在后续仔细2线看看：

this.QuickSort(0, LowerPoint - 1); 
    this.QuickSort(HigherPoint + 1, end);

有什么东西对他们不太合适。

来源

2011-06-13 04:00:56 greatwolf

你是对的！ this.QuickSort（start，LowerPoint - 1）;解决了这个问题。非常感谢！ – Dave 2011-06-13 04:07:04

我还想补充一点，在中间循环中并不存在相同的情况。因此，大量元素产生相同数字并导致无限循环的机会更大。 – Dave 2011-06-13 05:05:04

@Dave如果你正在排序的数组中存在重要的重复会导致无限循环，那么我想你有更多的错误来锤炼出来。分区时应该发生的性能下降到O（N^2）。但是，您可以修改qsort来处理这种情况，因此更糟 - 不会触发。 – greatwolf 2011-06-13 05:16:16

我实现了我的最后一次转让的快速排序，这里是我的代码它可以帮助你：

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; 
}

来源

2011-06-13 03:14:10

Java快速排序帮助

回答

相关问题