直接插入排序基本思想
1．直接插入排序的基本思想
直接插入排序（Straight Insertion
Sorting）的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程
中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。
把a[i]插入到a[0]，a[1]，...,a[i-1]之中的具体实施过程为:先把a[i]赋值给变量t,然后将t依次与a[i-1],a[i-
2],...进行比较,将比t大的元素右移一个位置,直到发现某个j(0<=j<=i-1),使得a[j]<=t或j为(-1),把t
赋值给a[j+1].
2、第i-1趟直接插入排序：
　通常将一个记录R[i](i=2，3，…，n-1)插入到当前的有序区，使得插入后仍保证该区间里的记录是按关键字有序的操作称第i-1趟直接插入排序。
　排序过程的某一中间时刻，R被划分成两个子区间R[1．．i-1]（已排好序的有序区）和R[i．．n]（当前未排序的部分，可称无序区）。
　直接插入排序的基本操作是将当前无序区的第1个记录R[i]插人到有序区R[1．．i-1]中适当的位置上，使R[1．．i]变为新的有序区。因为这种方法每次使有序区增加1个记录，通常称增量法。
　插入排序与打扑克时整理手上的牌非常类似。摸来的第1张牌无须整理，此后每次从桌上的牌(无序区)中摸最上面的1张并插入左手的牌(有序区)中正确的位
置上。为了找到这个正确的位置，须自左向右(或自右向左)将摸来的牌与左手中已有的牌逐一比较。
一趟直接插入排序方法
1．简单方法
　首先在当前有序区R[1..i-1]中查找R[i]的正确插入位置k(1≤k≤i-1)；然后将R[k．．i-1]中的记录均后移一个位置，腾出k位置上的空间插入R[i]。
注意：
　若R[i]的关键字大于等于R[1．．i-1]中所有记录的关键字，则R[i]就是插入原位置。
2．改进的方法
　　一种查找比较操作和记录移动操作交替地进行的方法。
具体做法：
　将待插入记录R[i]的关键字从右向左依次与有序区中记录R[j](j=i-1，i-2，…，1)的关键字进行比较：
　① 若R[j]的关键字大于R[i]的关键字，则将R[j]后移一个位置；
②若R[j]的关键字小于或等于R[i]的关键字，则查找过程结束，j+1即为R[i]的插入位置。
　关键字比R[i]的关键字大的记录均已后移，所以j+1的位置已经腾空，只要将R[i]直接插入此位置即可完成一趟直接插入排序。
直接插入排序算法
1．算法描述
实现程序
void insert_sort(ElemType a[],int n)
//待排序元素用一个数组a表示，数组有n个元素
{ int i,j;
ElemType t;
for ( i=1; i<n; i++) //i表示插入次数，共进行n-1次插入
{ t=a[i]; //把待排序元素赋给t
j=i-1;
while ((j>=0)&& (t<a[j]))
{ a[j+1]=a[j]; j--; } // 顺序比较和移动
a[j+1]=t;}
}
4、直接插入排序的效率分析
（1）时间复杂度
从时间分析，首先外层循环要进行n-1次插入，每次插入最少比较一次（正序），移动两次；最多比较i次，移动i＋2次（逆序）（i=1，2，…，n-1）。若分别用Cmin
，Cmax 和Cave表示元素的总比较次数的最小值、最大值和平均值，用Mmin ，Mmax 和Mave表示元素的总移动次数的最小值、最大值和平均值，则上述直接插入算法对应的这些量为：
Cmin=n-1 Mmin=2（n-1）
Cmax=1+2+…+n-1=（n2-n）/2 Mmax=3+4+…+n+1=（n2+3n-4）/2
Cave=（n2+n-2）/4 Mmax=（n2+7n-8）/4
因此，直接插入排序的时间复杂度为O（n2）。
由上面对时间复杂度的分析可知,当待排序元素已从小到大排好序(正序)或接近排好序时,所用的比较次数和移动次数较少;当待排序元素已从大到小排好序(逆
序)或接近排好序时,所用的比较次数和移动次数较多,所以插入排序更适合于原始数据基本有序(正序)的情况.
插入法虽然在最坏情况下复杂性为O(n2)，但是对于小规模输入来说，插入排序法是一个快速的排序法。许多复杂的排序法，在规模较小的情况下，都使用插入排序法来进行排序，比如快速排序。
（2）空间复杂度
首先从空间来看，它只需要一个元素的辅助空间，用于元素的位置交换O(1)
（3）稳定性:
插入排序是稳定的,因为具有同一值的元素必然插在具有同一值得前一个元素的后面,即相对次序不变.
（4）结构的复杂性及适用情况
插入排序是一种简单的排序方法,他不仅适用于顺序存储结构(数组),而且适用于链接存储结构,不过在链接存储结构上进行直接插入排序时,不用移动元素的位置,而是修改相应的指针。


