快速排序算法（递归）

我做了一个快速排序算法，在我看到的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(); 
}

来源

2012-04-05 Xegara

我提出的代码的修改.. 我添加如果（开始==结束）返回; //用于终止条件。但是当它进入快速排序（array，start + 1，temp）的第二个递归时会遇到错误; – Xegara 2012-04-05 10:58:31

缺少的是取消算法。如果你检查你的功能的控制流程，你会发现在每个路径上应用程序可以通过这个函数再次调用quicksort函数。查找完成时间很简单。在参数start和end相等的情况下，您只需要退出功能而不需要再次调用quicksort。这应该够了吧。

来源

2012-04-05 10:48:52 Nitram

我做了代码的修订， – Xegara 2012-04-05 10:57:58

我不认为第一次递归调用的参数也是正确的。（我没有验证剩下的部分，但如果'start'不是0，那么第一次调用通过一个小于我们正在工作的段的下限。） – 2012-04-05 11:21:33

谢谢:)嗯..我可以不会想到任何其他方式，因为快速排序算法是一种分而治之的算法，一旦第一个轴被排序（通常结束于中间），快速排序将再次出现在轴的左侧和右侧，所以直到列表排序.. :) – Xegara 2012-04-05 12:06:31

到了不速之客：您的代码缺少递归终止条件这意味着，即使输入范围为空。，你仍然输入递归调用（对数组有负面指示，这可能导致崩溃），你应该添加如

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

来源

2012-04-05 10:48:16 jpalecek

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-12 23:34:53 user1596193

快速排序算法（递归）

回答

相关问题