[读书笔记]<Algorithms In C: Part 1-4 Fundamentals, data structures, sorting, searching> 第三版 Robert Sedgewick著 周良忠 译

    快速排序(quicksort)大概是比其他任何排序算法都应用广泛的排序算法。快速排序流行的原因是，它易于实现、能够很好地适用于各种不同输入数据，而且消耗的资源比其他任何排序方法都少。

    快速排序有着与其相应的特征(只使用一个小的辅助栈)，排序N个项的平均时间仅与NlogN成比例，而且其内循环时间极短。它的缺点是不稳定，在最坏情况下，需要N^2次运算：而且，实现中的一个简单的错误可能难以察觉，可能导致某些文件性能低下，从这种意义上说，快速排序是脆弱的。

-------------------------------------------------------

基本算法

    快速排序是排序的一种分治算法(divide-and-conquer method)。它的工作方式是，次数组划分为两组，然后独立排序各个部分。划分的准确位置取决于输入文件中元素的初始顺序。方法的关键在于划分过程，它将数组重排，使如下3个条件成立：

• 对于某i值，元素a[i]处于数组中的最终位置；
• a[l],...,a[i-1]中元素大于a[i]；
• a[i+1],...,a[r]中元素小于a[i]。

    通过划分实现完全排序，然后递归地在子文件中应用这个方法。因为划分总是至少将一个子元素放到位，所以，通过归纳法证明递归方法构成了一个正确的排序并不难。

    如果数组只有一个或者更少的元素，则无任何运算。否则，partition程序将处理这个数组，它将a[i]放到最终位置(i为l和r之间某个值，且含r)，并重排其他元素，让递归调用能正确完成排序。

int partition(Item a[], int l, int r);
void quicksort(Item a[], int l, int r)
{
    int i;
    if(r<=l)
        return;
    i = partition(a, l, r);
    quicksort(a, l, i-1);
    quicksort(a, i+1, r);
}

    我们使用如下通用策略来实现划分。首先，任意选定a[r]为划分元素(partitioning element)——将处于最终位置的元素。下一步，从数组右端进行扫描，直至发现一个小于该划分元素的元素。停止扫描的这两个元素显然不在最后划分数组的正确位置，所以交换它们。按这种方式继续划分，确保左指针左边的元素都小于划分元素，而且右指针右边的元素都大于划分元素。

    变量v保存划分元素a[r]的值，i和j分别为左右扫描指针。划分循环增加i、减小j，同时保持一个不变的性质：i左边的元素没有比v大的，j右边的元素没有比v小的。一旦指针相遇，交换a[i]与a[r]后就完成了划分，这次交换将v放到a[i]，使得v的右边没有更小的元素，发的左边没有更大的元素。划分实现为一个无穷循环，当指针相遇时使用break跳出。测试j==l避免划分元素为文件中最小元素的情况发生。