希尔排序：
希尔排序因计算机科学家Donald L. Shell而得名，他在1959年发现了希尔排序算法。希尔排序基于插入排序，但是增加了一个新的特性，大大地提高了插入排序的执行效率。
依靠这个特别的实现机制，希尔排序对于多达几千个数据项的，中等大小规模的数组排序表现良好。希尔排序不像快速排序和其它时间复杂度为O(N*logN)
的排序算法那么快，因此对非常大的文件排序，它不是最优选择。但是，希尔排序比选择排序和插入排序这种时间复杂度为O(N2)的排序算法还是要快得多，并
且它非常容易实现。它在最坏情况下的执行效率和在平均情况下的执行效率相比没有差很多。
插入排序：复制的次数太多
由于希尔排序是基于插入排序的。回想一下在插入排序执行的一半的时候，标记符左边这部分数据项都是排过序的，而标记右边的数据项则没有排过序。这个算法取
出标记符所指的数据项，把它存储在一个临时变量里。接着，从刚刚被移除的数据项的左边第一个单元开始，每次把有序数据项向右移动一个单元，直到存储在临时
变量里的数据项能够有序回插。
下面是插入排序带来的问题。假设一个很小的数据项在很靠近右端的位置上，这里本来应该是值比较大的数据项所在的位置。把这个小数据项移动到在左边的正确位
置上，所有的中间数据项都必须向右移动一位。这个步骤对每一个数据项都执行了将近N次的复制。虽不是所有数据项都必须移动N个位置，但是数据项平均移动了
N/2个位置，这就是执行了N次N/2个移位，总共是N2/2次复制。因此，插入排序的执行效率是O(N2)。
如果能以某种方式不必一个一个地移动所有中间的数据项，就能把较小的数据项移动到左边，那么这个算法的执行效率就会有很大的改进。
N-增量排序
希尔排序通过加大插入排序中元素之间的间隔，并在这些有间隔的元素中进行插入排序，从而使数据项能大跨度地移动。当这些数据项排过一趟序后，希尔排序算法
减小数据项的间隔再进行排序，依此进行下去。进行这些排序时数据项之间的间隔被称为增量，并且习惯上用字母H来表示。
现在有10个数据项，增量为4。在0、4和8号位置上的数据项已经有序了。
当对0、4和8号数据项完成排序之后，算法向右移一步，对1、5和9号数据项进行排序。这个排序过程持续进行，直到所有的数据项都已经完成了4－增量排序，也就是说所有间隔为4的数据项之间都已经排列有序。
在完成以4为增量的希尔排序之后，数组可以看成是由4个子数组组成：（0,4,8），（1,5,9），（2,6）和（3,7），这四个子数组内分别是完全有序的。这些子数组相互交错着排列，然而彼此独立。
注意，在这个例子中，在完成以4为增量的希尔排序后，所有元素离它在最终有序序列中的位置相差都不到两个单元。这就是数组“基本有序”的含义，也正是希尔排序的奥秘所在。通过创建这种交错的内部有序的数据项**，把完成排序所必需的工作量降到了最小。
插入排序对基本有序的数组排序是非常有效的。如果插入排序只需要把数据项移动一位或者两位，那么算法大概需要O(N)时间。这样，当数组完成4-增量排序
之后，可以进行普通的插入排序，即1-增量排序。4-增量排序和1-增量排序结合起来应用，比前面不执行4-增量排序而仅仅应用普通的插入排序要快得多。
减小间隔
上面已经演示了以4为初始间隔对包含10个数据项的数组进行排序的情况。对于更大的数组开始的间隔也应该更大。然后间隔不断减小，直到间隔变成1。
举例来说，含有1000个数据项的数组可能先以364为增量，然后以121为增量，以40为增量，以13为增量，以4为增量，最后以
1为增量进行希尔排序。用来形成间隔的数列被称为间隔序列。这里所表示的间隔序列由Knuth提出，此序列是很常用的。数列以逆向形式从1开始，通过递归
表达式
h=3*b+1
来产生，初始值为1。
还有一些其他的方法也能产生间隔序列；后面会讲到这个问题。首先，来研究使用Kunth序列进行希尔排序的情况。
在排序算法中，首先在一个短小的循环中使用序列的生成公式来计算出最初的间隔。h值最初被赋为1，然后应用公式h=3*h+1生成序列
1,4,13,40,121,364，等等。当间隔大于数组大小的时候，这个过程停止。对于一个含有1000个数据项的数组，序列的第七个数字，1093
就太大了。因此，使用序列的第六个数字作为最大的数字来开始这个排序过程，作364-增量排序。然后，每完成一次排序全程的外部循环，用前面提供的此公式
倒推式来减小间隔：
h=(h-1)/3
这个倒推的公式生成逆置的序列364,121,40,13,4,1。从364开始，以每一个数字作为增量进行排序。当数组用1-增量排序后，算法结束。
希尔排序比插入排序快很多，它是基于什么原因呢？当h值大的时候，数据项每一趟排序需要移动元素的个数很少，但数据项移动的距离很长。这是非常有效率的。
当h减小时，每一趟排序需要移动的元素的个数增多，但是此时数据项已经接近于它们排序后最终的位置，这对于插入排序可以更有效率。正是这两种情况的结合才
使希尔排序效率那么高。
注意后期的排序过程不撤销前期排序所做的工作。例如，已经完成了以40-增量的排序的数组，在经过以13-增量的排序后仍然保持了以40-增量的排序的结果。如果不是这样的话，希尔排序就无法实现排序的目的。


