c快速排序算法无法继续

本文关键字：继续 算法 快速排序 | 更新日期: 2024-10-20 08:49:31

我刚刚在c#中实现了quicksort，但后来我遇到了这样一个问题。当我使用功能时

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

我得到的结果是这样的：CCD_ 1。花了几个小时，我仍然不太明白为什么索引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]

c快速排序算法无法继续

几件事：

do-while循环中移动索引指针的比较（while循环）以及使quicksort实际工作的递归调用丢失了。请记住，当您交换值时，递增i和递减j。其次，对于值i和j，不要在这些索引中加1，因为它们可能会给您带来越界错误，我想您将调用quicksort，如下所示：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
 }
相关文章：