快速排序

 1 #include<stdio.h>
 2 
 3 typedef struct NODE
 4 {
 5     int data;
 6     struct NODE *next;
 7 }Node;
 8 
 9 #define N 10
10 
11 int partition(int a[], int left, int right)
12 {
13     int low, high;
14     int pivot = a[left];
15 
16     low = left;
17     high = right;
18 
19     while(low < high)
20     {
21         while(low < high && a[high] > pivot)
22         {
23             high--;
24         }
25         //high从右向左找小于pivot 的元素
26         if(low < high)
27         {
28             a[low++] = a[high];
29         }
30 
31 
32         while(low < high && a[low] < pivot)
33         {
34             low++;
35         }
36         //low 从左向右找大于pivot 的元素
37         if(low < high)
38         {
39             a[high--] = a[low];
40         }                
41     }
42 
43     a[low] = pivot;//将枢轴元素保存到low=high的位置
44         
45     return low; //返回枢轴元素的位置
46     
47 }
48 
49 int QuickSort(int a[], int low, int high)
50 {
51     int p;
52 
53     if(low < high)
54     {
55         p = partition(a, low, high);
56         QuickSort(a, low, p - 1);
57         QuickSort(a, p + 1, high);
58     }
59 
60     return 0;
61 }
62 
63 
64 //测试程序
65 void main()
66 {
67     int a[N] = {2, 5, 3,  8, 10, 0, -5,  4, 34, 11};
68     int m, n;
69     int ret = 0;
70     int i;
71 
72     m = 0;
73     n = N -1;
74 
75     printf("before:");
76     for(i = 0; i < N; i++)
77     {
78         printf("%d ", a[i]);
79     }
80     printf("\nafter:");
81     
82     ret = QuickSort(a, m, n);
83     
84     for(i = 0; i < N; i++)
85     {
86         printf("%d ", a[i]);
87     }
88     printf("\nret:%d\n", ret);
89     
90 }