排序算法（内部）
插入排序算法
插入排序算法是所有排序方法中最简单的一种算法，其主要的实现思想是将数据按照一定的顺序一个一个地插入到有序的表中，最终得到的序列就是已经排序好的数据。
注意：很多初学者所说的插入排序，实际上指的就是直接插入排序算法，插入排序算法还包括: 折半插入排序算法、2-路插入排序算法、表插入排序算法和希尔排序算法等。
插入排序算法-直接插入
直接插入排序算法是插入排序算法中的一种，采用的方法是：在添加新的记录时，使用顺序查找的方式找到其要插入的位置，然后将新记录插入。
具体实现：
见代码。
直接插入排序算法本身比较简洁，容易实现，该算法的时间复杂度为：O(n^2)
插入排序算法-希尔排序
希尔排序算法，又称“缩小增量排序”，也是插入排序算法的一种，但是同前面几种排序算法比较来看，希尔排序在时间效率上有很大的改进。
在使用直接插入排序算法时，如果表中的记录只有个别的是无序的，多数保持有序，这种情况下算法的效率也会比较高；除此之外，如果需要排序的记录总量很少，该算法的效率同样会很高。希尔排序就是从这两点出发对算法进行改进得到的排序算法。
希尔排序的具体实现思路是：先将整个记录表分割成若干部分，分别进行直接插入排序，然后再对整个记录表进行一次直接插入排序。
希尔排序的过程中，对于分割的每个子表，其各自包含的记录在原表中并不是相互挨着的，而是相互之间相隔着某个固定的常数。例如上例中第一次排序时子表中的记录分割的常量为 5，第二次排序时为
3。通过此种方式，对于关键字的值较小的记录，其前移的过程不是一步一步的，而是跳跃性的前移，并且在最后一次对整表进行插入排序时减少了比较和排序的次数。
一般在记录数量多的情况下，希尔排序算法的排序效率较直接插入排序算法高。
具体实现：
见代码。
选择排序算法
三种选择排序算法，分别为：简单选择排序、 树形选择排序和堆排序。
选择排序算法-简单选择排序
该算法的实现思想为：对于具有 n 个记录的无序表遍历 n-1 次，第 i 次从无序表中第 i 个记录开始，找出后续关键字中最小的记录，然后放置在第 i 的位置上。
具体实现：
见代码。
选择排序算法树-形选择排序
树形选择排序（又称“锦标赛排序”），是一种按照锦标赛的思想进行选择排序的方法，即所有记录采取两两分组，筛选出较小（较大）的值；然后从筛选出的较小（较大）值中再两两分组选出更小（更大）值，依次类推，直到最后选出一个最小（最大）值。同样可以采用此方式筛选出次小（次大）值等。
该算法的时间复杂度为 O(nlogn)，同简单选择排序相比，该算法减少了不同记录之间的比较次数，但是程序运行所需要的空间较多。
堆排序
在学习堆排序之前，首先需要了解堆的含义：在含有 n 个元素的序列中，如果序列中的元素满足下面其中一种关系时，此序列可以称之为堆。
ki ≤ k2i 且 ki ≤ k2i+1（在 n 个记录的范围内，第 i 个关键字的值小于第 2i 个关键字，同时也小于第 2i+1 个关键字）
ki ≥ k2i 且 ki ≥ k2i+1（在 n 个记录的范围内，第 i 个关键字的值大于第 2i 个关键字，同时也大于第 2i+1 个关键字）
对于堆的定义也可以使用完全二叉树来解释，因为在完全二叉树中第 i 个结点的左孩子恰好是第 2i 个结点，右孩子恰好是 2i+1
个结点。如果该序列可以被称为堆，则使用该序列构建的完全二叉树中，每个根结点的值都必须不小于（或者不大于）左右孩子结点的值。
注意：堆用完全二叉树表示时，其表示方法不唯一，但是可以确定的是树的根结点要么是无序表中的最小值，要么是最大值。
通过将无序表转化为堆，可以直接找到表中最大值或者最小值，然后将其提取出来，令剩余的记录再重建一个堆，取出次大值或者次小值，如此反复执行就可以得到一个有序序列，此过程为堆排序。
具体实现：
见代码。
注意：代码中为了体现构建堆和输出堆顶元素后重建堆的过程，堆在构建过程中，采用的是堆的第二种关系，即父亲结点的值比孩子结点的值大；重建堆的过程也是如此。
堆排序在最坏的情况下，其时间复杂度仍为 O(nlogn)。这是相对于快速排序的优点所在。同时堆排序相对于树形选择排序，其只需要一个用于记录交换（rc）的辅助存储空间，比树形选择排序的运行空间更小。
总结
本节介绍了三种选择排序：简单选择排序、树形选择排序和堆排序。树形选择排序的产生是考虑到为了减少简单选择排序过程中做比较操作的次数；堆排序的产生是考虑到树形选择排序在运行时申请的辅助存储空间多。要根据特定地情况，选择合适的选择排序算法。
冒泡排序算法
冒泡排序，别名“起泡排序”，该算法的核心思想是将无序表中的所有记录，通过两两比较关键字，得出升序序列或者降序序列。
注意：通过一趟趟的比较，一个个的“最大值”被找到并移动到相应位置，直到检测到表中数据已经有序，或者比较次数等同于表中含有记录的个数，排序结束，这就是冒泡排序。
具体实现：
见代码。
总结
使用冒泡排序算法，其时间复杂度同实际表中数据的无序程度有关。若表中记录本身为正序存放，则整个排序过程只需进行 n-1（n 为表中记录的个数）次比较，且不需要移动记录；若表中记录为逆序存放（最坏的情况），则需要 n-1 趟排序，进行 n(
n-1)/2 次比较和数据的移动。所以该算法的时间复杂度为 O(n^2)。
快速排序算法
C语言中自带函数库中就有快速排序——qsort 函数 ，包含在 <stdlib.h> 头文件中。
快速排序算法是在冒泡排序的基础上进行改进的一种算法，其实现的基本思想是：
通过一次排序将整个无序表分成相互独立的两部分，其中一部分中的数据都比另一部分中包含的数据的值小，然后继续沿用此方法分别对两部分进行同样的操作，直到每一个小部分不可再分，所得到的整个序列就成为了有序序列。
例如，对无序表{49，38，65，97，76，13，27，49}进行快速排序，大致过程为：
首先从表中选取一个记录的关键字作为分割点（称为“枢轴”或者支点，一般选择第一个关键字），例如选取 49；
将表格中大于 49 个放置于 49 的右侧，小于 49 的放置于 49 的左侧，假设完成后的无序表为：{27，38，13，49，65，97，76，49}；
以 49 为支点，将整个无序表分割成了两个部分，分别为{27，38，13}和{65，97，76，49}，继续采用此种方法分别对两个子表进行排序；
前部分子表以 27 为支点，排序后的子表为{13，27，38}，此部分已经有序；后部分子表以 65 为支点，排序后的子表为{49，65，97，76}；
此时前半部分子表中的数据已完成排序；后部分子表继续以 65 为支点，将其分割为{49}和{97，76}，前者不需排序，后者排序后的结果为{76，97}；
通过以上几步的排序，最后由子表{13，27，38}、{49}、{49}、{65}、{76，97}构成有序表：{13，27，38，49，49，65，76，97}；
整个过程中最重要的是实现第 2 步的分割操作，具体实现过程为：
- 设置两个指针 low 和 high，分别指向无序表的表头和表尾，如下图所示：
- 先由 high 指针从右往左依次遍历，直到找到一个比 49 小的关键字，所以 high 指针走到 27 的地方停止。找到之后将该关键字同 low 指向的关键字进行互换：
- 然后指针 low 从左往右依次遍历，直到找到一个比 49 大的关键字为止，所以 low 指针走 到 65 的地方停止。同样找到后同 high 指向的关键字进行互换：
- 指针 high 继续左移，到 13 所在的位置停止（13<49），然后同 low 指向的关键字进行 互换：
- 指针 low 继续右移，到 97 所在的位置停止（97>49），然后同 high 指向的关键字互换 位置：
- 指针 high 继续左移，此时两指针相遇，整个过程结束
具体实现：
见代码。
总结
快速排序算法的时间复杂度为 O(nlogn)，是所有时间复杂度相同的排序方法中性能最好的排序算法。
归并排序算法
本节介绍一种不同于插入排序和选择排序的排序方法——归并排序，其排序的实现思想是：先将所有的记录完全分开，然后两两合并，在合并的过程中将其排好序，最终能够得到一个完整的有序表。
例如对于含有 n 个记录的无序表，首先默认表中每个记录各为一个有序表（只不过表的长度都为 1），然后进行两两合并，使 n 个有序表变为 ⌈ n/2⌉ 个长度为 2 或者 1 的有序表（例如 4 个小有序表合并为 2
个大的有序表），通过不断地进行两两合并，直到得到一个长度为 n 的有序表为止。这种归并排序方法称为：2-路归并排序。
具体实现：
见代码。
总结
归并排序算法的时间复杂度为 O(nlogn)。该算法相比于堆排序和快速排序，其主要的优点是：当记录表中含有值相同的记录时，排序前和排序后在表中的相对位置不会改变。
微信
支付宝
