编程珠玑（第二版）阅读笔记05

说实话，这本书里面所提出的问题，大都需要我去细细思考，仔细揣摩，有时候作者轻描淡写的几句话，我也要思考一段时间来体会其中的算法思想，一星期读完只能说是囫囵吞枣吧，而且再加上有软工结对编程的压力，所以以后还是要细细研读的。这本书使我印象深刻之点就在于，作者总是通过一些程序设计的小问题小例子来介绍编程的思想与技巧，尤其是作者所讲的关于关于编程的思想，关于一些基本的算法，总能让人收益匪浅。

作者在这本书中提及了一些对于程序员来说比较基础的算法思想，例如二分法、排序、标签等等。我个人感觉作者比较强调二分法，。二分法对于我来说也是很熟悉了，早在c语言的课上就已经学过了。而跟随着作者读下去，仿佛有了更深的理解。作者从第二章“啊哈，算法”引出了二分法并介绍了二分法的好处后，在第四五章又详细地介绍了二分法及其程序实现，而在第九章代码优化中又对二分法的程序进行了优化，可谓是对二分法情有独钟了。而我也在作者的引导下，再一次熟悉了二分法，它也成为我在读完这本书后扎根在我脑海的词之一了。熟悉的同时，我也在牢记作者强调的二分法的灵活的运用，以及算法转化为代码时注意要点，还有测试调试手段的应用，让我收益很大。

这本书的作者擅长用一个个小故事小问题来向我们展示丰富的编程方法和算法思想，不是很难但是十分启迪人思考，的确和书名一样是字字珠玑了。唯一的遗憾是由于翻译的原因，有些地方确实有些晦涩难懂短短一星期的时间确实很难将这本书真正理解，而这几星期的学习让我对这本书产生了十分浓厚的兴趣，看的很入迷，今后有机会定要将这本书在拿出来在细细研读。

以下是这本书的几个经典算法：

两个二叉搜索：

//返回第一个值为t的下标， x[0...n-1]共n个
bsearch(Type t)
{
    l = -1;
    u = n;
 
    while l + 1 != u
        /*invariant: x[l] < t && x[u] >= t && l < u */
        m = ( l + u ) / 2;
        if x[m] < t
            l = m
        else
            u = m
    /*assert l+1 = u && x[l] < t && x[u] >= t */
    p = u
    if p >= n || x[p] != t
        p = -1
 
    return p
}

//1000以内的元素进行二分。
bserarch(Type t)
{
    l = -1
    if ( x[511] < t )    l = 1000 - 512
        /* assert x[l] < t && x[l+512] >= t */
    if ( x[l+256] < t )  l += 256
        /* assert x[l] < t && x[l+256] >= t */
    if ( x[l+128] < t ) l += 128
    if ( x[l+64] < t ) l += 64
    if ( x[l+32] < t ) l += 32
    if ( x[l+16] < t ) l += 16
    if ( x[l+8] < t ) l += 8
    if ( x[l+4] < t ) l += 4
    if ( x[l+2] < t ) l += 2
    if ( x[l+1] < t ) l += 1
    p = l + 1
    if p > 1000 || x[p] != t 
        p = - 1
    return p
}

关于排序，在平时写程序过程中，我们往往直接使用库函数qsort或者是sort，但有时候对接口使用函数调用会不那么高效，我们可能会需要自己来写排序算法。分析了插入排序和快排的时间复杂度，以及一些改进方案。关于插入排序和快排，其实是老生常谈了，但通过作者的娓娓道来，原来就是一个很简单的排序算法，如果不断改进，也总有余地。这是改进后写的排序代码：

#include<stdio.h>
#include<stdlib.h>
 
int partition(int a[], int low, int high)
{
    int pivot;
    pivot = a[low];
 
    while(low<high){
        while(low<high && a[high]>=pivot)
            high--;
        a[low] = a[high];
        while(low<high && a[low]<=pivot)
            low++;
        a[high] = a[low];
    }
    a[low] = pivot;
    return low;
}
 
void qSort(int a[], int low, int high)
{
    int pivotkey;
    if(low < high){
        pivotkey = partition(a, low, high);
        qSort(a, low, pivotkey-1);
        qSort(a, pivotkey+1, high);
    }
}
 
void insertSort(int a[], int n)
{
    int i, j;
    int temp;
 
    for(i=1; i<n; i++){
        temp = a[i];
        for(j=i; temp<a[j-1]&&j>=1; j--)
            a[j] = a[j-1];
        a[j] = temp;
    }
}
 
int main(){
 
    int n, i;
    int a[100];
    scanf("%d", &n);
    
    for(i=0; i<n; i++){
        scanf("%d", &a[i]);
    }
 
    insertSort(a, n);
 
    for(i=0; i<n; i++){
        printf("%d  ", a[i]);
    }
    return 0;
}