基础算法之排序--快速排序

  1         /************************************************************************************** 
  2         * Function     : 快速排序 
  3         * Create Date  : 2014/04/21 
  4         * Author       : NTSK13 
  5         * Email        : beijiwei@qq.com 
  6         * Copyright    : 欢迎大家和我一起交流学习，转载请保持源文件的完整性。 
  7         *                任何单位和个人不经本人允许不得用于商业用途 
  8         * Version      : V0.1                     
  9         ***************************************************************************************                     
 10         基础算法之排序--快速排序   3 1 7 5 8 4 9 0 2 6 
 11          
 12         步骤: 
 13         1)选取base 为最左边的3,最小序号为0(left=0),最大序号为9(right=9) 
 14          
 15         2)从最右边开始,向左查找到第一个小于base的数字,序列号为j,放在序号为0的位置,也就是取得base值的位置. 
 16         3)从最左边开始,向右查找到第一个大于base的数字序列号为i,放在上次查找小于base的位置,序列号j 
 17          
 18         4)循环执行  步骤2) 和 步骤  3) ,直到 i >= j. 此时序列号i的左侧全是小于base的数,  序列号i的右侧全是大于base的数, 
 19          
 20         5)把base值放在序列号为i的位置 
 21          
 22         6)分别递归调用left到 i-1, i+1到 right 进行快排 
 23          
 24         注意  left小于right 是可以进行递归的条件. 
 25          
 26         **************************************************************************************/    
 27         #include<stdio.h>    
 28                       
 29         #define MY_FUNC  1  
 30         #if MY_FUNC    
 31           
 32         #define M 10  
 33         int data[M]={0};  
 34           
 35         void quick_sort(int array[],int left,int right);  
 36           
 37         // The first method:  
 38         int main()    
 39         {    
 40             int i=0;  
 41           
 42             freopen("input.txt","r",stdin);  
 43           
 44             for(i=0;i<M;i++)  
 45                 scanf("%d",&data[i]);  // get input data  
 46                      
 47             printf("Before quick sort : \n");  
 48             fflush(stdout);  
 49           
 50              for(i=0;i<M;i++) {  
 51                  printf("%d \t",data[i]);  
 52                  fflush(stdout);  
 53              }  
 54           
 55             quick_sort(data,0,M-1);  
 56           
 57             printf("\nAfter quick sort : \n");  
 58             fflush(stdout);  
 59           
 60             for(i=0;i<M;i++) {  
 61                 printf("%d \t",data[i]);  
 62                 fflush(stdout);  
 63              }  
 64           
 65             return (0);  
 66         }    
 67           
 68         void quick_sort(int array[],int left,int right)  
 69         {  
 70             int base=array[left];//选定base  
 71             int i=left;//左侧序号  
 72             int j=right;//右侧序号  
 73           
 74             if(left < right)  
 75             {  
 76                 while(i<j)  
 77                 {  
 78                     //注意下边while循环里 i<j是必须加入的  
 79                     while(i<j && array[j]>base)//right --> left 从数组最右侧 开始往左找比base小的数; 如果找到的话,放在最左边  
 80                         j--;  
 81                     array[i]=array[j];  
 82           
 83                     //注意下边while循环里 i<j是必须加入的  
 84                     while(i<j && array[i]<base)//left -->right 从数组最左侧 开始往 找比base大的数; 如果找到的话,放在最右边  
 85                         i++;  
 86                     array[j]=array[i];  
 87                 }  
 88                 array[i]=base;  
 89           
 90                 quick_sort(array,left,i-1);  
 91                 quick_sort(array,i+1,right);  
 92             }  
 93           
 94         }  
 95               
 96         /********************************************my function end**************************************************/    
 97         #else    
 98           
 99         #define M 10  
100         int data[M]={0};  
101           
102         int division(int a[],int left,int right);  
103         void quick_sort(int a[],int left,int right);  
104           
105         // The second method:      
106         int main()    
107         {  
108             int i=0;  
109           
110             freopen("input.txt","r",stdin);  
111           
112             for(i=0;i<M;i++)  
113                 scanf("%d",&data[i]);  // get input data  
114           
115             printf("Before quick sort : \n");  
116             fflush(stdout);  
117           
118              for(i=0;i<M;i++) {  
119                  printf("%d \t",data[i]);  
120                  fflush(stdout);  
121              }  
122           
123             quick_sort(data,0,M-1);  
124           
125             printf("\nAfter quick sort : \n");  
126             fflush(stdout);  
127           
128             for(i=0;i<M;i++) {  
129                 printf("%d \t",data[i]);  
130                 fflush(stdout);  
131              }  
132           
133           
134             return (0);  
135         }  
136            
137           
138         int division(int a[],int left,int right)  
139         {  
140             int base=a[left];  
141             while(left<right)  
142             {  
143                 while(left<right && a[right]>base)  
144                     --right;  
145                 a[left]=a[right];  
146                 while(left<right && a[left]<base)  
147                     ++left;  
148                 a[right]=a[left];  
149             }  
150             a[left]=base;  
151             return left;  
152           
153         }  
154         void quick_sort(int a[],int left,int right)  
155         {  
156             int i=0;  
157             if(left<right)  
158             {  
159                 i=division(a,left,right);  
160                 quick_sort(a,left,i-1);  
161                 quick_sort(a,i+1,right);  
162             }  
163         }  
164           
165         #endif   
166 
167