這兩天狂累，研究報告、宣講會、見面會、筆試、面試所有的事情都連續在一起，忙得夠嗆，今天面完阿里研究院，總算有點時間了，于是先把上次提到的其它一些基本算法練習完成。
這次的練習包括：
原地堆排序，歸并排序，基于快排的選擇，計數排序，插值查找。
原地heap sort
使用最大堆，基于兩個堆的基本操作siftdown和siftup實現如下兩個步驟，事實上代碼里只用了siftdown，注意：這里的堆是從下標0開始的數組，不同于一般的下標從1開始的堆實現
(1)在輸入數組上原地建堆，O(N)
(2)N次"extractMax"操作，利用swap和siftdown實現
代碼里的parent和child是兩個宏，在下面的algo.h頭文件里聲明
1
//基本堆操作，注意：這里的堆從數組0位置開始！
2//為了應用堆排序，使用max堆
3void sift_down(int a[], int i, int n)
4
{
5
int temp, child;
6 for(temp=a[i];left_child(i)<n;i=child)
7
{
8 child = left_child(i);
9 if(child!=n-1 && a[child]<a[child+1])
10 child++;
11 if(temp<a[child])
12 a[i] = a[child];
13 else
14 break;
15
}
16 a[i] = temp;
17
}
18
19void sift_up(int a[], int i, int n)
20{
21 int temp, p;
22 for(temp=a[i];i!=0;i=p)
23 {
24 p = parent(i);
25 if(a[p]<temp)
26 a[i] = a[p];
27 else
28 break;
29 }
30 a[i] = temp;
31}
32
33//原地堆排序
34void heap_sort(int a[], int n)
35{
36 int i;
37 for(i=n/2;i>=0;i--)
38 sift_down(a, i, n);//build heap O(N)
39 for(i=n-1;i>0;i--)
40 {
41 swap(a[0], a[i]);
42 sift_down(a, 0, i);
43 }
44}
歸并排序標準的非原地實現，但是也有一點小優化，在算法開始時就一次性開了和輸入數組同樣大小的數組來保存中間值，免去了遞歸merge時每次重開數組的開銷。
1//歸并實現一
2void merge1(int a[], int ta[], int l, int r, int rend)
3{
4 int lend=r-1, temp=l, num=rend-l+1;
5
6 while(l<=lend && r<=rend)
7 if(a[l]<=a[r])
8 ta[temp++] = a[l++];
9 else
10 ta[temp++] = a[r++];
11
12 while(l<=lend)
13 ta[temp++] = a[l++];
14 while(r<=rend)
15 ta[temp++] = a[r++];
16
17 for(int i=0;i<num;i++,rend--)
18 a[rend] = ta[rend];
19}
20
21//歸并排序實現一
22void msort1(int a[], int ta[], int l, int r)
23{
24 int m;
25 if(l<r)
26 {
27 m = (l+r)/2;
28 msort1(a, ta, l, m);
29 msort1(a, ta, m+1, r);
30 merge1(a, ta, l, m+1, r);
31 }
32}
33
34//歸并排序實現一
35void merge_sort1(int a[], int n)
36{
37 int *ta = new int[n];
38 msort1(a, ta, 0, n-1);
39 delete [] ta;
40}
select基于快排的選擇算法，平均時間復雜度O(N)，很實用的選擇算法
1//基于快排思想的選擇算法
2int select(int a[], int l, int r, int k)
3{
4 if(l>=r)
5 return a[l];
6
7 int i=l,j=r+1;
8 while(1)
9 {
10 do i++; while(i<=r && a[i]<a[l]);
11 do j--; while(a[j]>a[l]);
12 if(i>j)
13 break;
14 swap(a[i], a[j]);
15 }
16 swap(a[l], a[j]);
17
18 if(k==j+1)
19 return a[j];
20 else if(k<=j)
21 return select(a, l, j-1, k);
22 else
23 return select(a, j+1, r, k);//注意，這兒不用改變k
24}
25
26int select_kth(int a[], int n, int k)
27{
28 //為了不改變原始數組，復制原始數組
29 int *ta = new int[n];
30 for(int i=0;i<n;i++)
31 ta[i] = a[i];
32 return select(ta, 0, n-1, k);
33 delete [] ta;
34}
計數排序這里假設輸入數據的范圍在[0,20]，書上說一般數值范圍在[0,100]的時候計數排序很實用，典型應用，排序百分制的考試分數
1//計數排序，條件：輸入數據范圍0~20
2void csort(int a[], int b[], int c[], int len)
3{
4 int i;
5 for(i=0;i<len;i++)
6 c[a[i]]++;
7 for(i=1;i<=20;i++)
8 c[i] = c[i]+c[i-1];
9 for(i=len-1;i>=0;--i)
10 {
11 b[c[a[i]]-1] = a[i];
12 c[a[i]]--;
13 }
14}
15void count_sort(int a[], int n)
16{
17 int *b = new int[n];
18 int *c = new int[21];
19 for(int i=0;i<=20;i++)
20 c[i] = 0;
21
22 csort(a, b, c, n);
23
24 for(int i=0;i<n;i++)
25 a[i] = b[i];
26
27 delete [] b;
28 delete [] c;
29}
插值查找和二分查找一樣，插值查找算法需要輸入數據已排序，時間復雜度和曲線的彎曲度相關
1//插值查找，post condition: 數組a已排序
2int ip_search(int a[], int l, int r, int t)
3{
4 if(l>r || a[l]>t || a[r]<t)
5 return -1;
6
7 int i = l + (t-a[l])/(a[r]-a[l]);
8 if(a[i] == t)
9 return i;
10 else if(a[i]<t)
11 return ip_search(a, i+1, r, t);
12 else
13 return ip_search(a, l, i-1, t);
14}
15int interpolation_search(int a[], int n, int t)
16{
17 return ip_search(a, 0, n-1, t);
18}
為了便于以后的繼續擴展，這次連同上次的代碼分到了.h和.cpp里。
方法聲明，algo.h
1#ifndef _ALGO_H
2#define _ALGO_H
3
4#include <iostream>
5#include <fstream>
6#include <sstream>
7#include <string>
8#include <cmath>
9#include <iomanip>
10#include <vector>
11#include <deque>
12#include <list>
13#include <queue>
14#include <stack>
15#include <map>
16#include <algorithm>
17#include <limits>
18#include <utility>
19#include <ctime>
20#include <bitset>
21using namespace std;
22
23void bubble_sort(int[], int);
24void insert_sort(int[], int);
25void select_sort(int[], int);
26void quick_sort_1(int[], int);
27void quick_sort_2(int[], int);
28void quick_sort_3(int[], int);
29int binary_search_1(int[], int, int);
30int binary_search_1(int[], int, int);
31int rand_int(int, int);
32void heap_sort(int[], int);
33void merge_sort1(int[], int);
35int select_kth(int[], int, int);
36void count_sort(int[], int);
37int interpolation_search(int [], int);
38
39#define left_child(i) (2*(i)+1)
40#define parent(i) ((i-1)/2)
41
42inline void assign_array(int a1[], int a2[], int n)
43{
44 for(int i=0;i<n;i++)
45 a1[i] = a2[i];
46}
47
48inline void print_array(int a[], int n)
49{
50 for(int i=0;i<n;i++)
51 cout<<a[i]<<" ";
52 cout<<endl;
53}
54
55#endif
測試代碼，algo.cpp
1#include "algo.h"
2
3int main()
4{
5 int origin_array[] = {3,2,6,9,11,2,3,8,4,5,3,8,19,1,11,7};
6 int len = sizeof(origin_array)/sizeof(origin_array[0]);
7 int *test_array = new int[len];
8
9 //測試heap sort
10 assign_array(test_array, origin_array, len);
11 print_array(test_array, len);
12 cout<<"heap sort"<<endl;
13 heap_sort(test_array, len);
14 print_array(test_array, len);
15 cout<<endl;
16
17 //測試merge sort
18 assign_array(test_array, origin_array, len);
19 print_array(test_array, len);
20 cout<<"merge sort"<<endl;
21 merge_sort1(test_array, len);
22 print_array(test_array, len);
23 cout<<endl;
32
33 //測試counting sort
34 assign_array(test_array, origin_array, len);
35 print_array(test_array, len);
36 cout<<"counting sort"<<endl;
37 count_sort(test_array, len);
38 print_array(test_array, len);
39 cout<<endl;
40
41 //測試interpolation search
42 print_array(test_array, len);
43 int t, loc;
44 cout<<"請輸入要查找的值: ";
45 cin>>t;
46 if((loc=interpolation_search(test_array, len, t))>=0)
47 cout<<"find "<<t<<" at location: "<<loc<<endl;
48 else
49 cout<<t<<" is not in the array"<<endl<<endl;
50
51 //測試select kth
52 int k;
53 assign_array(test_array, origin_array, len);
54 print_array(test_array, len);
55 cout<<"請輸入要查找的目標值的序數(1表示第1小值，2表示第2小值 ctrl+z退出): ";
56 while(cin>>k)
57 {
58 cout<<"select kth"<<endl;
59 cout<<"第"<<k<<"小值為: "<<select_kth(test_array, len, k)<<endl;
60 cout<<"請輸入要查找的目標值的序數(1表示第1小值，2表示第2小值 ctrl+z退出): ";
61 }
62 cout<<endl;
63
64 return 0;
65}