排序算法中的稳定和不稳定指的是什么？
若在待排序的纪录中，存在两个或两个以上的关键码值相等的纪录，经排序后这些记录的相对次序仍然保持不变，则称相应的排序方法是稳定的方法，否则是不稳定的方法。
内部排序和外部排序
根据排序过程中涉及的存储器不同，可以讲排序方法分为两大类：一类是内部排序，指的是待排序的几率存放在计算机随机存储器中进行的排序过程；另一类的外部排序，指的是排序中要对外存储器进行访问的排序过程。
内部排序是排序的基础，在内部排序中，根据排序过程中所依据的原则可以将它们分为5类：插入排序、交换排序、选择排序、归并排序和基数排序；
根据排序过程的时间复杂度来分，可以分为三类：简单排序、先进排序、基数排序。
评价排序算法优劣的标准主要是两条：一是算法的运算量，这主要是通过记录的比较次数和移动次数来反应；另一个是执行算法所需要的附加存储单元的的多少。
插入排序：有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。
插入排序的基本思想是：每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
void InsertSort(int *arr, size_t size)
{
assert(arr);
for (int i = 0; i < size - 1; ++i)
{
int tmp = arr[i+1];
int end = i;
while (end >= 0&&arr[end]>tmp)
{
arr[end + 1] = arr[end];
--end;
}
arr[end + 1] = tmp;//即使都大于tmp,将tmp放置arr[0]处
}
}
希尔排序：希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量 =1( < …<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。
void ShellSort(int *arr, size_t size)
{
assert(arr);
int gap = size;
while (gap>1)//注意跳出条件
{
gap = gap / 3 + 1;
for (int i = 0; i < size - gap; ++i)//i可取到size-1-gap
{
int tmp = arr[i + gap];
int end = i;
while (end >= 0 && arr[end]>tmp)
{
arr[end + gap] = arr[end];
end-=gap;
}
arr[end + gap] = tmp;//即使都大于tmp,将tmp放置arr[0]处
}
}
}