【算法导论】排序（一）

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

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

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

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

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

一、插入排序。

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

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

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

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

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

C++实现：

template <typename T>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;}}

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

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

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

选择排序伪代码：