int partition(Item a[], int l, int r)
{
    int i = l-1, j = r;
    Item v = a[r];
    for( ; ; )
    {
       while (less(a[++i, v)) ;
       while(less(v, a[--j])) if(j==l) break;
       if(i >= j) break;
        exch(a[i], a[j]);
    }
    exch(a[i], a[r]);
    return i;
}

    划分的过程是不稳定的，因为在交换中，任何键可能被移过大量等于它的键。尚无使基于数组的快速排序变得稳定的简单办法。
    当文件中存在重复键时，指针的交叉就难以察觉。我们可以稍微改进此划分过程，当j<i时终止扫描，然后使用j代替i-l来为第一次递归调用确定左子文件的边界。让循环在这种情况下多重复一次是一种倒退，因为只要j和i引用相同的元素而终止扫描，就会有个元素处于其最终位置：一个终止是这两个扫描的元素，它因此必须等于划分元素，另一个是划分元素本身。

    对于键等于划分元素的情况，可以采取3种基本策略：碰到这类键时，让两个指针停止；让一个指针停止，让另一个跳过；或者让两个指针都越过。研究表明，最好是让两个指针停止，主要是因为当存在许多重复键时，这个策略可以平衡划分，而其他两种策略对于某些文件可能导致严重不平衡划分。

    排序的效率最终取决于文件的划分良莠程度，而后者又取决于划分元素的值。

-------------------------------------------------------

快速排序的性能特征

未完待续......

    已赴两年之约，又定十年之约!

[读书笔记]<Algorithms In C: Part 1-4 Fundamentals, data structures, sorting, searching> 第三版 Robert Sedgewick著 周良忠 译

    排序文件由数据项由数据项(item)组成，数据项又包含键(key)。在现代编程环境下，所有这些概念都具有自然抽象性。键通常只是项的一部分，它用于控制排序。排序方法的目标是重排这些项，让它们的键根据一些明确定义的排序规则来排序(通常按数字或字母来排序)。键和项的特性在各种应用中都可以各不相同，但键与相关信息按顺序排列的抽象概念是排序问题的本质。

    如果被排序的文件可以装载于内存中，则称该排序方法为内部排序(internal sort)。若排序文件来自碰带或磁盘，则称做外部排序(external sort)。两者的主要区别是，内部排序可以轻松访问任意项，而外部排序必须按顺序访问项，或者至少要按大数据块来访问。

    排序数组的问题以及排序链表的问题都很重要：在算法编制中，我们会碰到一些最适合于顺序排序的基本任务，还有其他一些最适合于链式分配的任务。一些经典的算法具有充分的抽象性，它们可以用数组或链表来实现；另外一些算法特别适合于用某一种数据结构来实现。

    我们首先学习数组排序。下面的程序是我们 的一个约定。它是一个驱动程序，通过从标准输入读取整数或者生成随机整数来填充数组；然后调用排序函数将整数按序放入数组；接着打印排序后的结果。排序函数假定被排序的数据类型为Item，而且为Item定义了运算less(比较两个键)、exch(交换两个项)以及compexch(比较两个项，并在必要时交换它们，让第二个项不小于第一个项)。

#include <stdio.h>
#include <stdlib.h>
#typedef int Item;
#define key(A) (A)
#define less(A, B) (key(A) < key(B))
#define exch(A, B) {Item t = A; A = B; B = t;}
#fefine compexch(A, B) if(less(B, A)) exch(A, B)
void sort(Item a[], int l, int r)
{
    int i, j;
    for(i=l+1; i<=r; i++)
        for(j=i; j>l; j--)
            comexch(a[j-1], a[j]);
}
main(int argc, char* argv[])
{
    int i;
    int N = atoi(argv[l]);
    int sw = atoi(argv[2]);
    int *a = malloc(N*sizeof(int));
    if(sw)
        for(i=0; i<N; i++)
            a[i] = 1000*(1.0*rand()/RAND_MAX);
    else
        while(scanf("%d", &a[N]) == 1)
            N++;
    sort(a, 0, N-1);
    for(i=0; i<N; i++) printf("%3d", a[i]);
    printf("\n");
}

    该示例sort函数是插入排序的一个变体。因为它只使用比较交换运算，所以它属于非适应性排序(nonadaptive sort)。它所执行的运算序列独立于数据的顺序。相比而言，适应性排序(adaptive sort)执行不同的运算序列，它们取决于比较(less运算)的结果。非适应性排序值得注意，因为它非常适合于硬件实现，但我们考虑的大部分通用排序都是适应性的。
    如果文件中具有重复键的项保持相对顺序，就称此排序方法为稳定的(stable)。例如，如果有一个按字母排列的学生表，他们的毕业年份按年排序，通过稳定方法生成的表中，同一班级的人仍然按字母排序，而能过非稳定方法生成的表中，可能不带有丝毫原始字母的痕迹。

    排序通常按两种途径之一来访问项：或者访问键进行比较，或者访问整个项进行移动。如果排序的项庞大，进行间接排序，避免打乱这些项是明智的。我们排的不是项本身，而是指针(或索引)的数组，让第一个指针指向最小的项，第二个指针指向第二小的项，依此类推。我们可以让键与项一起(如果键庞大)，或者与指针一起(如果键小)。排序后，可以重排项，但通常没有必要这样做，因为在排序后的状态，我们还可以(间接地)引用它们。

-------------------------------------------------------

选择排序

    首先，找出数组中的最小元素，并用首位置的元素与它交换。然后，找出次大元素，并用第十个位置的元素与它交换。重复此步骤，直到排序完整个数组。这个方法称做选择排序(selection sort)，因为它重复性地选择剩余元素中的最小元素来完成排序。

void selection(Item a[], int l, int r)
{
    int i, j;
    for(i=1; i<r; i++)
    {
       int min = i;
       for(j=i+1; j<=r; j++)
           if(less(a[j], a[min]))
                min = j;
       exch(a[i], a[min]);
    }
}

    内循环仅仅测试当前元素是否为目前为止最小元素(另外，还有增加当前元素索引并检查它未越过数组的对应代码)。移动项的工作在外循环中完成：每次交换将一个元素放到它的最终位置上，所以，交换次数为N-1(对最后一个元素不需要交换)。因此，运行时间受比较次数的限制。

    选择排序的一个缺点是，它的运行时间与文件中已完成的排序量只有一点关系。遍历文件查找最小元素的过程似乎对于下一次遍历文件时最小元素可能所在的位置并没有提供多少信息。例如，排序用户可能惊奇地发现，排序一个已经排序好的文件，或者排序一个所有键相等的文件与排序一个随机排序的文件，它们所花的时间一样长。

    尽管使用了暴力方式，但它在一个重要应用中，胜过更复杂的算法：对于具有庞大项、小键值的文件，使用选择排序则更为合适。对于这种应用，移动数据的开销控制比较的开销，而且没有其他算法在排序文件时，数据移动的次数会比选择排序更少。

-------------------------------------------------------

插入排序

    人们通常用于排序手中桥牌的方法是一次考虑一张牌，将它插入到已经排序过的牌的适当位置中。本章第一节的程序是这个方法的一个实现，它被称做插入排序(insertion sort)。

    第一节的插入排序的实现简单，但有效。但还有值得我们改进的地方。首先，我们碰到不大于正被插入项的键时，停止compexch运算，因为左边的子数组已经排序好了。这种修改将实现变成一种适应性排序，而且对于随机排序的钕，程序加速约2倍。

    通过前一段中描述的改进，终止内循环的条件有两个——可以将它重新用while循环来编码，以明确反映这一事实。实现的一个较细微的改进是j>l的测试是多余的。

    第三个改进也是包含删除内循环中的过多指令。它的依据是对同一个元素的连续交换率不高，因而只将较大元素右移一个位置，而不使用交换，因此避免了上述方式的时间浪费。

    改进程序：(i)它首先将数组中的最小的元素放在第一个位置，让它作为标记；(ii)在内循环中，它进行单个赋值，而不是进行交换；(iii)当正插入的元素已经就位时，终止内循环。

void insertion(Item a[], int l, int r)
{
    int i;
    for(i=l+1; i<=r; i++)
       compexch(a[l], a[i]);
    for(i=l+2; i<=r; i++)
    {
       int j = i;
       Item v = a[i];
        while(less(v, a[j-1]))
       {
          a[j] = a[j-1];
            j--
        }
        a[j] = v;
    }
}

    与选择排序不一样，插入排序的运行时间主要取决于输入数组中键的初始顺序。如果文件庞大，而且已经排序过(或者接近排序状态)，则插入排序速度快，而选择排序较慢。

-------------------------------------------------------

冒泡排序

    许多人学的第一种排序方法是冒泡排序(bubble sort)，因为它相当简单。冒泡排序不断地扫描文件，交换没有按顺序排列的邻近元素，直到完成整个文件的排序才停止。冒泡排序的主要优点是它易于实现，但实际上是否真的比插入排序和选择排序更容易实现值得商榷。一般说来，冒泡排序会比其他两种方法要慢。

    对于从l到r-1的每个i，内部(j)循环通过从右到左的元素传递、比较交换连续的元素，将a[i], ..., a[r]中的最小元素放到a[i]的位置上。最小元素通过这种比较一直向左移动，因此就“冒泡”似地移到了起始处。与在选择排序中一样，当索引i从左向右在文件中移动时，索引左边的元素就是该元素在数组中的最终位置。

void bubble(Item a[], int l, int r)
{
    int i, j;
    for(i=l; i<r; i++)
       for(j=r; j>i; j--)
            compexch(a[j-1], a[j]);
}

-------------------------------------------------------

基本排序的性能特征

    选择排序、插入排序和冒泡排序不管在最坏情况下还是在一般情况下，它们都是二次性时间算法，而且都不需要额外内存。它们的运行时间因此只相差常数倍，但它们的运算方式大不一样。

    一般来说，排序算法的运行时间与算法使用的比较次数成正比例，与移动或交换的项数成比例，或者与两者比成比例。对于随机输入，比较这些方法包括对比较和交换次数常数倍差异的研究、对内循环长度的常数倍差异的研究。对于具有特殊性质的输入，这些方法的运行时间可能相差不只常数倍。

    性质： 插入排序约平均使用N^2/4次比较、N^2/4次半交换(移动)，在最坏情况下，比较与交换次数加倍。

    性质：冒泡排序在最坏情况下，约平均使用N^2/2次比较、N^2/2次交换。

    定义：倒置(inversion)指颠倒文件中一对键的次序。

    为了定义文件中的倒置数，对每个元素，可以加和其左边元素大于该元素的个数(称这个量为元素对应的倒置数)。这个计数正好是插入排序中插入元素时它必须移动的距离。部分正序的文件与任意分布的文件相比，其倒置数要少。

    性质：对于对应于每个元素的倒置数都都不超过某常数的文件，插入排序和冒泡排序使用线性数量的比较和交换。

    性质：至多有一定数量的元素具有多于一定数量的相应倒置时，对于这种文件，插入排序使用线性数量的比较和交换。

    对于小文件，插入排序和选择排序的速度是冒泡排序的两倍，但是运行时间呈二次性增长（当文件大小成倍增长时，运行时间成4倍增长）。对于庞大的随机排序文件，以上方法都无能为力。当比较开销昂贵时（例如，其中的键为串），则插入排序比其他两种排序方法要快得多，因为它使用的比较要少。在交换开销昂贵的场合，选择排序是最佳选择。

    插入排序的运行时间取决于文件中倒置的总数量，与倒置的分布方式无关。

    要得到运行时间的结论，需要分析比较和交换的相对开销，这个因子又反过来取决于项的大小和键。

    性质：对于大项、小键文件，选择排序的运行时间为线性。

-------------------------------------------------------

希尔排序

    插入排序速度慢，因为它进行的唯一交换涉及到邻接项，因此，在数组中，项只能一次移动一个位置。例如，如果最小项刚好就在数组的末端，则需要N步将它移到位。希尔排序(shell sort)是插入排序的简单扩展，它允许离得很远的元素进行交换，所以提高了速度。

     希尔排序的思想是，重建文件后让它具有以下性质：每h取一个元素(从任意处开始)，得到一个有序文件。这种文件称称作h-有序(h-sorted)。换一个角度看，一个h-有序文件是h个独立的有序文件，它们交叉排列在一起。当h较大时，通过h-排序我们可以在数组中长距离移动元素，因此，使得对于更小的h，更容易进行h-排序。对于任意的h值序列(以1结尾)，使用这样的过程都生成一个有序文件。这就是希尔排序的实质。

     一种实现希尔排序的方式是，对每个h，分别使用插入排序独立排序所有h个子文件。尽管这个过程已经很简单，但我们甚至还可以使用更简单的方式，因为这些子文件是独立的。当使用h-排序文件时将较大元素移到时右边，然后在h-子文件的前面元素中插入。

    如果我们不使用标记，则在插入排序中，将其中的每个"1"换成"h"，得到的程序对文件做h-排序。添加一个循环来更改增量，得到如下紧凑的希尔排序实现。本程序使用的增量序列为：1 4 13 40 121 364 1093 3280 9841...(这是Knuth在1969年推荐的值，计算该增量序列很容易，从1开始，通过乘以3再加1得到下一个增量，而且得到一个相当有效的排序，即使对于中等大小的大型文件也有效)   

void shellsort(Item a[], int l, int r)
{
   int i, j, h;
   for(h=1; h<=(r-1)/9; h=3*h+1)
      ;
   for( ; h>0; h/=3)
     for(i=l+h; i<=r; i++)
        {
          int j=i; Item v=a[i];
           while(j>=l+h && less(v, a[j-1])
           {
              a[j] = a[j-h];
             j -= h;
           }
            a[j] = v;
        }
}

    性质：对于一个k-有序文件进行h-排序的结果是一个既h-有序又k-有序的文件。

    性质：g-排序一个既h-有序又k-有序的文件，希尔排序进行的比较次数少于N(h-1)(k-1)/g。设h和k互质。

    性质：对于增量序列1 4 13 40 121 364 1093 3280 9841...，希尔排序的比较次数少于O(N^(3/2))。

    性质：对于增量序列1 8 23 77 281 1073 4193 16577...，希尔排序的比较次数少于O(N^(4/3))。

    性质：对于增量序列1 2 3 4 6 9 8 12 18 27 16 24 36 54 81...，希尔排序的比较次数少于O(N(logN)^2)。

    设计一个优秀希尔排序增量序列的问题是简单算法具有复杂行为的一个突出例子。

    看到一些公司的Software Engineer的招聘广告，发现自己的知识面还是太狭窄了。最近正在疯狂恶补设计模式、UML和XML方面的知识。从图书馆借来一撂又一撂的书，先从简单的看起，由易到难，一步一步来。

    现在是Java大行其道的时代，作为非计算机专业的C/C++阵营的程序开发者，真有点夹缝求生的感觉。

    需要知道的东西越来越多：Programming Language(C/C++/Java), Data Structure & Algorithms, Design Patterns, Software Engineering, OS(Windows/Linux), Datebase, Networks, UML, XML...~!#$%^&*Oh, my god!

摘自：《面向对象分析设计与编程(OOA/OOD/OOP/AOP)》  第二版  吴炜煜 编著  清华大学出版社

    在这里，我们讨论类的两种特殊成员两数——构造函数和析构函数在虚函数机制中的使用。构造函数为对象分配存储空间，使一个对象初始化，而析构函数在该对象生命期完结时做相应的扫尾工作并释放出构造函数分配的内存。那么，这两种函数是否可以声明为虚函数呢?
    构造函数不能是虚函数。这一点可以从两个方而来解释。从概念上来说，虚函数机制只有在应用于地址时才有效，因为地址在编译阶段提供的类型信息不完全。构造函数的功能是为一个对象在内行中分配空间，也就是说，此时该对象的类型已经确定了，编译系统确切的知道应该调用哪—个类的构造函数。不需要也不可能应用动态绑定。从实现上来说，每个对象的VPTR需要构造函数来创始化(当然是由编译系统自动加进去的代码来实现)。在构造函数没有调用之前VPTR没有形成，根本就不可能实现动态绑定。
    那么，当构造函数内部有虚函数时，又会出现什么情况呢?结果是，只有在该类中的虚函数版本被调用。也就是说，此时虚函数机制不起作用了，调用虚函数如同调用—般的成员函数一样。
    构造函数不能是虚函数，那么析构函数呢？我们说，析构函数可以是虚函数，而且应该被声明为虚函数。与一般成员函数相似，析构函数被调用时，对象的构造已经完成，VPTR和VTABLE也已被正确初始化，因此虚析构函数在实现上是可能的。从设计角度来看，析构函数的任务是释放内存，因此它必须确切知道被释放的对象的类型，否则可能破坏有用的数据，产生不可预知的后果。例如，我们用基类指针指向了派生类对象，那么释放内作时，必须是释放派生类对象的存储空间。所以，析构函数经常被声明为虚函数。由于效率上的原因，并不把析构函数缺省为虚函数。但作为一条实践经验、可以给有虚函数的每个基类声明虚析构函数。
    同样的问题是，当析构函数内部有虚函数时，会如何工作呢？与构造函数相同，只有“局部”的版本被调用。但是，行为相同，原因是不一样的。构造函数只能调用“局部”版本，是因为调用时还没有派生类版本的信息。析构函数则是因为派生类版本的信息已经不可靠了。我们知道，析构函数的调用顺序与构造函数相反，是从派生类的析构函数到基类的析构函数。当某个类的析构函数被调用时，其下一级的析构函数已经被调用了，相应的数据也已被丢失，如果再调用虚函数的最后一级的版本，就相当于对一些不可靠的数据进行操作，这是非常危险的。因此，在析构函数中，虚函数机制也是不起作用的。

    另外说明一点，析构函数不能为纯虚函数，但你可以为其定义一个什么都不做的实现(里面是空语句)。

    有些事情还是提前感受一下的好。最近在关注一些找工作相关的信息。看到网上有好些人发的求职的笔经与面经，看到了自己和别人的差距。看到一些公司发的招聘广告与要求，尝试将自己对号入座，发现还有许多需要改进的地方。每个游戏都有他的游戏规则，找工作也一样。不能再像以前那样以一个学生的眼光来看待周围的一切而无视进化论的存在了。

    是的，要为自己的未来做点打算。给自己一个明确的定位，找到自己的缺点和不足之处，然后努力去改进。

    不知道什么时候开始，我习惯且喜欢上了安静的校园假期。没有出游，也不回家，就静静地待在校园里做自己想做的事情。尤其是五一、十一、还有周末这样的小假期，虽然作息与平时没有什么不同，但周围宁静，心也平静。

    今天是五月二日，早晨7点钟起床，吃了早饭就悠闲地走往实验室。校园里人不多，但是喜鹊叫得很欢。我知道它们也喜欢这样一个春日的早晨。

    上午的时候，实验室里只有几个人，大家都各做各的事情，都保持着一种默契。要在平时，这里同学来回出入与穿梭的频率是很高的。

    中午照例是要去健身房的。运动运动，洗个澡，感觉浑身舒爽。

    回来以后，又去图书馆借了几本书，是有关应聘与面试的。都说机会偏爱有准备的人，我不知道我以后是不是有准备的人，但我希望是。

    我喜欢这种感觉，单调却不乏味。