快速排序算法(递归)

Question

我根据我在youtube上观看的算法的可视化演示，制作了一个快速排序算法，但我的递归根本不起作用。:(如果我注释掉这两行，

quicksort(array,0,start-1);
quicksort(array,start+1,temp);

。。程序没有崩溃，输出变为2,1,3,5,4，这是部分正确的。但当它进入递归时，它会崩溃。在整个while循环之后，start与end相同。

#include <stdio.h>
#include <conio.h>

void swap(int *a, int *b){

int temp = *a;
*a = *b;
*b = temp;
}

void quicksort(int *array, int start, int end){

int pivot = start;
int temp = end;     
while(start != end){

if(pivot==start){
    if(array[pivot] > array[end]){
    swap(&array[end],&array[pivot]);
    pivot = end;
    start++;
    }
    else
    end--;
}
else{
if(array[pivot] < array[start]){
    swap(&array[start],&array[pivot]);
    pivot = start;
    end--;
}  
else
start++;   

}               
}

quicksort(array,0,start-1);
quicksort(array,start+1,temp);
}




main(){

int x[5] = {3,1,5,2,4};
int i;
quicksort(x,0,4);
for(i=0;i<5;i++)
printf("%d ", x[i]);
getch();
}

Answer 1

缺少的是取消算法的点。如果检查函数的控制流，您将看到在应用程序可以遍历此函数的每条路径上，都会再次调用quicksort函数。发现你什么时候做完了很简单。您只需要退出函数，而不需要再次调用quicksort，以防参数start和end相等。这应该能起到作用。

Answer 2

对于crasher:您的代码缺少递归的终止条件。这意味着即使输入范围为空，您仍然可以输入递归调用(带有数组的负索引，这可能是导致崩溃的原因)。您应该添加如下条件

if(there's at most 1 element in the input range)
  return; // already sorted

Answer 3

QuickSort Algorithm:

    - QuickSort( A[], l, r)
      - P = A[l] // Select pivot as the beginning element from array or you can do better //with good pivots.
      - i = l + 1 // index i to be next of pivot
      - for j = l + 1 to r
         - if A[j] < P
           - swap (A[j], A[i])
           - increment i
         - end if
     - end for
     - swap (A[i-1], A[l]);
     -- Call recursive on left partitioned array
     -- Call recursive on right partitioned array.




// QuickSort_2.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#define ARR_SIZE            200
#define PR_ARR_SIZE         200
unsigned int input_arr[ARR_SIZE];

void swap(unsigned int *a, unsigned int *b)
{
    unsigned int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}

void print_input(unsigned int input[], unsigned int l, unsigned  int n)
{
    unsigned int i;
    for (i = l; i < n; i++)
        printf("%d ", input[i]);
    printf("\n");
}

void QuickSort(unsigned int input[], unsigned int l, unsigned int r)
{
    unsigned int i = l + 1, j;
    unsigned int pivot = input[l];
    if (l + 1 < r) {
        for (j = l + 1; j < r; j++) {
            if (input[j] < pivot) {
                swap(&input[j], &input[i]);
                i++;
            }
        }
        swap(&input[i - 1], &input[l]);

        QuickSort(input, l, i);
        QuickSort(input, i, r);
    }
}


int _tmain(int argc, _TCHAR* argv[])
{
    unsigned int i = 0;
    unsigned int val;
    FILE *fp;

    errno_t err = fopen_s(&fp, "IntegerArray.txt", "r+");
    if (err) {
        printf("unable to open a file\n");
        return -1;
    }
    while (fscanf_s(fp, "%ld\n", &val) != EOF) {
        input_arr[n++] = val;
    }

    print_input(input_arr, 0, n);
    QuickSort(input_arr, 0, n);
    print_input(input_arr, 0, n);

    return 0;
}

Put these values in "IntegerArray.txt" file and 

2
3
4
5
6
10
11
12
1
17
18
19
20
7
8
9
13
14
15
16