Fly me to the moon

the beauty of C++

基本算法练习(二)

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

原地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<=&& 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 *= new int[n];
18    int *= 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>|| a[l]>|| 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[], intint);
30int binary_search_1(int[], intint);
31int rand_int(intint);
32void heap_sort(int[], int);
33void merge_sort1(int[], int);
35int select_kth(int[], intint);
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}

posted on 2009-09-28 20:36 翼帆 阅读(724) 评论(0)  编辑 收藏 引用 所属分类: 算法笔试/面试


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

<2009年9月>
303112345
6789101112
13141516171819
20212223242526
27282930123
45678910

统计

常用链接

留言簿

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