排序
- 按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作；
稳定性
- 若存在多个具有相同关键字的对象，经过排序，其相对位置次序保持不变，则称此算法稳定；
内部排序
- 数据元素全部放在内存中的排序；
外部排序
- 数据元素太多不能同时放在内存中，根据排序过程的要求不能在内存之间移动数据的排序；
一，常见排序算法
插入排序：直接插入排序、希尔排序shell；
选择排序：选择排序、堆排序；
交换排序：冒泡排序、快速排序；
归并排序
计数排序
基数排序
二，常见排序算法的实现
直接插入排序
逻辑思路：
- 把待排序的对象，按其值的大小逐个插入到一个有序序列中（已经排好序），直到所有对象插入完为止，得到一个新的有序序列；
- 即当插入第i个元素时，其前面元素已为有序序列，在依次与前面元素比较，直到找到插入位置插入为止，原位置元素按顺序后移；
特性：
- 元素越接近有序，此算法时间效率越高；
- 时间复杂度，
；
- 空间复杂度，
；
- 稳定性，稳定；
//直接插入法
void InsertSort(int* arr, int n)
{
int i = 0;
for (i; i < n - 1; i++)
{
//单次插入
int end = i;
int tmp = arr[end + 1];
while (end >= 0)
{
if (tmp < arr[end])
{
arr[end + 1] = arr[end];
--end;
}
else
break;
}
arr[end + 1] = tmp;
}
}?
?