快速排序

 1 /*快速排序*/
 2 #include<stdio.h>
 3 #include<stdlib.h>
 4 
 5 typedef struct
 6 {
 7     int *data;
 8     int length;
 9 }Sqlist;
10 
11 
12 /*顺序表的初始化*/
13 void InitList(Sqlist &L, int l)
14 {
15     L.data = (int*)malloc((l+1)*sizeof(int));
16     L.length = 0;
17 }
18 
19 void CreateLList(Sqlist &L, int *a, int l)
20 {
21     L.length = 1;
22     for(int i=1; i<=l; i++)
23     {
24         L.data[i] = a[i-1];
25         L.length++;
26     }
27 }
28 
29 /*将序列进行分块*/
30 int Partition(Sqlist &L, int low, int high)
31 {
32     L.data[0] = L.data[low];
33     while(low<high)
34     {
35         while(low < high && L.data[high] > L.data[0])
36         {
37 
38             high--;
39         }
40 
41         L.data[low] = L.data[high];
42         while(low < high && L.data[low]<=L.data[0])
43         {
44             low++;
45         }
46         L.data[high] = L.data[low];
47     }
48 
49     L.data[low] = L.data[0];
50     return low;
51 }
52 
53 
54 /*递归思想对序列进行排序*/
55 int QSort(Sqlist &L, int low, int high)
56 {
57     if (low<high)
58     {
59         int pivotloc =    Partition(L,low,high);
60         QSort(L,low,pivotloc-1);
61         QSort(L,pivotloc+1,high);
62     }
63 }
64 
65 void QuickSort(Sqlist &L)
66 {
67     QSort(L,1,L.length-1);
68 }
69 
70 void DisplayList(Sqlist L)
71 {
72     for(int i = 1; i<L.length; i++)
73     {
74         printf("%d ",L.data[i]);
75     }
76 
77     printf("
");
78 }
79 
80 int main(int argc, char const *argv[])
81 {
82     Sqlist L;
83     int a[] = {27,13,76,97,65,38,49};
84     int l = sizeof(a)/sizeof(a[1]);
85 
86     InitList(L,l);
87     CreateLList(L,a,l);
88     QuickSort(L);
89     DisplayList(L);
90     return 0;
91 }