排序算法的总结及感悟
排序的基本概念
排序：有n个记录的序列{R1，R2，…，Rn}，其相应关键字的序列是{K1，K2， …，Kn }，相应的下标序列为1，2，…， n。通过排序，要求找出当前下标序列1，2，…， n的一种排列p1，p2， …，pn，使得相应关键字满足如下的非递减（或非递增）关系，即：Kp1≤ Kp2≤…≤ Kpn，这样就得到一个按关键字有序的记录序列：{Rp1， Rp2， …， Rpn}。
1、内部排序：整个排序过程完全在内存中进行，称为内部排序。
2、外部排序：由于待排序记录数据量太大，内存无法容纳全部数据，排序需要借助外部存储设备才能完成，称为外部排序。
3、在排序过程中，一般进行两种基本操作：①比较两个关键字的大小。
②将记录从一个位置移动到另一个位置。
【插入类排序】
基本思想：在一个已排好序的记录子集的基础上，每一步将下一个待排序的记录有序插入到已排好序的记录子集中，直到将所有待排记录全部插入为止。
（1）直接插入排序
说明：直接插入排序方法是最稳定的排序方法，直接插入排序算法简便，比较适用于待排序记录数目少且基本有序的情况。
算法思想：基本操作是将第i个记录插入到前面i-1个已排好序的记录中，具体过程为：将第i个记录的关键字Ki顺次与其前面记录的关键字Ki-1，Ki-2，…K1进行比较，将所有关键字大于Ki的记录依次向后移动一个位置，直到遇见一个关键字小于或者等于Ki的记录Kj，此时Kj后面必为空位置，将第i个记录插入空位置即可。
void InsSort(RecordType r[],int length) /*对记录数组r做直接插入排序，length为数组的长度*/
{
for ( i=2 ; i< length ; i++ )
{
r[0]=r[i]; j=i-1; /*将待插入记录存放到r[0]中*/
while (r[0].key< r[j].key ) /* 寻找插入位置 */
{r[j+1]= r[j]; j=j-1;}
r[j+1]=r[0]; /*将待插入记录插入到已排序的序列中*/
}
} /* InsSort */
该算法的要点是：①使用监视哨r[0]临时保存待插入的记录。②从后往前查找应插入的位置。③查找与移动用同一循环完成。
直接插入排序的时间复杂度为T（n）=O（n的平方），空间复杂度为S（n）=O（1）。
（2）折半插入排序法算法分析：采用折半插入排序法，可减少关键字的比较次数。每插入一个元素，需要比较的次数最大为折半判定树的深度，如插入第i个元素时，设i=2j,则需进行log2i次比较，因此插入n-1个元素的平均关键字的比较次数为O(nlog2n)。虽然折半插入排序法与直接插入排序法相比较，改善了算法中比较次数的数量级，但其并未改变移动元素的时间耗费，所以折半插入排序的总的时间复杂度仍然是O(n2)。
（3）堆排序
说明：堆排序是对树型选择排序的进一步改进。采用堆排序时，只需要一个记录大小的辅助空间。堆排序是在排序过程中，将向量中存储的数据看成一棵完全二叉树，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择关键字最小的记录，即待排序记录仍采用向量数组方式存储，并非采用树的存储结构，而仅仅是采用完全二叉树的顺序结构的特征进行分析而已。
堆中根结点的关键字最大，称为大根堆。反之如果这棵完全二叉树中任意结点的关键字大于或者等于其左孩子和右孩子的关键字（当有左孩子或右孩子时），对应的堆为小根堆。
堆排序的过程主要需要解决两个问题：(1) 按堆定义建初堆（2）去掉最大元之后重建堆，得到次大元。
利用堆进行排序：
进行堆排序的步骤：
①将待排序记录按照堆的定义建初堆，并输出堆顶元素。
②调整剩余的记录序列，利用筛选法将前n-i个元素重新筛选建成为一个新堆，再输出堆顶元素。
③重复执行步骤②n-1次进行筛选,新筛选成的堆会越来越小，而新堆后面的有序关键字会越来越多，最后使待排序记录序列成为一个有序的序列，这个过程称之为堆排序。
堆排序算法分析：堆排序是一种不稳定的排序方法，它不适用于待排序记录个数n较少的情况，但对于n较大的文件还是很有效的。
【交换类排序】
交换类的排序思想：通过一系列交换逆序元素进行排序的方法。
（1）冒泡排序：冒泡排序是一种简单的交换排序方法，它是通过对相邻的数据元素进行交换，逐步将待排序序列变成有序序列的过程。
（2）快速排序：在待排序记录序列中选取一个记录（通常选取第一个记录）作为枢轴，其关键字设为Ki，然后将其余关键字小于ki的记录移到前面，而将关键字大于或等于ki的记录移到后面，结果将排序记录序列分成两个字表，最后将关键字ki的记录插到其其分界线的位置处。
【选择类排序】
选择排序的基本思想是：每一趟在n-i+1（i=1，2，…n-1）个记录中选取关键字最小的记录作为有序序列中第i个记录。
（1）简单选择排序
基本思想：第i趟简单选择排序是指通过n-i次关键字的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录进行交换。共需进行i-1趟比较，直到所有记录排序完成为止，在简单选择排序过程中，所需移动记录的次数比较少。最好情况下，即待排序记录初始状态就已经是正序排列了，则不需要移动记录。最坏情况下，即待排序记录初始状态是按逆序排列的，则需要移动记录的次数最多为3（n-1）。
简单选择排序的算法描述如下：
void SelectSort(RecordType r[], int length)
/*对记录数组r做简单选择排序，length为数组的长度*/
{ n=length;
for ( i=1 ; i<= n－１; ++i)
{k=i；
for ( j=i+1 ; j<= n ; ++j)
if (r[j].key < r[k].key ) k=j；
if ( k!=i)
{ x= r[i]； r[i]= r[k]； r[k]=x; }
}
} /* SelectSort */
（2）树型选择排序
基本思想：树型选择排序也称作锦标赛排序。它的基本思想是：先把待排序的n个记录的关键字两两进行比较，取出较小者。然后再在ën/2 û个较小者中，采用同样的方法进行比较选出每两个中的较小者，如此反复，直至选出最小关键字记录为止。
【归并排序】
基本思想：是将两个或两个以上有序表合并成一个新的有序表。假设初始序列含有n个记录，首先将这n个记录看成n个有序的子序列，每个子序列的长度为1，然后两两归并，得到én/2ù个长度为2（n为奇数时，最后一个序列的长度为1）的有序子序列；在此基础上，再进行两两归并，如此重复，直至得到一个长度为n的有序序列为止。这种方法被称作2-路归并排序。
归并排序的算法分析：归并排序中一趟归并中要多次用到2-路归并算法，一趟归并排序的操作是调用én/2h ù次算法merge 将r1[1…n]中前后相邻且长度为h的有序段进行两两归并，得到前后相邻、长度为2h的有序段，并存放在r[1…n]中，其时间复杂度为O(n)。整个归并排序需进行m（m=log2n）趟2-路归并，所以归并排序总的时间复杂度为O（nlog2n）。在实现归并排序时，需要和待排记录等数量的辅助空间，空间复杂度为O(n)。
各种排序方法的综合比较：
简单排序一般只用于n值较小的情况；
归并排序适用于n值较大的情况；
基数排序适用于n值很大而关键字的位数d较小的序列；
快速排序是排序方法中最好的方法。
从排序的稳定性来看，基数排序是稳定的，除了简单选择排序，其它各种简单排序法也是稳定的。多数情况下，排序是按记录的主关键字进行的，此时不用考虑排序方法的稳定性。如果排序是按记录的次关键字进行的，则应充分考虑排序方法的稳定性。