排序算法总结与C代码

最近参加笔试，感觉排序算法需要好好的整理一下，感觉部分排序算法理解得不是很清楚；通过这段时间的整理与总结来对排序算法的一个复习吧。

主要参考了《大话数据结构》：
1. 冒泡排序的基本思想：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。

n(n-1)/2。也因此无论在序列何种情况下，它都不会有优秀的表现，可见对数据的有序性不敏感。它虽然比较次数多，而对于交换次数而言，当最好的时候，交换为0次，最坏的时候交换次数为n-1次，所以数据交换量却很少，基于时间复杂度是比较与交换次数的总和，因此总的时间复杂度依然为O(n^2)。尽管与冒泡排序算法的时间复杂度相同，但是简单选择排序的性能上还是略优于冒泡排序。
3.直接插入排序
直接插入排序的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的记录数增1的有序表
n-1次比较，由于每次都是a[j]>a[j-1]因此没有移动记录，时间复杂度为O(n);在最坏情况下，将需要(n+2)(n-1)/2次比较,并且将移动次数也达到最大值(n+4)(n-1)/2。如果排序记录是随机的，根据概率相同原则，平均比较和移动次数约为你(n^2)/4,所以直接插入排序的时间复杂度为O(n^2).
4.希尔排序
希尔排序的基本思想：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，并使整个序列中的记录基本有序，再对全体记录进行一次排序。
5.堆排序
堆排序的思想：首先将待排序列构建为大顶堆(大顶堆：每个结点的值大于或等于其左右孩子结点的值)。此时整个序列的最大值就是堆顶的根结点。将它移走（其实就是讲其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的n-1个子序列重新构造成一个堆，这样就会得到n个元素中的次大值。如此反复执行，便得到一个有序序列。
    在正式排序时，第i次取堆顶记录重建堆需要用O(logi)的时间（完全二叉树的某个结点到根节点的距离为[logi]+1），并且需要取n-1次堆顶记录，因此重建堆的时间复杂度为O(nlogn)。
    所以总体来说，堆排序的时间复杂度为O(nlogn)。由于堆排序对原始记录的排序状态并不敏感，因此无论最好、最坏平均时间复杂度均为O(nlogn)。所以一般在小规模的序列中不合适，但对于较大的序列，将表现出优越的性能。
6.归并排序
归并排序思想：假设初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度的长度为1，然而两两归并，得到[n/2]([x]表示不小于x的最小整数)个长度为2或1的有序子序列；再两两归并,.....,如此重复，直至得到一个长度为n的有序序列为止。
(1) 平方阶(O(n2))排序
　　各类简单排序，例如直接插入、简单选择和冒泡排序； 
(2) 线性对数阶(O(nlog2n))排序
　　如快速排序、堆排序和归并排序； 
(3) O(n1+§))排序
　　§是介于0和1之间的常数。希尔排序便是一种；
排序方法的选择
因为不同的排序方法适应不同的应用环境和要求，所以选择合适的排序方法很重要
(1)若n较小，可采用直接插入或直接选择排序。
当记录规模较小时，直接插入排序较好，它会比选择更少的比较次数；
但当记录规模较大时，因为直接选择移动的记录数少于直接插人，所以宜用选直接选择排序。
这两种都是稳定排序算法。
(2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜(这里的随机是指基准取值的随机，原因见上的快速排序分析)；这里快速排序算法将不稳定。
(3)若n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。
快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；
堆排序虽不会出现快速排序可能出现的最坏情况。但它需要建堆的过程。这两种排序都是不稳定的。
　 归并排序是稳定的排序算法，但它有一定数量的数据移动，所以我们可能过与插入排序组合，先获得一定长度的序列，然后再合并，在效率上将有所提高。