关于数据结构，关于算法，关于hash桶算法

在之前，我都从来不看重数据结构和算法的执行效率，什么时间复杂度和空间复杂度搞得我头晕，但是前几天逄洪江给我出了一道题，在我用两种算法实际比较后发现算法真的很重要。题目大意如下：从一个随机数组中，找出两数相加之和等于5的所有结果。

当时我想也没想就用嵌套for循环做了出来，但是他让我用一亿个数据和20万范围去测试，结果我的算法直接死机……用十万条数据去计算，也用了十多秒的时间才算完。后来逄洪江给我介绍了hash桶算法，大意是生成20万大小的数组作为桶，如果数组中存在某数据，就在桶中同一下标数据变为1，不存在则为0。然后把桶中数据用快速排序轮一遍，相加等于5的数据存入链表中即可。此算法时间复杂度可以达到O(n)的水平。我实现算法后，才测试了一下，同样是一亿数据，20万范围，最快3.7秒全部处理完！这就是算法的力量！

桶算法主要代码如下：//忽略了与之配套的chain.c文件，该文件是链表生成，链表添加，结构设计部分。

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include "chain.c" //include the chain.c to create chain and list
  4 #define NUMBER_SCOPE 69000
  5 #define ARRAY_SIZE 100000000
  6 #define PLUS_RESULT 5
  7     
  8 int *createArray(long length){
  9     int i;
 10     int *array=(int*)malloc(length*sizeof(int));
 11     srand((int)time(0));
 12     printf("Array:");
 13     for(i = 0;i<length;i++){
 14         array[i]=rand()%NUMBER_SCOPE - (NUMBER_SCOPE)/2;
 15         //printf("%d,",array[i]);
 16     }
 17     return array;
 18 }
 19     
 20 /*
 21 find the max number from a array 
 22 */
 23 int maxNum(int *array,int length){
 24     int i,max;
 25     max = array[0];
 26     for(i = 1;i<length;i++){
 27         if(array[i] > max){
 28             max = array[i];
 29         }
 30     }
 31     return max;
 32 }
 33 /*
 34 find the min number from a array 
 35 */
 36 int minNum(int *array,int length){
 37     int i,min;
 38     min = array[0];
 39     for(i = 1;i<length;i++){
 40         if(array[i] < min){
 41             min = array[i];
 42         }
 43     }
 44     return min;
 45 }
 46 /*
 47 this function to fill barrel ,first parameter is the barrel,second is array
 48 */
 49 int *fillBarrel(int *barrel,int *array){
 50     int i,site;
 51     for(i = 0;i < ARRAY_SIZE;i++){
 52         site = array[i] - barrel[1] + 3;
 53         barrel[site] = 1;
 54     }
 55     return barrel;
 56 }
 57 /*
 58 this function get a barrel array ,return a result chain,
 59 it create by Quick Sort
 60 */
 61 struct chain *createResult(int *barrel){
 62     int l_site,r_site,l_index,r_index;
 63     struct chain *result;
 64     struct list lst;
 65     l_index = 3;
 66     r_index = barrel[0] - 1;
 67     while(l_index < r_index && 1){
 68         if((barrel[l_index] == 1) && (barrel[r_index] == 1)){
 69             l_site = l_index - 3 + barrel[1];
 70             r_site = r_index - 3 + barrel[1];
 71             // printf("\nl_site = %d\tr_site = %d",l_site,r_site);
 72             // printf("\nbarrel[%d] = %d \nbarrel[%d] = %d",l_index,barrel[l_index],r_index,barrel[r_index]);
 73             if((l_site + r_site) == PLUS_RESULT){
 74                 lst.firstNum  = l_site;
 75                 lst.secondNum = r_site;
 76                 /*add in chain*/
 77                 result = addlink(result,lst);
 78                 l_index ++;
 79                 r_index --;
 80             }
 81             else if((l_site + r_site) > PLUS_RESULT){
 82                 r_index--;
 83             }
 84             else{
 85                 l_index++;
 86             }
 87         }else if(barrel[l_index] != 1){
 88             l_index ++;
 89         }
 90         else{
 91             r_index --;
 92         }
 93     }
 94     return result;
 95 }
 96 /*
 97 this function well create a barrel array by the array in the parameters
 98 */
 99 int *createBarrel(int *array,int length){
100     int min,max,capacity,*barrel,i;
101     min = minNum(array,length);
102     max = maxNum(array,length);
103     capacity = max - min + 4;   //+4,because save capacity,min and max.
104     barrel = (int*)malloc(capacity*sizeof(int));
105     for(i = 0;i<capacity;i++){
106         barrel[i] = 0;
107     }
108     barrel[0] = capacity;   //save barrel capacity in barrel[0]
109     barrel[1] = min;        //save min number in barrel[1]
110     barrel[2] = max;        //save max number in barrel[2]
111     return barrel;
112 }
113     
114 /*
115 this function could display the information about the barrel and the content
116 */
117 void showBarrel(int *barrel){
118     int i;
119     // for(i = 3;i < barrel[0];i++){
120     //  printf("%d\t",barrel[i]);
121     // }
122     printf("\narray_length = %d\ncapacity = %d\nmin = %d\nmax = %d\n",ARRAY_SIZE,barrel[0],barrel[1],barrel[2]);
123 }
124     
125 main(){
126     int *array,*barrel;
127     long length;
128     struct chain *result;
129     //int a[] = {1,2,3,4,5,7,7,7,7,0};
130     printf("======main() begin=======\n");
131     length = ARRAY_SIZE;
132     array = createArray(length);
133     //array = a;
134     //printf("\n====create array over=======");
135     barrel = createBarrel(array,length);
136     //printf("\n====create barrel over=======");
137     barrel = fillBarrel(barrel,array);
138     //printf("\n====fill barrel over=======\n");
139     showBarrel(barrel);
140     //printf("\n====show barrel over=======\n");
141     result = create();
142     //printf("\n====create result over=======\n");
143     result = createResult(barrel);
144     printf("\n====computer result over=======\n");
145     /* the function to display the result chain*/
146     showChain(result);
147 }