其他间隔序列
选择间隔序列可以称得上是一种魔法。至此只讨论了用公式h=h*3+1生成间隔序列，但是应用其他间隔序列也取得了不同程序的成功，只是一个绝对的条件，就是逐渐减小的间隔最后一定要等于1，因此最后一趟排序是一次普通的插入排序。
在希尔的原稿中，他建议初始的间距为N/2，简单地把每一趟排序分成了两半。因此，对于N=100的数组逐渐减小的间隔序列为
50,25,12,6,3,1。这个方法的好处是不需要在不开始排序前为找到初始的间隔而计算序列；而只需要用2整除N。但是，这被证明并不是最好的数
列。尽管对于大多数的数据来说这个方法还是比插入排序效果好，但是这种方法有时会使运行时间降到O(N2)，这并不比插入排序的效率更高。
这个方法的一个变形是用2.2而非2来整除每一个间隔。对于N=100的数组来说，会产生序列45,20,9,4,1。这比用2整除显著改善了效果，因为
这样避免了某些导致时间复杂度为O(N2)的最坏情况的发生。不论N为何值，都需要一些额外的代码来保证序列的最后取值为1。这产生了和清单中所列的
Knuth序列差不多的结果。
递减数列的另一个可能是
if(h<5)
h=1;
else
h=(5*h-1)/11;
间隔序列中的数字互质通常被认为很重要：也就是说，除了1之外它们没有公约数。这个约束条件使每一趟排序更有可能保持前一趟排序已排好的效果。希尔最初以N/2为间隔的低效性就是归咎于它没有遵守这个准则。
或许还可以设计出像如上讲述的间隔序列一样好的间隔序列。但是不管这个间隔序列是什么，都应该能够快速地计算，而不会降低算法的执行速度。
希尔排序的效率
迄今为止，除了在一些特殊的情况下，还没有人能够从理论上分析希尔排序的效率。有各种各样基于试验的评估，估计它的时间级从O(N3/2)到O(N7/6)。

[基数排序]
下面说到我们的重头戏，基数排序(Radix Sort)。上述的基数排序和桶排序都只是在研究一个关键字的排序，现在我们来讨论有多个关键字的排序问题。
假设我们有一些二元组(a,b)，要对它们进行以a为首要关键字，b的次要关键字的排序。我们可以先把它们先按照首要关键字排序，分成首要关键字相
同的若干堆。然后，在按照次要关键值分别对每一堆进行单独排序。最后再把这些堆串连到一起，使首要关键字较小的一堆排在上面。按这种方式的基数排序称为MSD(Most Significant Dight)排序。
第二种方式是从最低有效关键字开始排序，称为LSD(Least Significant Dight)排序。首先对所有的数据按照次要关键字排序，然后对所有的数据按照首要关键字排序。要注意的是，使用的排序算法必须是稳定的，否则就会取消前一次排序的结果。由于不需要分堆对每堆单独排序，LSD方法往往比MSD简单而开销小。下文介绍的方法全部是基于LSD的。
通常，基数排序要用到计数排序或者桶排序。使用计数排序时，需要的是Order数组。使用桶排序时，可以用链表的方法直接求出排序后的顺序。下面是一段用桶排序对二元组基数排序的程序：
?View Code CPP
基数排序是一种用在老式穿卡机上的算法。一张卡片有80列，每列可在12个位置中的任一处穿孔。排序器可被机械地”程序化”以检查每一迭卡片中的某
一列，再根据穿孔的位置将它们分放12个盒子里。这样，操作员就可逐个地把它们收集起来。其中第一个位置穿孔的放在最上面，第二个位置穿孔的其次，等等。
对于一个位数有限的十进制数，我们可以把它看作一个多元组，从高位到低位关键字重要程度依次递减。可以使用基数排序对一些位数有限的十进制数排序。

[三种线性排序算法的比较]
从整体上来说，计数排序，桶排序都是非基于比较的排序算法，而其时间复杂度依赖于数据的范围，桶排序还依赖于空间的开销和数据的分布。而基数排序是一种对多元组排序的有效方法，具体实现要用到计数排序或桶排序。
相对于快速排序、堆排序等基于比较的排序算法，计数排序、桶排序和基数排序限制较多，不如快速排序、堆排序等算法灵活性好。但反过来讲，这三种线性
排序算法之所以能够达到线性时间，是因为充分利用了待排序数据的特性，如果生硬得使用快速排序、堆排序等算法，就相当于浪费了这些特性，因而达不到更高的
效率。
在实际应用中，基数排序可以用于后缀数组的倍增算法，使时间复杂度从O(N*logN*logN)降到O(N*logN)。线性排序算法使用最重要的是，充分利用数据特殊的性质，以达到最佳效果。

好帖，求教一个问题，你知不知道怎么把字符串转换成运算表达式，最后得到整型的输出结果...跪求

atoi();

谢谢