一、排序
1.1 概念
所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
1.2 常见的排序算法
本文将重点讲解插入排序和选择排序。
二、插入排序
基本思想：直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。
实际应用中玩扑克牌时，就用了插入排序的思想。
2.1 直接插入排序
当插入第 i (i>=1) 个元素时，前面的 array[0], array[1], …, array[i-1] 已经排好序。此时用 array[i] 的排序码与 array[i-1], array[i-2], … 的排序码顺序进行比较，找到插入位置即将 array[i] 插入，原来位置上的元素顺序后移。
void InsertSort(int* a, int n) {
for (int i = 0; i < n - 1; i++) {
int end = i;
int tmp = a[end + 1];
while (end >= 0) {
if (a[end] > tmp) {
a[end + 1] = a[end];
end--;
} else {
break;
}
}
a[end + 1] = tmp;
}
}
直接插入排序的特性总结：
- 元素集合越接近有序，直接插入排序算法的时间效率越高。
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
2.2 希尔排序
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数（通常是 gap = n/3+1），把待排序文件所有记录分成各组，所有的距离相等的记录分在同一组内，并对每一组内的记录进行排序。然后 gap=gap/3+1 得到下一个整数，再将数组分成各组，进行插入排序，当 gap=1 时，就相当于直接插入排序。
