文章介绍了插入排序、希尔排序、选择排序、堆排序、冒泡排序、归并排序的实现思路与使用c编写的代码，同时对排序算法的三个评价要素：时间复杂度、空间复杂度、稳定性，分别进行了具体分析。
1、插入排序
实现思想：确定一个有序的数组，将后续的元素逐一插入此有序数组，确定其相对位置，直到所有元素插入完成； 代码如下：
void InsertSort(int* a, int n)
{
for (int i = 1; i < n; i++)
{
int tmp = a[i];
int end = i-1;
// 将有序元素与待插入元素比较，确定其最终插入位置
while (end >= 0)
{
// 若之前的元素大于待插入元素，则将其后移
if (a[end] > tmp)
a[end + 1] = a[end--];
// 否则跳出循环
else
{
break;
}
}
a[end + 1] = tmp;
}
}
容易发现，当数组越接近有序，元素之间的比较与交换越少，时间效率越高；越接近倒序，发生的交换与比较越多，时间效率越低； 时间复杂度：$O(n^{2})$；第i个元素需要与前$i-1$个元素比较； 空间复杂度：$O(1)$； 稳定性：稳定；
2、希尔排序
实现思想：希尔排序是对插入排序的优化。将原数组的元素按照某个间隔$gap$划分为一组，同组的元素进行插入排序，$gap>1$时，实际上是对数组中的元素进行预排序，从而减少元素之间的比较和交换。 以升序为例，假设有10个元素，最大的元素恰巧在序列头部，此时采用插入排序，确定其最后位置时，需要与剩下的每个元素都进行比较，也就是9次；而采用希尔排序，若$gap=2$，此时需要比较预排序（$gap=2$)时的4次，加上最后进行排序时（$gap=1$）时的1次，共5次； 代码如下：
void ShellSort(int* a, int n)
{
int gap = n / 2;
while (gap > 0)
{
// i++时就进行了不同分组的切换
for (int i = gap; i < n; i++)
{
// 在其内部仍然是插入排序的逻辑
int tmp = a[i];
int end = i - gap;
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + gap] = a[end];
end -= gap;
}
else
break;
}
a[end + gap] = tmp;
}
// gap慢慢减小到1
gap /= 2;
}
}
时间复杂度：$O(nlogn)$； 空间复杂度：$O(1)$； 稳定性：不稳定；当两个相同的元素存在在不同组时，在预排序阶段它们的先后顺序可能会产生变化；
3、选择排序
实现思想：以升序为例，每次找剩余序列中最小的元素，将其插入最终位置; 代码如下：
void Swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
void SelectSort(int* a, int n)
{
for (int i = 0; i < n; i++)
{
int min = i;
// 找到后续元素中最小的元素位置
for (int j = i + 1; j < n; j++)
{
if (a[j] <= a[min])
{
min = j;
}
}
// 交换
Swap(&a[i], &a[min]);
时间复杂度：$O(n^2)$； 空间复杂度：$O(1)$； 稳定性：不稳定；进行元素交换时，会变换元素顺序，从而导致不稳定，例如{5，5，1}；当5和1进行交换时，两个5的先后顺序已发生变化；
4、堆排序
实现思想：根据堆的性质，升序建大堆，每次选出最大的数，随后调整堆，让次大的数浮到堆顶，依次类推；降序建小堆，原理相同； 代码如下：
// 向下调整成大根堆，前提：左右子树都是堆
void AdjustDwon(int* a, int n, int root)
{
int child = root * 2 + 1;
while (child < n)
{
if (child + 1 < n && a[child + 1] > a[child])
{
child++;
}
if (a[child] > a[root])
{
Swap(&a[child], &a[root]);
root = child;
child = root * 2 + 1;
}
else
{
break;
}
}
}
void HeapSort(int* a, int n)
{
// 从最后一个分支节点开始建堆
for (int i = (n - 2) / 2; i >= 0; i--)
{
AdjustDwon(a, n, i);
}
int end = n - 1;
// 开始排序，每次出一个元素，随后调整剩下的元素
while (end > 0)
{
Swap(&a[0], &a[end]);
AdjustDwon(a, end, 0);
end--;
}
}
时间复杂度：$O(nlogn)$；每次调整的复杂度为$logn$，共需调整n次；建堆的时间消耗小于排序时的消耗，根据时间复杂度的计算规则，略去；
空间复杂度：$O(1)$；原地调整堆排序即可，无需更多空间；
稳定性：不稳定；在调整堆再到排序的过程中，原在前的数可能会排序到后方，例如21 20a 20b 12 11 8 7,堆排序后为7 8 11 12 20a 20b 21（其中a，b仅为区分顺序）。
5、冒泡排序
实现思想：每趟排序都会将最大（小）的数据放到队尾，临近的两个数相比，将大（小）的数继续往后比，比较完成也就选出了最大（小）的元素；如此继续，经过n-1趟排序，序列便会有序； 增加优化：当一趟排序已经不发生交换时，此时序列已经有序，不用在进行多余比较，可防止元素有序后仍进行比较的时间消耗； 代码：
void BubbleSort(int* a, int n)
{
for (int i = n - 1; i >= 0; i--)
{
int exchange = 0;
for (int j = 0; j < i; j++)
{
if (a[j] > a[j + 1])
{
Swap(&a[j], &a[j + 1]);
exchange = 1;
}
}
// 一趟排序中，未发生交换，表明元素已有序，无须继续
if (exchange == 0)
{
break;
}
}
}
时间复杂度：$O(n^2)$；共需要排序$n-1$趟，每次需要比较$n-i$次，其中i为排序的趟数； 空间复杂度：$O(1)$；原地排序，无需更多空间； 稳定性：稳定；当元素大小相同时，可不发生交换；
6、归并排序
实现思想：将本来无序的序列划组排序，随着组内元素的增多，最终有序；如下图：
代码：
void MergeSort(int* a, int begin, int end)
{
int n = end - begin + 1;
int* tmp = (int*)malloc(sizeof(int) * n);
int gap = 1;
while (gap < n)
{
// 两两归并
for (int i = 0; i < n; i += 2 * gap)
{
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
// 第二组不存在
if (begin2 >= n)
break;
// 第二组结尾越界，进行修正
if (end2 >= n)
end2 = n - 1;
// 测试在归并的区间
// printf("[%d,%d][%d,%d]", begin1, end1, begin2, end2);
// 将归并结果放到tmp数组中
int cur = 0;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] <= a[begin2])
tmp[i + cur++] = a[begin1++];
else
tmp[i + cur++] = a[begin2++];
}
while (begin1 <= end1)
{
tmp[i + cur++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[i + cur++] = a[begin2++];
}
// 将归并好的数据拷贝回原数组
memcpy(a + i, tmp + i, (end2 - i + 1) * sizeof(int));
}
// printf("\n");
gap *= 2;
}
}
时间复杂度：$O(nlogn)$；共需$logn$层，每层都需访问n个元素； 空间复杂度：$O(n)$；需建立一个与原序列相同大小的空间，用于归并数据； 稳定性：稳定；比较排序都发生在相邻的空间，因此不会影响序列的稳定性。
标签：end,int,复杂度,元素,gap,算法,排序 From： https://blog.51cto.com/u_15423682/9089004