【数据结构的内部排序总结】1 / 1 0 数 据 结 构 的 内 部 排 序 数 据 结 构 中 的 内 部 各 种 排 序 ， 大 体 上 分 为 五 大 类 ， 在 我 们 对 每 个 算 法 进 行 分 析 前 ， 最 重 要 的 是 搞 清 楚 它 的基 本 思 想 。 ★插入类 排 序 ； ★交换类 排 序 ； ★选择类 排 序 ； ★归并排 序 ； ★分 配类 排 序 ； 一 、插入类排 序 基 本 思 想 是 ：在 一个 已经排 好序 的 序 列中 ， 每 一步都将下一个 待排 序 的 记录插入到已排 好序 的 记录中 ， 直到所有待排 序 的 记录全部 插入为 止。 插入类 排 序 又分 为 三大 类 ： ●直接插入排 序 ； ●折半插入排 序 ； ●希尔排 序 ； 下面我 们 以直接插入排 序 与希尔排 序 为 例。 (1 ) 直接插入排 序 算法思想：将第 i 个 记录（i 一般是 从 2 开始）插入到前 面 i-1 个 已经排 好序 的 记录中 。 具体过程：将第 i 个 记录的 关键字 K 顺次与其前 面记录的 关键字进 行 比较。将所有关键字大 于 K 的 记录依次向后移动一个 位置， 直到遇到小于或等于 K 的 关键字， 就把 K 插入到其后面即可。 下面我 们 以一个 例子为 例， 讲解它 的 具体 实现过程。 直接插入排序举例 以 12 2 16 30 8 28 4 10 20 6 18 序列为例 第一趟：2 12 16 30 8 28 4 10 20 6 18 第二趟：2 8 12 16 30 28 4 10 20 6 18 第三趟：2 8 12 16 28 30 4 10 20 6 18 第四趟：2 4 8 12 16 28 30 10 20 6 18 第五趟：2 4 8 10 12 16 28 30 20 6 18 第六趟：2 4 8 10 12 16 20 28 30 6 18 第七趟：2 4 6 8 10 12 16 20 28 30 18 第八趟：2 4 6 8 10 12 16 18 20 28 30 功能实现： 输入：数组名称（也就是数组首地址）、数组中元素个数 ================================================ 算法思想简单描述：在要排序的一组数中，假设前面(n-1) [n>=2] 个数已经是排好顺序的，现在要把第 n个数插到前面的有序数中，使得这n 个数也是排好顺序的。如此反复循环，直到全部排好顺序。 直接插入排序是稳定的。算法时间复杂度)( 2nO ===================================================== vo...
