1.排序的概念及应用
1.1 排序的概念
排序:所谓排序,就是使一串记录按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。
稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且 r[i] 在 r[j] 之前,而在排序后的序列中,r[i] 仍在 r[j] 之前,则称这种排序算法是稳定的;否则称为不稳定的。

内部排序:数据元素全部放在内存中的排序。外部排序:数据元素太多不能同时放在内存中,根据排序过程的要求不能在内外存之间移动数据的排序。
1.3 常见的排序算法

2.常见排序算法的实现 (默认排升序)
2.1 插入排序
2.1.1 基本思想
直接插入排序是一种简单的插入排序法,其基本思想是:
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列。实际中我们玩扑克牌时,就用了插入排序的思想。
如下模拟动图:

2.1.2 直接插入排序
当插入第 i(i>=1) 个元素时,前面的 array[0],array[1],…,array[i-1] 已经排好序,此时用 array[i] 的排序码与 array[i-1],array[i-2],…的排序码顺序进行比较,找到插入位置将 array[i] 插入,原来位置上的元素顺序后移如下图:

直接插入排序具体操作:
第一步 理清思路:
当插入第 i(i>=1) 个元素时,前面的 array[0],array[1],…,array[i-1] 已经排好序,
此时用 array[i] 的排序码与 array[i-1],array[i-2],…的排序码顺序进行比较,找到插入位置将 array[i] 插入,原来位置上的元素顺序后移
第二步 具体步骤:
1. 定义 tmp 保存 排序前 i 下标对应的值。for(i) 为 外循环,for(j) 为 内循环,j = i -1.





