快速排序不正确

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。