快速排序不正確

Question

對不起，我知道有關於quicksort的一堆問題，但有一個錯誤，我不能找到。

public static void QuickSort(int[] sort) 
{ 
    QuickSort(sort, 0, sort.Length - 1); 
} 

private static void QuickSort(int[]sort, int first, int last) 
{ 
    int i = first; 
    int j = last; 
    int pivot = (i + j)/2; 
    int temp; 

    while(i <= j) 
    { 
     while(sort[i] < sort[pivot]){i++;} 
     while(sort[j] > sort[pivot]){j--;} 

     if(i <= j) 
     { 
      temp = sort[i]; 
      sort[i] = sort[j]; 
      sort[j] = temp;    
      i++; 
      j--; 
     } 

    } 

    if(first < j)QuickSort(sort, first, j); 
    if(last > i)QuickSort(sort, i, last); 
} 

這似乎不錯，但排序這個數組

int[] sortMe = {2,5,6,4,8,9,6,3,21,2,5,4,8,9,6,5,46,6,3}; 

這樣的：

2,2,3,4,3,4,5,5,6,6,5,6,6,8,8,9,9,21,46 

，而不是明顯的正確的順序。

Answer 1

的問題是，你計算pivot爲index，然後將其與sort陣列值進行比較，而要修改的最while循環內的sort陣列。 Pivot應該是指向sort數組索引的最外側while循環的初始值，稍後將其與該值進行比較，而不是基於索引的sort數組。

你的方法應該是：

public static void Quicksort(int[] sort, int first, int last) 
{ 
    int i = first, j = last; 
    int pivot = sort[(first + last)/2]; //change here 

    while (i <= j) 
    { 


     while (sort[i] < pivot) //Change here 
     { 
      i++; 
     } 

     while (sort[j] > pivot) //Change here 
     { 
      j--; 
     } 

     if (i <= j) 
     { 
      // Swap 
      int tmp = sort[i]; 
      sort[i] = sort[j]; 
      sort[j] = tmp; 

      i++; 
      j--; 
     } 
    } 

    // Recursive calls 
    if (first < j) 
    { 
     Quicksort(sort, first, j); 
    } 

    if (i < last) 
    { 
     Quicksort(sort, i, last); 
    } 
} 

Answer 2

我覺得你pivot選擇是錯誤的。

退房http://en.wikipedia.org/wiki/Quicksort#Choice_of_pivot

在快速排序的非常早期的版本中， 分區的最左邊的元素往往會被選擇作爲樞轉元件。不幸的是， 這會導致已排序陣列上的最壞情況行爲，這是一種相當常見的用例。這個問題是很容易通過選擇 爲無規指數爲樞軸，選擇 分區的選擇的 第一位數中間索引或（特別是對於較長的分區）分區爲的，中間的和最後一個元素解決樞。

只要改變你的int pivot = (i + j)/2;到int pivot = first;

static void Main(string[] args) 
    { 
     int[] sortMe = { 2, 5, 6, 4, 8, 9, 6, 3, 21, 2, 5, 4, 8, 9, 6, 5, 46, 6, 3 }; 
     QuickSort(sortMe, 0, sortMe.Length - 1); 

     foreach (var item in sortMe) 
      Console.Write(item + " "); 
    } 

    private static void QuickSort(int[] sort, int first, int last) 
    { 
     int i = first; 
     int j = last; 
     int pivot = first; 
     int temp; 

     while (i <= j) 
     { 
      while (sort[i] < sort[pivot]) { i++; } 
      while (sort[j] > sort[pivot]) { j--; } 

      if (i <= j) 
      { 
       temp = sort[i]; 
       sort[i] = sort[j]; 
       sort[j] = temp; 
       i++; 
       j--; 
      } 

     } 

     if (first < j) QuickSort(sort, first, j); 
     if (last > i) QuickSort(sort, i, last); 
    } 

輸出會;

2 2 3 3 4 4 5 5 5 6 6 6 6 8 8 9 9 21 46 

這是DEMO。