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快速排序幫助

回答

相關問題