C语言递归快速排序算法实现

jack1007

递归函数quicksort里面没有判断左右范围大小，导致无穷递归，纠结了半天。闲来没事，写简单的数据结构，学学编程。

1. #include <stdio.h>
   
2. 
   
3. int quichsort(int *arr, int left, int right);
   
4. void swap(int *a, int *b);
   
5. 
   
6. int
   
7. main()
   
8. {
   
9.   int arr[] = {9, 2, 1, 4, 3, 15, 11, 6, 7};
   
10.   int arr_len = sizeof(arr) / sizeof(arr[0]);
    
11.   int i;
    
12.   for (i = 0; i < arr_len; i++) {
    
13.     printf("%d ", arr[i]);
    
14.   }
    
15.   printf("\n");
    
16.   quicksort(arr, 0, arr_len - 1);
    
17.   for (i = 0; i < arr_len; i++)
    
18.     printf("%d ", arr[i]);
    
19.   printf("\n");
    
20. 
    
21.   return 0;
    
22. }
    
23. 
    
24. int
    
25. quicksort(int *arr, int left, int right)
    
26. {
    
27.   int i = left;
    
28.   int j = right;
    
29.   int one_key = arr[left];
    
30.   if (i >= j) //avoid infinity recursion
    
31.     return 0;
    
32.   while (i != j) {
    
33.   //accomplish one quicksort
    
34.     while (arr[j] > one_key) {
    
35.       j--;
    
36.     }
    
37.     swap(&arr[j], &one_key);
    
38.     while (arr[i] < one_key) {
    
39.       i++;
    
40.     }
    
41.     swap(&arr[i], &one_key);
    
42.   }
    
43.   quicksort(arr, left, i - 1); //accomplish the left remaining quicksort
    
44.   quicksort(arr, j + 1, right); //accomplish the right remaining quicksort
    
45. }
    
46. 
    
47. void
    
48. swap(int *a, int *b)
    
49. {
    
50.   int tmp;
    
51.   tmp = *a;
    
52.   *a = *b;
    
53.   *b = tmp;
    
54. }

复制代码

lxyscls_cu

交换有问题
1、在循环内，应该是i,j位置上的值进行交换
2、在循环外，交换i和标志位上的值

1. int partition(Item a[], int l, int r)
   
2. {
   
3.     int i = l - 1;
   
4.     int j = r;
   
5.     Item v = a[r];
   
6. 
   
7.     for (; ;) {
   
8.         while (less(a[++i], v)) ;
   
9.         while (less(v, a[--j]) if (j == l) break;
   
10.         if (j <= i) break;
    
11.         exch(a[i], a[j]);
    
12.     }
    
13.     exch(a[i], a[r]);
    
14. 
    
15.     return i;
    
16. }
    
17. 
    
18. void quicksort(Item a[], int l, int r)
    
19. {
    
20.     int i;
    
21. 
    
22.     if (l >= r) return;
    
23.     i = partition(a, l, r);
    
24.     quicksort(a, l, i - 1);
    
25.     quicksort(a, i + 1, r);
    
26. }

复制代码

{:3_189:}

linux_c_py_php

看算法导论吧, 这种快排实现过时了.