本文共 2096 字，大约阅读时间需要 6 分钟。

虽然久闻大名，但第一次接触算法导论，是看了网易公开课MIT的《算法导论》课，记得 第一集就讲到了插入排序和归并排序。

几个星期前也买了算法导论这本书，准备慢慢啃~

这星期主要在看前两部分，除了对于讲渐进时间、递归式分析这些东西感到云里雾里的，其它的都就

感觉越看越有觉得入迷，果然不愧是一本经典之作

好吧，开始。本文主要是用C++把书中的算法实现，以及一些笔记。

一、插入排序。

插入算法的设计使用的是增量（incremental）方法：在排好子数组A[1..j-1]后，将

元素A[ j]查入，形成排好序的子数组A[1..j]

插入排序的效率为O（n^2），在数据规模较小的时候效率较高。

最佳的情况是一个数组已经是排好序的，只需O（n）。最坏情况是输入数据是逆序的， O（n^2）。 对于一个算法，一般是考察它的最坏情况运行时间

.

伪代码：这里需要注意的是由于大部分编程语言的数组都是从0开始算起，而伪代码是从1开始的

C++实现：

template 
   
    void insert_sort(T *begin, T *end){  // 采用了更接近C++ STL sort的调用方式    T *p,*t,key;    for(p=begin+1; p!=end; ++p){        // 把A[j]插入排好序的A[1...j-1]中        key = *p;        t=p-1;        while(t>=begin && *t>key){            *(t+1) = *t;            --t;        }        *(t+1) = key;    }}
   

二、冒泡排序、选择排序、交换排序。

记得曾在刘汝佳的《算法竞赛入门经典》中看到一段代码，书上说是冒泡排序，但是却和冒泡排序的过程有点不一样。一直到最近才知道，

原来那个应该算作是交换排序。

选择排序伪代码：

冒泡排序伪代码：

// 选择排序void select_sort(int *start,int *end){	int *p,*q,*min;	for(p=start; p
   
    start; --q){            if(*q<*(q-1))				Swap(q,q-1);        }    }}
   

这三个排序的效率都为O（n^2）

从中可以看出，选择排序和冒泡排序都是从当前位置i的后面所有数中最小的一个数，交换到i位置中，但是选择排序只需要交换一次，冒泡排序可能会交换多次，速度应该是选择排序更快。。

除了选择排序和冒泡排序，还有一个叫”交换排序“的，思想也几乎一样，它是分别将第 i 个数 和后面的数一一比较，一旦后面的一个数比它小，就交换。

三、归并排序(合并排序)

归并排序是一种高效的排序算法，按照分治三步法：

划分问题：把序列分成元素个数尽量相等的两半

递归求解：把两半元素分别排序

合并问题：把两个有序表合并成一个

MERGE-SORT伪代码：

MERGE是关键:

这里给的代码实现是在每一堆的底部放一张“哨兵卡”，可以用于简化代码。

但是我用C++实现的方式采用另外一种形式，放“哨兵卡”虽然可以简化代码，但是这个“哨兵值”却有点局限性，在不同平台和机器下可能会不同。

// 算法导论实现版本template
   
    void merge(T array[],int p,int q,int r){     int n1,n2,i,j,k;     n1=q-p+1;    n2=r-q;     T *left=new T[n1], *right=new T[n2];     for(i=0; i
    
     void merge_sort(T array[],int p,int r){    if(p
    
   

并归排序在ACM中有个用处，可以用来求逆序数对（《算法竞赛入门经典》P144），因为如果直接枚举的效率为O（n^2）会超时。

受并归排序启发，由于合并操作是从小到大进行的，当右边的A【j】复制到T中时（这里的T是刘汝佳版的并归排序实现，后面给出），左边还没来得及复制到T得那些数就是左边所有比A【j】大的数，即A【j】的逆序数

刘汝佳神牛的并归排序+顺便求出逆序数

void merge_sort(int *A,int x,int y,int *T){   // T是专门开得一个临时数组。 这样可以大大节约了很多时间（上面的方式要多次开辟数组空间）    if(y-x > 1){        int m=x+(y-x)/2;   // 划分        int p=x, q=m, i=x;        merge_sort(A,x,m,T);        merge_sort(A,m,y,T);        while(p
   
    =y || (p