快速排序输出不一致

Question

我想体验快速排序的最坏情况。因此，我按降序生成一个数组。按快速排序进行排序后，数组的第一个元素有时变成垃圾，而有时变为0。当第一元件成为垃圾的所有元素的顺序向上滑动，第二元素变成0，第三元件变为1等 这里我的代码：

void generateDescendingArray(int *arr, int n) { 

    for(int i = n - 1; i >= 0; i--) { 
     arr[n-i-1] = i; 
    } 
} 

void quickSort(int *A, int start, int end) { 
    if(end > start) { 
     int s = partition(A, start, end); //split position 
     quickSort(A, start, s - 1); //sort before the split 
     quickSort(A, s + 1, end); //sort after the split 
    } 
} 
int partition(int *A, int start, int end) { 

    int pivot = A[start]; 
    int i = start; 
    int j = end + 1; 

    do { 

     do { i++; 
     } while(pivot > A[i]); 

     do { j--; 
     } while(pivot < A[j]); 

     swap(&A[i], &A[j]); 

    } while(j > i); 
    swap(&A[i], &A[j]); //undo last swap when i >= j 
    swap(&A[start], &A[j]); 

    return j; 
} 
int main() { 
    int A[n]; 
    generateDescendingArray(A, n); 
    quickSort(A, 0, n); 

    return 0; 
} 

Answer 1

作为诊断在评论中，你需要：

• 以防扫描与空闲分区通过检查i和j在partition()中循环之前。
• 拨打quickSort()并输入正确的索引 - 0和n-1。

实验表明do { … } while (j > i);环配方也干净地工作。

这些变化导致：

#include <stdio.h> 

static inline void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; } 
static int partition(int *A, int start, int end); 

static 
void generateDescendingArray(int *arr, int n) { 

    for(int i = n - 1; i >= 0; i--) { 
     arr[n-i-1] = i; 
    } 
} 

static 
void quickSort(int *A, int start, int end) { 
    if(end > start) { 
     int s = partition(A, start, end); //split position 
     quickSort(A, start, s - 1); //sort before the split 
     quickSort(A, s + 1, end); //sort after the split 
    } 
} 

static 
int partition(int *A, int start, int end) { 

    int pivot = A[start]; 
    int i = start; 
    int j = end + 1; 

    while (i < j) 
    { 

     do { i++; 
     } while(pivot > A[i]); 

     do { j--; 
     } while(pivot < A[j]); 

     swap(&A[i], &A[j]); 

    } 
    swap(&A[i], &A[j]); //undo last swap when i >= j 
    swap(&A[start], &A[j]); 

    return j; 
} 

enum { NUM_PER_LINE = 10 }; 

static void print_data(const char *tag, const int *A, int num) 
{ 
    printf("%s (%d):\n", tag, num); 
    const char *pad = ""; 
    int i; 
    for (i = 0; i < num; i++) 
    { 
     printf("%s%d", pad, A[i]); 
     pad = " "; 
     if (i % NUM_PER_LINE == NUM_PER_LINE - 1) 
     { 
      putchar('\n'); 
      pad = ""; 
     } 
    } 
    if (i % NUM_PER_LINE != 0) 
     putchar('\n'); 
} 

int main(void) { 
    for (int n = 1; n < 24; n++) 
    { 
     int A[n]; 
     generateDescendingArray(A, n); 
     print_data("Unsorted", A, n); 
     quickSort(A, 0, n-1); 
     print_data("Sorted", A, n); 
    } 

    return 0; 
} 

的代码产生正确的输出，AFAICS：

Unsorted (1): 
0 
Sorted (1): 
0 
Unsorted (2): 
1 0 
Sorted (2): 
0 1 
Unsorted (3): 
2 1 0 
Sorted (3): 
0 1 2 
Unsorted (4): 
3 2 1 0 
Sorted (4): 
0 1 2 3 
… 
Unsorted (21): 
20 19 18 17 16 15 14 13 12 11 
10 9 8 7 6 5 4 3 2 1 
0 
Sorted (21): 
0 1 2 3 4 5 6 7 8 9 
10 11 12 13 14 15 16 17 18 19 
20 
Unsorted (22): 
21 20 19 18 17 16 15 14 13 12 
11 10 9 8 7 6 5 4 3 2 
1 0 
Sorted (22): 
0 1 2 3 4 5 6 7 8 9 
10 11 12 13 14 15 16 17 18 19 
20 21 
Unsorted (23): 
22 21 20 19 18 17 16 15 14 13 
12 11 10 9 8 7 6 5 4 3 
2 1 0 
Sorted (23): 
0 1 2 3 4 5 6 7 8 9 
10 11 12 13 14 15 16 17 18 19 
20 21 22 

Answer 2

使用霍尔的分区方案：

int partition(int *A, int start, int end) { 

    int i = start - 1; 
    int j = end + 1; 
    int pivot = start; 

    while(1) { 
     while (A[++i] < A[pivot]); 
     while (A[--j] > A[pivot]); 

     if (i >= j) { 
     return j; 
     } 
     // swap A[i] and A[j] 
    } 

    return j; 
} 

void quickSort(int *A, int start, int end) { 
    if(start < end) { 
     int s = partition(A, start, end); 
     quickSort(A, start, s); 
     quickSort(A, s + 1, end); 
    } 
} 

int main() { 
    ... 
    quickSort(A, 0, n - 1); // CHANGED to n - 1 because you already have + 1 in partition 
}