dream.in.java

能以不变应万变是聪明人做事的准则。万事从小事做起,积累小成功,问鼎大成功,是成功者的秘诀。

合并排序

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 #include<time.h>
  4 
  5 #define MAX1 10
  6 #define MAX2 10
  7 
  8 
  9 #define SWAP(x,y) {int t; t = x; x = y; y = t;}
 10 
 11 int partition(int[], int , int );
 12 void quicksort(int[] , int ,int);
 13 void mergesort(int[], intint[], intint[]);
 14 
 15 int main(void) {
 16     int number1[MAX1] = {0};  
 17     int number2[MAX1] = {0};  
 18     int number3[MAX1+MAX2] = {0}; 
 19     int i;
 20     srand(time(NULL));  
 21     printf("排序前:");  
 22     printf("\nnumber1[]:");     
 23     for(i = 0; i < MAX1; i++) {   
 24         number1[i] = rand() % 100;    
 25         printf("%d ", number1[i]);  
 26     }
 27     printf("\n"); 
 28 
 29     printf("\nnumber2[]:");   
 30     for(i = 0; i < MAX2; i++) {   
 31         number2[i] = rand() % 100;       
 32         printf("%d ", number2[i]); 
 33     } 
 34     
 35     printf("\n=====================================\n"); 
 36 
 37     // 先排序兩筆資料    
 38     quicksort(number1, 0, MAX1-1);    
 39     quicksort(number2, 0, MAX2-1); 
 40     printf("\n排序后:"); 
 41     printf("\nnumber1[]:");     
 42     for(i = 0; i < MAX1; i++) {   
 43         //number1[i] = rand() % 100;    
 44         printf("%d ", number1[i]);  
 45     }
 46     printf("\n"); 
 47     printf("\nnumber2[]:");   
 48     for(i = 0; i < MAX2; i++) {   
 49         //number2[i] = rand() % 100;       
 50         printf("%d ", number2[i]); 
 51     } 
 52     mergesort(number1, MAX1, number2, MAX2, number3); 
 53     printf("\n合併後:");    
 54     for(i = 0; i < MAX1+MAX2; i++)     
 55         printf("%d ", number3[i]);    
 56     printf("\n"); 
 57 
 58     return 0;
 59 }
 60 
 61 int partition(int number[], int left, int right) {  
 62     int i, j, s;  
 63     s = number[right]; 
 64     i = left - 1;    
 65     for(j = left; j < right; j++) {   
 66         if(number[j] <= s) {        
 67             i++;           
 68             SWAP(number[i], number[j]);  
 69         }    
 70     }    
 71     SWAP(number[i+1], number[right]);  
 72     return i+1
 73 }
 74 
 75 
 76 void quicksort(int number[], int left, int right) {   
 77     int q;     
 78     if(left < right) {      
 79         q = partition(number, left, right);   
 80         quicksort(number, left, q-1);     
 81         quicksort(number, q+1, right);
 82     }
 83 }
 84 
 85 
 86 //合并排序
 87 void mergesort(int number1[], int M, int number2[],   
 88                int N, int number3[]) {
 89     int i = 0, j  = 0, k = 0;
 90 
 91     while(i < M && j <N){
 92         if(number1[i] <= number2[j]){
 93             number3[k++= number1[i++];
 94         }
 95         else{
 96             number3[k++= number2[j++];
 97         }
 98     }
 99 
100         while(i < M){
101             number3[k++= number1[i++];
102         }
103         while(j < N){
104             number3[k++= number2[j++];
105         }
106     }
107 
108 
109 

posted on 2009-05-04 19:12 YXY 阅读(190) 评论(0)  编辑  收藏


只有注册用户登录后才能发表评论。


网站导航: