内部排序小结

一、重要概念：
内部排序 VS 外部排序
内部排序：整个过程完全在内存中进行的排序。
外部排序：由于待排序的记录数据量太大，内存无法容纳全部数据，排序需要借助外部存储
                 设备才能完成的排序。
稳定排序 VS 不稳定排序
稳定性是排序算法的一种特性。有些排序算法是稳定的，有些排序算法不是稳定的。如果待排序
的元素中有两个元素关键字相同，如果排序后算法能保证其顺序不会变化则说明该算法是稳定的，
反之，该算法是不稳定的。
----------------------------------------------------------------------------------------
二、内部排序的分类。
1，交换类排序。（冒泡排序，快速排序）
2，选择类排序。（简单选择排序，堆排序）
3，插入类排序。（直接插入排序，折半插入排序，希尔排序）
4，归并类排序。（归并排序）。
-----------------------------------------------------------------------------------------
三、排序算法分析与比较。
3.1，交换类排序。

冒泡排序

    最坏的情况是待排序的记录是逆序的，此时，每一趟冒泡排序需要进行i次比较，3i次移动。
一共有n-1趟， 因此该算法的时间复杂度为O(n^2),空间复杂度为O(1)，冒泡排序算法是稳定
的排序算法。

快速排序

     快速排序最好的情况是每次将待排序的记录都等分为二，此时时间复杂度为O(nlog2^n)。
最坏情况下，待排序记录已经排好序，此时总共的比较次数为n(n-1)/2，此时时间复杂度为O(n^2)。
     快速排序的时间复杂度为O(nlogn)，空间复杂度为O(log2^n)，它是一种不稳定的排序算法。
举反例如下：待排序序列为{3,2,(2)},则一趟排序后记录为{(2),2,3}。
           
3.2，选择类排序。

简单选择排序

无论待排序记录的初始排列如何，简单选择排序总的比较次数总为n(n-1)/2，因为它每趟比较的
次数为n-i，i的范围从1到n-1。最好的情况下，简单选择排序算法的移动次数为0，最坏情况下
移动的3(n-1)。

简单选择排序算法的时间复杂度为O(n^2)，空间复杂度为O(1)，它是不稳定的排序算法。举反例如下：
待排序记录为{6,8,(6),2,7}，一趟排序后记录为{2,8,(6),6,7}，二趟排序后记录为{2,(6),8,6,7}。

选择排序的过程：（用{6,8,(6),2,7}为例子）
{6，8，(6)，2，7}
{2，8，(6)，6，7}
{2，(6)，8，6，7}
{2，(6)，6，8，7}
{2，(6)，6，7，8}

堆排序：
堆排序是种比较重要的排序方法，在工程应用中用的比较广，在内核中的排序都是用的堆排序。
堆排序的时间复杂度为O(nlogn)。而且是不稳定的排序算法。

3.3，插入类排序。

直接插入排序

如果待排序记录之间是顺序排列，此时整个排序过程中元素比较的次数为n-1次，移动次数为0次。
如果待排序记录 之间是逆序排列，第i趟排序比较次数为i，移动的次数为i+1，其中i的范围是2到n。
因此，整个排序过程中元素的比较次数为(n+2)(n-1)/2， 移动次数为(n+4)(n-1)/2。

直接插入排序算法的时间复杂度为O(n^2)，空间复杂度为O(1)。从直接插入排序算法的实现可以
发现，位置靠后的记录是不可能插入到相同大小的记录之前的，因此直接插入排序算法是稳定的。

直接插入排序的过程：（用{6,8,(6),2,7}为例子）
{6，8，(6)，2，7}
{6，8，(6)，2，7}
{6，(6)，8，2，7}
{2，6，(6)，8，7}
{2，6，(6)，7，8}

折半插入排序

折半插入排序算法与直接插入排序算法相比，每趟的比较次数为log2^i，因此整体的比较次数为
O(nlog2^n)。但是折半算法的移动次数较直接插入算法并未改变。

折半算法的时间复杂度仍然是O(n^2)，空间复杂度为O(1)。从算法实现可以看出折半插入排序算法
是稳定的。

希尔排序

希尔排序利用了当“待排序记录n较小，序列基本有序”时使用直接插入算法性能较好这一特点而改进。
希尔排序算法的时间复杂度为O(n^1.5)，空 间复杂度为O(1)，它是不稳定的排序算法。举反例如下：
待排序序列为{2，4，1，(2)}，设delta[1]=2，则一趟排序后序列为{1, (2),2,4}。

---------------------------------------------------------------------------------------------
四、总结


参考：http://edsionte.com/techblog/archives/3857