快速排序算法

“挖坑填数+分治法”
 1 //快速排序实现 
 2  
 3 #include "stdio.h"
 4 #include "stdlib.h"
 5 #include "time.h"//用于获取程序运行时间  
 6 
 7 void quick_sort(int s[],int l,int r)
 8 {
 9     if(l < r)
10     {
11         int i=l,j=r,x=s[l];
12         while(i<j)
13         {
14             while(i<j && s[j]>=x)//从右到左找到第一个小于x的数  
15                 j--;
16             if(i<j)
17                 s[i++]=s[j];
18             
19             while(i<j && s[i]<=x)//从左往右找到第一个大于x的数  
20                 i++;
21             if(i<j)
22                 s[j--]=s[i]; 
23             
24         }
25         
26         s[i]=x;//i = j的时候，将x填入中间位置  
27         quick_sort(s,l,i-1);//递归调用 
28         quick_sort(s,i+1,r);        
29     }
30 }
31 
32 
33 int main()
34 {
35     clock_t start,finish;
36     double totaltime;
37     start=clock();
38     
39     /****下面为需要运行的主程序****/ 
40     
41     int a[] = {1,8,44,77,35,65,78,12,25,455,20,15,45};
42     int length = sizeof(a)/sizeof(int);//求数组的长度  
43     
44     printf("原序列为： ");
45     for(int i=0;i<length;i++)
46     {
47         printf("%3d",a[i]);
48     }
49     
50     quick_sort(a,0,length);
51     
52     printf("
排序后的序列为：");
53     for(int i=0;i<length;i++)
54     {
55         printf("%3d",a[i]);
56     }
57 
58     /********************************/
59         
60    finish=clock();
61    totaltime=(double)(finish-start)/CLOCKS_PER_SEC;
62    
63    printf("
程序运行的时间为: %.5f 秒",totaltime);
64 
65 }
运行结果：