分治法之快速排序

 1 #include <stdio.h>
 2 #include <time.h>
 3 const int MAX=20;
 4 void QuickSort(int a[],int low,int high)
 5 {
 6     if(low>=high)
 7         return ;
 8     int first=low,last=high;
 9     int key=a[low];
10     while(first<last)
11     {
12         while(first<last && a[last]>=key)
13             --last;
14         a[first]=a[last];
15         while(first<last && a[first]<=key)
16             ++first;
17         a[last]=a[first];
18     }
19     a[first]=key;//找准轴值所在位置
20     QuickSort(a,low,first-1);
21     QuickSort(a,first+1,high);
22 }
23 extern void test2()
24 {
25          int length,i;
26          int num[MAX];
27          clock_t start,end;
28          printf("请输入待排序的数组长度(按ctrl+z结束)
");
29          while(scanf("%d",&length)!=EOF)
30          {
31              printf("请依次输入数组元素
");
32              for(i=0;i<length;i++)
33                  scanf("%d",num+i);
34              start=clock();
35              QuickSort(num,0,length-1);
36              end=clock();
37              printf("
-------------------------------------------
");
38              printf("快速排序(用时%f)后输出元素序列
",(double)(end-start)/CLOCKS_PER_SEC);
39              for(int i=0;i<length;i++)
40                  printf("%d	",num[i]);
41              printf("
");
42              for(i=0;i<length;i++)//清零
43                  num[i]=0;
44              printf("请输入待排序的数组长度(按ctrl+z结束)
");
45          }
46 }
View Code