【IT168 技术】排序

　　排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。分内部排序和外部排序，若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。

　　概念

　　将杂乱无章的数据元素，通过一定的方法按关键字顺序排列的过程叫做排序。

　　常见排序算法

　　快速排序、希尔排序、堆排序、直接选择排序不是稳定的排序算法，而基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。

　　分类

　　稳定排序：假设在待排序的文件中，存在两个或两个以上的记录具有相同的关键字，在 用某种排序法排序后，若这些相同关键字的元素的相对次序仍然不变，则这种排序方法 是稳定的。其中冒泡，插入，基数，归并属于稳定排序，选择，快速，希尔，堆属于不稳定排序。

　　就地排序：若排序算法所需的辅助空间并不依赖于问题的规模n，即辅助空间为O(1)， 则称为就地排序。

　　排序算法

　　冒泡排序

　　持续比较相邻元素，大的挪到后面，因此大的会逐步往后挪，故称之为冒泡。 复杂度分析：平均情况与最坏情况均为 O(n^2), 使用了 temp 作为临时交换变量，空间复杂度为 O(1)

　　堆排序

　　堆排序的是集合了插入排序的单数组操作，又有归并排序的时间复杂度，完美的结合了2者的优点。

　　直接插入排序

　　直接插入排序是一种最简单的排序方法，它的基本操作是将一个记录插入到已排好的有序的表中，从而得到一个新的、记录数增1的有序表。当前元素的前面元素均为有序，要插入时，从当前元素的左边开始往前找(从后往前找)，比当前元素大的元素均往右移一个位置，最后把当前元素放在它应该呆的位置就行了。

　　归并排序

　　归并排序(Merge Sort)与快速排序思想类似：将待排序数据分成两部分，继续将两个子部分进行递归的归并排序;然后将已经有序的两个子部分进行合并，最终完成排序。

　　其时间复杂度与快速排序均为O(nlogn)，但是归并排序除了递归调用间接使用了辅助空间栈，还需要额外的O(n)空间进行临时存储。从此角度归并排序略逊于快速排序，但是归并排序是一种稳定的排序算法，快速排序则不然。

　　所谓稳定排序，表示对于具有相同值的多个元素，其间的先后顺序保持不变。对于基本数据类型而言，一个排序算法是否稳定，影响很小，但是对于结构体数组，稳定排序就十分重要。

　　快速排序

　　通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

　　直接选择排序

　　所谓选择排序，就是每次找到未排序中最小的(最大的也行)元素的位置，找到后与该位置与未排序序列的第一个元素交换值，直到该序列成为有序序列。

　　初始状态整个序列为无序序列，每次交换都使有序序列的长度加一，无序序列的起始位置后移一位。选择排序的平均时间复杂度为O(n^2)，且选择排序相对不稳定。

　　希尔排序

　　Shellsort是最古老的排序算法之一，该算法以其发明者Donald L. Shell的名字命名。

　　在ShellSort排序算法之前的算法时间复杂度基本都是O(n2)O(n2)，该算法是突破这个时间复杂度的第一批算法之一。

　　另外 Shellsort 是快速、易于理解和易于实现的。 然而，其复杂度分析有点复杂。