分治测试

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <time.h>
 4 
 5 #define SIZE_ARRAY 100
 6 void quick_sort(int *array, int len); //分治
 7 
 8 
 9 int main()
10 {
11     int array[SIZE_ARRAY] = {0};
12     int i = 0, j = SIZE_ARRAY - 1;
13     int boop = 0;
14     srand((unsigned)time(NULL));
15     while(i < SIZE_ARRAY)
16     {
17         array[i] = rand() % SIZE_ARRAY;
18         i++;
19     }
20 
21     i = 0;
22     quick_sort(array, SIZE_ARRAY); //排序还有意思吗？
23 
24     while(i < j)
25     {
26         if(array[i] + array[j] == SIZE_ARRAY)
27         {
28             printf("I got it!\narray[%d] = %d, array[%d] = %d\n", i, array[i], j, array[j]);
29             boop = 1;
30             break;
31         }
32         else if(array[i] + array[j] > SIZE_ARRAY)
33         {
34             j--;
35         }
36         else
37         {
38             i++;
39         }
40     }
41 
42     if(0 == boop)
43     {
44        printf("I can‘t find it!\n");
45     }
46     
47     getchar();
48     return 0;
49 }
50 
51 
52 
53 
54 void quick_sort(int *array, int len) //分治
55 { 
56    int i = 0, j = len - 1;
57    int temp = array[i];
58    
59    if(len > 1)
60    {
61        while(i < j)
62        {
63           for(; j > i; j--)
64           {
65               if(array[j] < temp)
66               {
67                   array[i] = array[j];
68                   break;
69               }
70           }
71           for(; i < j; i++)
72           {
73               if(array[i] > temp)
74               {
75                   array[j] = array[i];
76                   break;
77               }
78           }
79        }
80 
81        quick_sort(array, i);
82        quick_sort(array + i + 1, len - 1 - i);
83    }
84    
85 }