这两天狂累，研究报告、宣讲会、见面会、笔试、面试所有的事情都连续在一起，忙得够呛，今天面完阿里研究院，总算有点时间了，于是先把上次提到的其它一些基本算法练习完成。
这次的练习包括：
原地堆排序，归并排序，基于快排的选择，计数排序，插值查找。
原地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}