快速排序：时间复杂度O(nlog2n)

才开始忘记那个递归的判断条件了。。。

以前一直以为递归难懂，其实并不是。。。

1. //快速排序算法  
2. #include <stdio.h>  
3.  
4. #define MAX 10  
5.  
6. int Partition(int arr[], int left, int right)    //选一个数，这个数左边的为小于它的，右边为大于它的  
7. {  
8.     int low, high, x;  
9.     low = left;  
10.     high = right;  
11.     x = arr[left];                       //x选取第一个数，将其与其他数进行比较  
12.     while(low < high)  
13.     {  
14.         while(arr[high] >= x && (low < high))    //先从右边开始遍历数  
15.             high--;  
16.         if(low < high)  
17.         {  
18.             arr[low] = arr[high];  
19.             low++;  
20.         }   
21.         while(arr[low] <= x && (low < high))    //开始从左边开始遍历  
22.             low++;  
23.         if(low < high)   
24.         {  
25.             arr[high] = arr[low];  
26.             high--;  
27.         }                   
28.     }   
29.     arr[low] = x;             //将中间数放在low = high 的位置  
30.     return low;                //返回中间数的位置   
31. }   
32.  
33.  
34. //进行递归排序  
35. void RecursionQuickSort(int arr[], int low, int high)  
36. {  
37.     int mid;  
38.     if(low < high)  
39.     {  
40.         mid = Partition(arr, low, high);     //得到中间数  
41.         RecursionQuickSort(arr, low, mid - 1);  
42.         RecursionQuickSort(arr, mid + 1, high);   //中间的那个数不变   
43.     }  
44. }   
45.  
46.  
47. int main()  
48. {  
49.     int i;  
50.     int arr[MAX] = {50, 45, 23, 45, 56, 74, 78, 89, 45, 56};  
51.     RecursionQuickSort(arr, 0, MAX - 1);  
52.       
53.     for(i = 0; i < MAX; i++)       
54.         printf("%d ", arr[i]);  
55.     printf("\n");  
56.     return 0;   
57. }