算法之快速排序

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <time.h>
 4 
 5 #define MAXLENGTH 21
 6 
 7 typedef struct
 8 {
 9     int key;
10 } Record;
11 
12 typedef struct
13 {
14     Record r[MAXLENGTH];
15     int length;
16 } DataList;
17 
18 void printList(DataList *list)
19 {
20     int i = 0;
21     for(i-0; i<list->length; i++)
22     {
23         printf("%d  ",list->r[i]);
24     }
25     printf("\n");
26 }
27 
28 int partition(DataList *list,int i ,int j)
29 {
30     int low = i;
31     int high = j;
32     int x = list->r[low].key;
33 
34     while(low<high)
35     {
36         while(list->r[high].key>=x&&low<high)
37             high--;
38 
39         if(low<high)
40         {
41             list->r[low] = list->r[high];
42             low++;
43         }
44 
45         while(list->r[low].key<=x&&low<high)
46             low++;
47 
48         if(low<high)
49         {
50             list->r[high]=list->r[low];
51             high--;
52         }
53 
54     }
55     list->r[low].key = x;
56     printf("low = %d\n",low);
57     return low;
58 }
59 
60 void quicksort(DataList *list,int i,int j)
61 {
62     int mod;
63     if(i<j)
64     {
65         mod = partition(list,i,j); //划分为左右两个子表
66         quicksort(list,i,mod-1);   //对左子表快速排序
67         quicksort(list,mod+1,j);    //对右子表快速排序
68     }
69 }
70 
71 
72 int main()
73 {
74     DataList *list = (DataList *)malloc(1*sizeof(DataList));
75     memset(list,0,sizeof(DataList));
76 
77     srand(time(0));
78 
79     int m = 0;
80     int index = 1;
81     for(m=0; m<20; m++)
82     {
83         int i = 0;
84         i = rand() % 100;
85         list->r[index].key = i;
86         list->length++;
87         index++;
88     }
89 
90     printList(list);
91 
92     int low = 1;
93     int high =20;
94     quicksort(list,low,high);
95 
96     printList(list);
97 }