排序（一）——冒泡排序、直接插入排序、希尔排序（BubbleSOrt,InsertSort,ShellSort)
欢迎来到繁星的CSDN，本期的内容主要包括冒泡排序(BubbleSort），直接插入排序(InsertSort)，以及插入排序进阶版希尔排序（ShellSort）。
废话不多说，直接上正题！
一、冒泡排序
冒泡排序是我们的老朋友了，我们最初模拟实现qsort的时候就是用它来模拟的（尽管qsort的底层原理实际是quicksort，即快排）。
上代码！
void BubbleSort(int* a, int n)
{
for (int j = 0; j < n; j++)
{
// 单趟
int flag = 0;
for (int i = 1; i < n - j; i++)
{
if (a[i - 1] > a[i])
{
Swap(&a[i - 1], &a[i]);
flag = 1;
}
}
if (flag == 0)
{
break;
}
}
}代码相当简单，其思想就是通过两两之间的比较，每一趟都将最大的数据放在数组的最后。
缺点是，冒泡排序的速度相当慢，原因不仅仅在于比较的次数恒定（n*(n+1)/2次)，更在于如果数据量庞大，各个数据移动的速度也相当慢。
实际意义聊胜于无，但却很好地帮我们入门各大排序算法，这是它仍然活跃的意义。
二、直接插入排序
我们一般会叫它插入排序，在此加入“直接”二字，是为了区分它和希尔排序。
插入排序的思路也是较为简单的。
面对一个有n个元素的数组，如果前n-1个元素都有序，那么第n个元素通过和前面所有元素比较，就能得到该元素在数组中的位置。有一点数学归纳法的思想在里面。
上代码！
void InsertSort(int* a, int n)
{
// [0, n-1]
for (int i = 0; i < n - 1; i++)
{
// [0, n-2]是最后一组
// [0,end]有序 end+1位置的值插入[0,end]，保持有序
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 1] = a[end];
--end;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}由于一个元素一定有序，所以第一个元素不用排序。而从第二个元素开始，通过比较，不断插入到前面的数组中，使前n项都有序，如此往复，便可使得整个数组有序。
相比于冒泡排序，插入排序少了大量重复的交换数值的工作，而是一步到位，得到数据的最终位置（尽管时常需要将所有数据后移，但代码中只是赋值，而非交换，效率比冒泡高的多）。
两者运行时间差别：
（此处数据为10000个）
尽管如此，我们在实际工作中也很少使用直接插入排序，即使时间比冒泡排序少的多，其时间复杂度仍为O(n^2)。但不得不指出，它仍有应用，后续在快排的时候将会提到。
三、希尔排序
希尔排序是插入排序的优化版本，优化到可以和快速排序一较高下。
希尔排序主要做两件事：1、预排序。2、插入排序。
由插入排序的代码可知，当数组越趋近于有序，比较和赋值的次数也越来越少。所以预排序的目的就是使得整个数组接近有序。
上代码！
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
// +1保证最后一个gap一定是1
// gap > 1时是预排序
// gap == 1时是插入排序
gap = gap / 3 + 1;
for (size_t i = 0; i < n - gap; ++i)
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}要点解释：
1、gap代表的含义是，下标相减为gap的元素为一组，进行插入排序。此举的意义是使得O（n^2)的复杂度造成的影响尽可能小，因为a*(n/a)^2小于n^2，a为任意整数。
2、而当gap等于1时再进行排序，就是插入排序了。
3、gap的大小实际上由写代码的人自己决定，没有一定gap越大，或者gap越小的效果最好，但可以确定的是，经过预排序的插排会比直接插排要更快。
4、上述代码中的gap是一个效果较好的gap，可以参照并直接使用。
本篇内容到此结束，谢谢大家的观看！
觉得写的还不错的可以点点关注，收藏和赞，一键三连。
我们下期再见~
往期栏目：
原文地址：https://blog.csdn.net/xqhoj/article/details/140347441
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！