c# quicksort 算法不继续

Question

我刚刚在 C# 中实现了快速排序，但后来我遇到了这样的问题。当我使用我的函数时

static void QS(int[] arr, int left, int right){
        int pivot = left;
        int temp;
        int i = left + 1;
        int j = left + 1;

        do {    
        if (arr [i] < arr [pivot]) {
                temp = arr [j];
                arr [j] = arr [i];
                arr [i] = temp;
                i++;
            }
            else{}
        j++;
        }while(j<=right);

            temp = arr [pivot];
            arr [pivot] = arr [i - 1];
            arr [i - 1] = temp;
}

对于数组

int[] arr = { 12, 9, 19, 8, 7, 13, 10, 71, 18, 34, 90, 15, 3 };

我得到这样的结果： 9, 12, 19, 8, 7, 13, 10, 71, 18, 34, 90, 15, 3。在这上面花了几个小时我仍然不太明白为什么索引 i 不继续。可能问题比我想象的要多。

我省略了递归调用以专注于函数本身。我正在使用这个伪代码：

Partiton(A,l,r)  
//[input corresponds to A[l…r]]  
p:=A[l]  
i:=l+1  
  for  
   j=l+1 to r  
    if A[j] < p  
    swap A[j] and A[i]  
    i:=i+1  
swap  A[l] and A[i‐1]

Answer 1

几件事：

您缺少移动索引指针的 do while 循环中的比较（while 循环），以及使快速排序真正起作用的递归调用。记住当你交换你的值时，递增 i 和递减 j。其次，对于值 i 和 j，不要将 1 添加到这些索引，因为它们可能会给您带来越界错误，我假设您将像这样调用快速排序：quicksort(arr, 0, arr.Length - 1); .最后，请选择你的主元作为中值，因为它会产生更快的排序时间和结果，而不是选择数组中的第一个值。

我会这样写：

   quicksort(arr[], begin, end)
   {
       pivot = (begin + end) / 2
       left = begin;
       right = end;
   while (left <= right)
   {
      while (arr[left] < pivot)
      {
          left++;
      }
      while (arr[right] > pivot)
      {
          right--;
      }
      if (left <= right)
      {
          swap(arr, left, right);
          left++;
          right--;
      }
  }
   //do your recursive call logic here
 }

c# quicksort 算法不继续

c# quicksort algorithm doesnt proceed

c#

arrays

sorting

algorithm

quicksort