惯用的排序和查找(不定期更新)

 1 void BubbleSort(int *a, int n)
 2 {
 3 　　int i,j,t;
 4 　　for(i=0; i<n-1; i++)
 5 　　{
 6 　　　　for(j=0; j<n-1-i; j++)
 7 　　　　{
 8 　　　　　　if(a[j]>a[j+1])
 9 　　　　　　{
10 　　　　　　　　t = a[j];
11 　　　　　　　　a[j] = a[j+1];
12 　　　　　　　　a[j+1] = t;
13 　　　　　　}
14 　　　　}
15 　　}
16 }

 1 void SelectSort(int *a, int n)
 2 {
 3     int i,j,m,t;
 4     for(i=0; i<n-1; i++)
 5     {
 6         m = i;
 7         for(j=i+1; j<n; j++)
 8         {
 9             if(a[m]>a[j])
10             {
11                 m=j;
12             }
13         }
14         t=a[m];
15         a[m] = a[i];
16         a[i] = t;
17     }
18 }

 1 void InsertSort(int *a, int n)
 2 {
 3     int in,out,t;
 4     for(out=1; out<n; out++)
 5     {
 6         t = a[out];
 7         in = out;
 8         while(in>0 && a[in-1]>=t)
 9         {
10             a[in] = a[in-1];
11             in--;
12         }
13         a[in] = t;
14     }
15 }

 1 void QuickSort(int *a, int l, int r)
 2 {
 3     int i,j,t;
 4     if(l <r)
 5     {
 6         i=l;
 7         j=r;
 8         t = a[i];
 9         while(i<j)
10         {
11             while(i<j && a[j]>t) j--;
12             if(i<j)
13             {
14                 a[i] = a[j];
15                 i++;
16             }
17             while(i<j && a[i]<t) i++;
18             if(i<j)
19             {
20                 a[j] = a[i];
21                 j--;
22             }
23         }
24         a[i] = t;
25         QuickSort(a, l, i-1);
26         QuickSort(a, i+1, r);
27     }
28 }

 1 void Merge(int *initList, int *mergeList, int left, int mid, int right)
 2 {
 3     int i,j,k;
 4     i=left;
 5     j=mid+1;
 6     k=left;
 7     while(i<=mid && j<=right)
 8     {
 9         if(initList[i]<initList[j])
10         {
11             mergeList[k++]=initList[i++];
12         }
13         else
14         {
15             mergeList[k++]=initList[j++];
16         }
17 
18         if(i>mid)
19         {
20             while(j<=right)
21             {
22                  mergeList[k++]=initList[j++];
23             }
24 
25         }
26         else if(j>right)
27         {
28             while(i<=mid)
29             {
30                 mergeList[k++]=initList[i++];
31             }
32         }
33 
34     }
35 }
36 void MergePass(int *initList, int *mergeList, int n, int s)
37 {
38     int i,j;
39     for(i=0; i<=n-2*s+1; i+=2*s)
40     {
41         Merge(initList, mergeList, i, i+s-1, i+2*s-1);
42     }
43     if(i+s<n)
44         Merge(initList, mergeList, i, i+s-1, n-1);
45     else
46         for(j=i; j<=n-1; j++)
47         mergeList[j] = initList[j];
48 }
49 void MergeSort(int *a, int b, int n)
50 {
51     int s=1;
52     while(s<n)
53     {
54         MergePass(a, b, n, s);
55         s*=2;
56         MergePass(b, a, n, s);
57     }
58 }

 1 int get_index(int num, int dec,int order)
 2 {
 3     int i,j,n;
 4     int index;
 5     int div;
 6     for(i=dec; i>order; i--)
 7     {
 8         n=1;
 9         for(j=0; j<dec-1; j++)
10             n*=10;
11         div=num/n;
12         num-=div*n;
13         dec--;
14     }
15     n=1;
16     for(i=0;i<order-1;i++)
17         n*=10;
18     index=num/n;
19     return index;
20 }
21 void radis_sort(int array[], int dec, int order)
22 {
23     int i,j;
24     int index;
25     int tmp[10]={0};
26     int num[10]={0};
27     for(i=0; i<10; i++)
28     {
29         index=get_index(array[i], dec, order);
30         num[index]++;
31     }
32     for(i=1; i<10; i++)
33         num[i]+=num[i-1];
34     for(i=10-1;i>=0;i--)
35     {
36         index=get_index(array[i], dec, order);
37         {
38             j=--num[index];
39             tmp[j]=array[i];
40         }
41     }
42     for(i=0;i<10;i++)
43     {
44         array[i]=tmp[i];
45     }
46 }

 1 int BinSelect(int x, int a[], int n)
 2 {
 3     int low=0, hight=n-1, mid;
 4 
 5     while(low <= hight)
 6     {
 7         mid = (low + hight)/2;
 8         if(x > a[mid])
 9         {
10             low = mid +1;
11         }
12         else if(x < a[mid])
13         {
14             hight = mid-1;
15         }
16         else if(x == a[mid])
17         {
18             return mid-1;
19         }
20 
21     }
22     return -1;
23 }