1

我从我观看的 youtube 中算法的视觉呈现中制作了一个快速排序算法，但我的递归根本不起作用。:( 如果我注释掉这两行，

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

..程序没​​有崩溃，输出变为2,1,3,5,4，这部分正确..但是当它进入递归时它崩溃了。在整个while循环之后，开始与结束相同..

#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();
}
4

3 回答 3

2

缺少的是取消算法的重点。如果您检查您的函数的控制流，您会看到在应用程序可以通过该函数的每条路径上，该quicksort函数都被再次调用。找出何时完成很简单。如果参数和相等，您只需要退出函数而无需再次调用。这应该够了吧。quicksortstartend

于 2012-04-05T10:48:52.800 回答
0

致崩溃者：您的代码缺少递归的终止条件。这意味着即使输入范围为空，您仍然可以输入递归调用（数组的负索引，这可能导致崩溃）。您应该添加条件，例如

if(there's at most 1 element in the input range)
  return; // already sorted
于 2012-04-05T10:48:16.700 回答
0 
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
于 2013-02-12T23:34:53.420 回答