各种算法的说明

<1>直接选择排序(Selection Sort)：简单的选择排序，它的比较次数一定：n(n-1)/2。也因此无论在序列何种情况下，它都不会有优秀的表现（从上100K的正序和反序数据可以发现它耗时相差不多，相差的只是数据移动时间），可见对数据的有序性不敏感。它虽然比较次数多，但它的数据交换量却很少。所以我们将发现它在一般情况下将快于冒泡排序。
# /*
#     2.直接选择排序 选择排序是这样实现的：
#         1.首先在未排序序列中找到最小元素，存放到排序序列的起始位置
#         2.然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。
#         3.以此类推，直到所有元素均排序完毕。
# */ 



<2>直接插入排序(Insertion Sort)：简单的插入排序，每次比较后最多移掉一个逆序，因此与冒泡排序的效率相同。但它在速度上还是要高点，这是因为在冒泡排序下是进行值交换，而在插入排序下是值移动，所以直接插入排序将要优于冒泡排序。直接插入法也是一种对数据的有序性非常敏感的一种算法。在有序情况下只需要经过n-1次比较，在最坏情况下，将需要n(n-1)/2次比较。
# /*        
#         1.直接插入排序 一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
# 
#        1. 从第一个元素开始，该元素可以认为已经被排序
#        2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
#        3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
#        4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
#        5. 将新元素插入到该位置中
#        6. 重复步骤2
# */ 



<3>冒泡排序(Bubble Sort)：将相邻的两个数据元素按关键字进行比较，如果反序，则交换。对于一个待排序的数据元素序列，经一趟排序后最大值数据元素移到最大位置，其它值较大的数据元素向也最终位置移动，此过程为一次起泡。然后对下面的记录重复上述过程直到过程中没有交换为止，则已完成对记录的排序。
# /*        
#         3.冒泡排序 冒泡排序是这样实现的：
#         
#            1. 首先将所有待排序的数字放入工作列表中。
#            2. 从列表的第一个数字到倒数第二个数字，逐个检查：若某一位上的数字大于他的下一位，则将它与它的下一位交换。
#            3. 重复2号步骤(倒数的数字加1。例如：第一次到倒数第二个数字，第二次到倒数第三个数字，依此类推...)，直至再也不能交换。
#         
#         冒泡排序的平均时间复杂度与插入排序相同，也是平方级的，但也是非常容易实现的算法
#  


<4>快速排序(Quick Sort)：是冒泡排序的改进，它通过一次交换能消除多个逆序，这样可以减少逆序时所消耗的扫描和数据交换次数。在最优情况下，它的排序时间复杂度为Ｏ(nlog2n)。即每次划分序列时，能均匀分成两个子串。但最差情况下它的时间复杂度将是Ｏ(n^2)。即每次划分子串时，一串为空，另一串为m-1（程序中的100K正序和逆序就正是这样，如果程序中采用每次取序列中部数据作为划分点，那将在正序和逆时达到最优）。从100K中正序的结果上看“快速排序”会比“冒泡排序”更慢，这主要是“冒泡排序”中采用了提前结束排序的方法。有的书上这解释“快速排序”，在理论上讲，如果每次能均匀划分序列，它将是最快的排序算法，因此称它作快速排序。虽然很难均匀划分序列，但就平均性能而言，它仍是基于关键字比较的内部排序算法中速度最快者。
# /*    
# 5.快速排序     快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。
# 
# 步骤为：
# 
#    1. 从数列中挑出一个元素，称为 "基准"（pivot），
#    2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分割之后，该基准是它的最后位置。这个称为分割（partition）操作。
#    3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
# 
# 递回的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递回下去，但是这个演算法总会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
# */


<5>希尔排序(Shell Sort)：增量的选择将影响希尔排序的效率。但是无论怎样选择增量，最后一定要使增量为１，进行一次直接插入排序。但它相对于直接插入排序，由于在子表中每进行一次比较，就可能移去整个经性表中的多个逆序，从而改善了整个排序性能。希尔排序算是一种基于插入排序的算法，所以对数据有序敏感。



<6>归并排序(Merge Sort)：归并排序是一种非就地排序，将需要与待排序序列一样多的辅助空间。在使用它对两个己有序的序列归并，将有无比的优势。其时间复杂度无论是在最好情况下还是在最坏情况下均是 O(nlog2n)。对数据的有序性不敏感。若数据节点数据量大，那将不适合。但可改造成索引操作，效果将非常出色。


排序方法的选择

因为不同的排序方法适应不同的应用环境和要求，所以选择合适的排序方法很重要

(1)若n较小，可采用直接插入或直接选择排序。
当记录规模较小时，直接插入排序较好，它会比选择更少的比较次数；
但当记录规模较大时，因为直接选择移动的记录数少于直接插人，所以宜用选直接选择排序。
这两种都是稳定排序算法。


(2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜(这里的随机是指基准取值的随机，原因见上的快速排序分析)；这里快速排序算法将不稳定。


(3)若n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。
快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；
堆排序虽不会出现快速排序可能出现的最坏情况。但它需要建堆的过程。这两种排序都是不稳定的。
　归并排序是稳定的排序算法，但它有一定数量的数据移动，所以我们可能过与插入排序组合，先获得一定长度的序列，然后再合并，在效率上将有所提高。


(4)特殊的箱排序、基数排序
它们都是一种稳定的排序算法，但有一定的局限性：
1>关键字可分解。
2>记录的关键字位数较少，如果密集更好
3>如果是数字时，最好是无符号的，否则将增加相应的映射复杂度，可先将其正负分开排序。