数据结构-快速排序

程序代码如下：
  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <time.h>
  4 #define MAXSIZE 20
  5 typedef int KeyType;
  6 typedef char InfoType;
  7 
  8 //结构体定义
  9 typedef struct {
 10     KeyType key;
 11     InfoType otherinfo;
 12 }RedType;
 13 typedef struct {
 14     RedType r[MAXSIZE+1];
 15     int length;
 16 }SqList;
 17 
 18 //各个函数定义
 19 void print(SqList *L);
 20 void init(SqList *L);
 21 int Partition(SqList *L,int low,int high);
 22 void QSort(SqList *L,int low,int high);
 23 void QuickSort(SqList *L);
 24 
 25 //初始化，随机产生待排序的数组
 26 void init(SqList *L) {
 27     int n,i;
 28     printf("请输入待排序的元素个数：");
 29     scanf("%d",&n);
 30     srand(((int)time(0)));//设置随机种子
 31     for(i=1; i<=n; i++) {
 32         L->r[i].key = rand()%10+1;
 33     }
 34     L->length = n;
 35     printf("随机产生的待排数组为：");
 36     print(L);
 37     printf("
");
 38 }
 39 
 40 //输出数组元素
 41 void print(SqList *L) {
 42     int i;
 43     for(i=1; i<=L->length; i++) {
 44         printf("%d ",L->r[i].key);
 45     }
 46     printf("
");
 47 }
 48 
 49 //进行分趟排序
 50 int Partition(SqList *L,int low,int high) {//改进的算法
 51     int pivotkey;
 52     L->r[0] = L->r[low];
 53     pivotkey = L->r[low].key;
 54     while(low<high) {
 55         while(low<high && L->r[high].key>=pivotkey) {
 56         --high;
 57         }
 58         L->r[low] = L->r[high];
 59         while(low<high && L->r[low].key<=pivotkey) {
 60             ++low;
 61         }
 62         L->r[high] = L->r[low];
 63     }
 64     L->r[low] = L->r[0];
 65     return low;
 66 }
 67 /*int Partition(SqList *L,int low,int high) {
 68     int pivotkey;
 69     pivotkey = L->r[low].key;
 70     while(low<high) {
 71         while(low<high && L->r[high].key>=pivotkey) {
 72         --high;
 73         }
 74         L->r[0] = L->r[high];
 75         L->r[high] = L->r[low];
 76         L->r[low] = L->r[0];
 77         while(low<high && L->r[low].key<=pivotkey) {
 78             ++low;
 79         }
 80         L->r[0] = L->r[high];
 81         L->r[high] = L->r[low];
 82         L->r[low] = L->r[0];
 83     }
 84     return low;
 85 }*/
 86 
 87 
 88 //递归调用 分趟进行排序
 89 void QSort(SqList *L,int low,int high) {
 90     int pivotloc;
 91     if(low < high) {
 92         pivotloc = Partition(L,low,high);
 93         QSort(L,low,pivotloc-1);
 94         QSort(L,pivotloc+1,high);
 95     }
 96 }
 97 
 98 //进行快速排序
 99 void QuickSort(SqList *L) {
100     QSort(L,1,L->length);
101 }
102 
103 //主函数
104 int main()
105 {
106     SqList sq;
107     int k;
108     init(&sq);
109     QuickSort(&sq);
110     printf("排序之后的数组为：");
111     print(&sq);
112     return 0;
113 }