這兩天狂累，研究報告、宣講會、見面會、筆試、面試所有的事情都連續(xù)在一起，忙得夠嗆，今天面完阿里研究院，總算有點時間了，于是先把上次提到的其它一些基本算法練習(xí)完成。
這次的練習(xí)包括：
原地堆排序，歸并排序，基于快排的選擇，計數(shù)排序，插值查找。
原地heap sort
使用最大堆，基于兩個堆的基本操作siftdown和siftup實現(xiàn)如下兩個步驟，事實上代碼里只用了siftdown，注意：這里的堆是從下標0開始的數(shù)組，不同于一般的下標從1開始的堆實現(xiàn)
(1)在輸入數(shù)組上原地建堆，O(N)
(2)N次"extractMax"操作，利用swap和siftdown實現(xiàn)
代碼里的parent和child是兩個宏，在下面的algo.h頭文件里聲明
1
//基本堆操作，注意：這里的堆從數(shù)組0位置開始！
2//為了應(yīng)用堆排序，使用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}
歸并排序標準的非原地實現(xiàn)，但是也有一點小優(yōu)化，在算法開始時就一次性開了和輸入數(shù)組同樣大小的數(shù)組來保存中間值，免去了遞歸merge時每次重開數(shù)組的開銷。
1//歸并實現(xiàn)一
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//歸并排序?qū)崿F(xiàn)一
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//歸并排序?qū)崿F(xiàn)一
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基于快排的選擇算法，平均時間復(fù)雜度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 //為了不改變原始數(shù)組，復(fù)制原始數(shù)組
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}
計數(shù)排序這里假設(shè)輸入數(shù)據(jù)的范圍在[0,20]，書上說一般數(shù)值范圍在[0,100]的時候計數(shù)排序很實用，典型應(yīng)用，排序百分制的考試分數(shù)
1//計數(shù)排序，條件：輸入數(shù)據(jù)范圍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}
插值查找和二分查找一樣，插值查找算法需要輸入數(shù)據(jù)已排序，時間復(fù)雜度和曲線的彎曲度相關(guān)
1//插值查找，post condition: 數(shù)組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}
為了便于以后的繼續(xù)擴展，這次連同上次的代碼分到了.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<<"請輸入要查找的目標值的序數(shù)(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<<"請輸入要查找的目標值的序數(shù)(1表示第1小值，2表示第2小值 ctrl+z退出): ";
61 }
62 cout<<endl;
63
64 return 0;
65}