直接插入排序
外循环：遍历所有元素，将当前R[i]记为K
内循环：从当前i-1开始，j往前遍历，从右往左找第一个<=当前K的元素R[j]，将该元素的右边的第一个元素修改为K
逐个插入，插入时即确定位置
/*直接插入排序*/
void InsertionSort(int R[], int n) { //对R[1]...R[n]排序for (int i = 2; i <= n; i++) {int K = R[i], j = i - 1;while (j >= 1 && R[j] > K) { //通过指针j扫描R[i-1]...R[1]，从右往左找第1个<=R[i]的元素R[j + 1] = R[j];j--;}R[j + 1] = K;}
}时间复杂度及稳定性分析
| 时间复杂度 | 最好 | 平均 | 最坏 | 稳定性 |
| 直接插入排序算法 | O(n) | O(n^2) | O(n^2) | 稳定 |
简单冒泡排序
从左往右扫描数组，如果遇到反序对（两个相邻的元素，且前面的元素比后面大），则交换这两个元素。
扫描一趟之后，则最大元素被交换到最右边。
如果把数组立起来，最大元素就像气泡一样，浮到上面。此过程称为一趟冒泡。
外层循环：从n到2，从右向左，依次全部遍历
内层循环：从1到当前bound，从左到右，找逆序对进行交换
/*冒泡排序*/
void SimpleBubbleSort(int R[], int n) {for (int bound = n; bound >= 2; bound--) {for (int i = 1; i < bound; i++) {if (R[i] > R[i + 1])swap(R[i] , R[i + 1]);}}
}
优化冒泡排序
在每趟冒泡过程中，当比较结束后，如果发现位置t是最后依次元素交换的位置，即说明从Rt+1~Rn已经排序。
从而下一趟比较只要进行到位置t即可。
这样可以减少算法的关键词比较次数。
void BubbleSort(int R[], int n) {int bound = n; //每趟冒泡排序关键词比较终止位置while (bound > 0) {int t = 0; //本趟冒泡元素交换的最后位置for (int i = 1; i < bound; i++) {if (R[i] > R[i + 1]) {swap(R[i], R[i + 1]);t = i;}}bound = t;}
}时间复杂度及稳定性分析
| 时间复杂度 | 最好 | 平均 | 最坏 | 稳定性 |
| 冒泡排序 | O(n) | O(n^2) | O(n^2) | 稳定 |
直接选择排序
（1）在前n个元素里找最大元素，与R[n]交换，使R[n]就位
（2）在前n-1个元素里找最大元素，与R[n-1]交换，使R[n-1]就位
（3）在前n-2个元素里找最大元素，与R[n-2]交换，使R[n-2]就位
······
以此类推，最后形成递增的有序序列
注意的是，因为交换使得原始顺序被打乱，因此直接选择排序不稳定。
/*直接选择排序*/
void SelectionSort(int R[], int n) {for (int i = n; i >= 1; i--) {//i标识当前处理的子数组的右边界//在子数组R[i]...R[i]里找最大元素，和R[i]交换int max = 1;for (int j = 2; j <= i; i++) {if (R[j] > R[max]) max = j;}swap(R[max], R[i]);}
}时间复杂度及稳定性分析
| 时间复杂度 | 最好 | 平均 | 最坏 | 稳定性 |
| 直接选择排序 | O(n^2) | O(n^2) | O(n^2) | 不稳定 |
希尔排序
亦称渐进增量排序，是对直接排序算法的改进（可看作直接插入算法的升级版）。
把记录按下标进行分组。
直接插入排序算法在“短文件”、“待排序文件基本有序”时速度快，希尔排序充分利用了这两个特点。
基本过程：
（1）将元素分为d组；
（2）对每组使用直接插入排序法排序；
（3）把d值减小，重复执行(1）（2），直至d减小到1。
随着增量d逐渐减小，组数越来越少，魅族包含的元素越来越多，当d值减少到1时，整个文件敲好被分成1组，算法终止。
原理：
开始时增量值比较大，每组中的元素较少，插入排序速度较快；
算法执行过程中，随着增量值逐渐变小，每组中元素个数逐渐变多，由于前面工作的基础，大多数元素已基本有序，而插入排序在元素接近有序时速度快。
实现：
分组及对每组插入排序：
无需新开数组，可在原来的大数组上操作；
组内相邻元素的下标间隔d。
/*希尔排序*/
void ShellSort(int R[], int n) { //对R[1]...R[n]递增排序for (int d = n / 2; d > 0; d /= 2) { //d为增量值for (int i = d + 1; i <= n; i++) { //...R[i-3d],R[i-2d],R[i-d]int K = R[i], j = i - d; //指针j从右往左扫描本组元素while (j > 0 && R[j] > K) { //在本组中从右往左找第1个<=K的元素R[j + d] = R[j];j -= d;}R[j + d] = K;}}
}时间复杂度及稳定性分析
算法的时间复杂度与所选的增量序列有很大关系；
一般认为平均时间复杂度介于O(N^2)和O(nlogn)之间；
稳定性：不稳定