常用的数据结构排序算法分类

首先对排序有个宏观的了解， 排序的思想是这样的，将有序的记录序列（或称）按照一定的关键字，将一个序列排列成想要得到的一个新的序列。基本上现在的排序可以区分以下几类：内排序和外排序，稳定排序和不稳定排序。

内排序：整个排序过程，所有元素调到内存中进行的排序。内排序效率用比较次数来衡量。

外排序：数据量较大的情况下，需要借助外部存储设备才能完成排序。外排序用读/写外存的次数来衡量效率，块与块之间不能保证有序。

排序的性能比较最基本的是其稳定性，之后就是时间复杂度，空间复杂度了。

稳定排序：对于相的元素来说，在排序之前和之后的顺序是一样的。

不稳定排序：对于相同的元素来说，在排序之前和之后顺序发生了变化。

根据使用的实际情况，用到内排序的还是较多，所以重点讨论几种内排序。几种常见的排序算法大概有以下图中所示几种：

那么，举几个例子，讲解下其应用的相关排序算法。

（一）冒泡排序

         思想：反复扫描待排序序列，在扫描的过程中顺次比较相邻的两个元素的大小，若逆序就交换位置。第一趟，从第一个数据开始，比较相邻的两个数据，（以升序为例）如果大就交换，得到一个最大数据在末尾；然后进行第二趟，只扫描前n-1个元素，得到次大的放在倒数第二位。以此类推，最后得到升序序列。如果在扫描过程中，发现没有交换，说明已经排好序列，直接终止扫描。所以最多进行n-1趟扫描。

例：设记录key集合k={50，36，66，76，95，12，25，36}，排序过程如下：

最后排序结果为红色背景的顺序。

（二）简单选择排序

思想：第一趟时，从第一个记录开始，通过n – 1次关键字的比较，从n个记录中选出关键字最小（大）的记录，并和第一个（可以是最后一个）记录进行交换。第二趟从第二个记录开始，选择最小（大）的和第二个记录交换。以此类推，直至全部排序完毕。

例：设记录key集合k={50，36，66，76，95，12，25，36}，排序过程如下：

（三）快速排序

思想：冒泡排序一次只能消除一个逆序，为了能一次消除多个逆序，采用快速排序。以一个关键字为轴，从左从右依次与其进行对比，然后交换，第一趟结束后，可以把序列分为两个子序列，然后再分段进行快速排序，达到高效。

例：设记录的key集合k={50，36，66，76，36，12，25，95}，每次以集合中第一个key为基准的快速排序过程如下：

（四）直接插入排序

思想：最基本的插入排序，将第i个插入到前i-1个中的适当位置。

例： 设文件记录的key集合k={50，36，66，76，95，12，25，36}（考虑到对记录次key排序的情况，允许多个key相同。如此例中有2个key为36，后一个表示成36，以示区别），按直接插入排序方法对k的排序过程如下：k={50，36，66，76，95，12，25，36}

上面呢，通过例题加图示的方式，简单的分析了其中的4个排序算法，是否理解了呢？好了，其他排序算法的分析我们以后有时间再讲。当然，理解了这种套路的话，或者你来总结一下。