排序是数据结构中的重要知识点，也是考研中的必考内容，一般会在选择题第11题考察，最常见的题目类型是给出一串记录和经过若干趟排序之后的记录，判断可能属于哪种排序算法。只要能够深入理解课本中常见排序算法的工作原理，知道每种算法的排序特点（不需要手写代码），这类题目就能很容易做出。
内部排序：排序在内存完成；
外部排序：待排记录数据量过大，内存无法容纳全部数据，需要借助外存；
稳定性：相等的元素，若经过排序，这些元素的相对次序保持不变，则排序算法是稳定的，否则是不稳定的。
（1）--
直接插入排序核心思想：逐个处理待排序的记录，每条新记录与前面已排序的子序列进行比较，将它插入到子序列的正确位置。插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。
（2）--
折半插入排序是对直接插入排序算法的改进，主要区别是在插入到已排序的序列时采用折半查找（二分查找），很明显相比直接插入排序减少了元素比较次数。
（3）--
希尔排序也是对直接插入排序的改进，它是把序列按一定间隔分组，对每组使用直接插入排序；随着间隔减小，一直到1，使得整个序列有序。如图d表示间隔，也叫做增量，相同颜色是一组，当d=1时，序列有序。（希尔排序在考试中的出现频率还挺高的）。
（4）--
冒泡排序的实现原理：两两比较相邻的记录值,如果反序则交换,直到没有反序记录为止，冒泡排序每趟可以确定最大元素位置。（5）--
快速排序是应用最多的排序算法，因快速二字闻名。快速排序和归并排序一样，都是采用分治思想，其基本思想：在待排序表L[1...n]中任取一个元素pivot作为基准，通过一趟排序将待排序表划分为两独立的部分L[1...k-1]和L[k+1...n]，使得L[1...k-1]中所有元素小于pivot,L[k+1...n]中所有元素大于或等于pivot,则pivot放在了其最终位置L(k)上，这个过程称作一趟快速排序，而后分别递归地对两个子表重复上述过程，直至每部分内只有一个元素或空为止，即所有元素放在了其最终位置上。
下图为一次快排过程，随机选择一个元素key作为基准，设置低位指针lo和高位指针hi。
（6）--简单选择排序的基本思想：比较+交换。
1.从待排序序列中，找到关键字最小的元素；2.如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；3.对余下的N-1个元素，重复(1)、(2)步，直到排序结束。（7）--堆是一棵顺序存储的完全二叉树。其中每个结点的关键字都不大于其孩子结点的关键字，这样的堆称为小根堆；每个结点的关键字都不小于其孩子结点的关键字，这样的堆称为大根堆。
堆排序是利用堆这种数据结构所设计的一种排序算法。在数组的非降序排序中，需要使用大根堆，根据大根堆的特点可知，最大值一定在堆顶。
（8）
归并排序是建立在归并操作上的一种有效的排序算法，该算法是分治法的典型应用，各层分治递归可以同时进行。归并排序思路简单，速度仅次于快速排序，一般用于总体无序，但各子项相对有序的数列。
（9）
基数排序：对待排序的N个元素进行若干趟的“分配”与“收集”来实现排序。假设有欲排数据序列：。
首先根据个位数值，在遍历数据时将它们各自分配到编号0至9的桶中，结果如下：
分配结束后，接下来将所有桶中数据按桶号由小到大依次重新收集串接起来，得到如下仍然无序的数据序列：。接着，根据十位数值分配，结果如下：
分配结束后，接下来再将所有桶中的数据依次收集串接起来，得到如下数据序列：。
以上是内部排序，所有的排序算法在真题中都出现过，当然真题中也有涉及外部排序，均为多路归并排序，关于多路归并排序中如何构造最佳归并树，如何增补虚段，请听下次讲解！欢迎