c - 快速排序并不是每次都排序

Question

我的快速排序有问题。对于某些值它有效，但对于其他值则无效。例如，当第一个值小于最后一个值时，它不起作用。我不知道出了什么问题。这是代码:

#include <stdio.h>
#include <time.h>

#define lenght_max 1000000
int x;
int tablica[lenght_max];
int q;

int Partition(left, right) {

    int tmp;
    int i;
    int j;

    i = -1;
    j = 0;

    x = tablica[right];
    i = left - 1;

    for(j = left; j < right; j++){
      if(tablica[j] <= x) {
        i++;
        tmp = tablica[i];
        tablica[i] = tablica[j];
        tablica[j] = tmp;
      }
    }

    return i + 1;
}

void Quicksort(left, right) {    
    if(left < right){ 
      q = Partition(left, right);
      Quicksort(left , q - 1);
      Quicksort(q + 1, right);
    }
}

int main(void) {

  int i;
  int temporary;
  int left;
  int right;

  printf("Witaj uzytkowniku. To jest program preferujacy sortowanie szybkie - quicksort.\n");
  printf("Podaj, ile liczb chcialbys posortowac: ");
  scanf("%i", &temporary);

  printf("Podaj liczby do sortowania: \n");

  for(i = 0; i < temporary; i++)
    scanf("%d", &tablica[i]);

    left = 0;
    right = temporary - 1;
    x = temporary / 2;

  Quicksort(left, right);

  printf("\nPROCES:\n");

  for(i = 0; i < temporary; i++)
    printf("%d\n", tablica[i]);

  return 0;
}

Answer 1

如果我没有忽略这个问题，在我看来，您似乎忘记将枢轴与大于Partition末尾的枢轴的第一个元素交换。修复应该很简单，只需添加:

    tmp            = tablica[i+1];
    tablica[i+1]   = tablica[right];
    tablica[right] = tmp;

在 Partition 内的 return i + 1; 语句之前。