【数据结构初阶】排序算法(上)插入排序与选择排序
文章目录
- 1.排序概念及运用
- 1. 1 概念
- 1. 2 运用
- 1.3 常见排序算法
- 2. 插入排序
- 2. 1 直接插入排序
- 2. 2 希尔排序
- 2. 2. 1 希尔排序的时间复杂度
- 3. 选择排序
- 3. 1 直接选择排序
- 3. 2 堆排序
- 3. 3 Top-K问题
1.排序概念及运用
1. 1 概念
排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
1. 2 运用
各大购物平台可以按综合，销量，评论数，新品等许多要素进行排序。
大学可以按照软科，校友会等多种要素进行排序。
1.3 常见排序算法
2. 插入排序
基本思想
直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。
实际中我们玩扑克牌时，就用了插入排序的思想：
2. 1 直接插入排序
当插入第 i(i>=1)个元素时，前面的 array[0],array[1],…,array[i-1]已经排好序，此时用 array[i]的排序码与 array[i-1],array[i-2],… 的排序码顺序进行比较，找到插入位置即将 array[i]插入，原来位置上的元素顺序后移。
我们以这个数组为例介绍一下详细步骤：
int a[] = {5, 3, 9, 6, 2, 4, 7, 1, 8};
比如说我们要把这个数组排成升序的。
首先我们找到第二个（此时i=1）元素3，逐一向后比较，直到找到比它小的数，放到这个数的前面，而这里就是放到数组的第一个元素的位置，也就是第一步是5和3交换位置。
此时：
int a[] = {3, 5, 9, 6, 2, 4, 7, 1, 8};
然后i++，对9进行操作，向前找比9小的，发现5就比9小，由于5前面的数字都已经有序了，所以9不在进行比较。
这一步对数组没有更改。
接着6，向前找比6小的，可以找到5，那么最终就是6与9交换了位置，
int a[] = {3, 5, 9, 6, 2, 4, 7, 1, 8};
接着2，向前找直接找到头，放到3的前面。这里要说一下，在每次比较之后，如果还需要进行下一步的比较，应该将比较过的两个数据交换，一步步往前走，而不是找到要到的位置之后进行一次交换，这样会打乱已经排序好的数据。
int a[] = {2, 3, 5, 9, 6, 4, 7, 1, 8};
到了这里，前4个数据就已经有序了，剩下的数据就不在赘述了，都是这个逻辑。
参考代码：
void InsertSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
//外层循环控制排序次数，是n-1次,因为第一个数不需要排序
int cur = i;
//这里并没有采取每次交换的方法，因为那样的效率太低了
//这里采取的是先把要比较的那个数存储起来，然后如果需要发生交换时就让前面的数直接向后覆盖
//最后找到指定位置时，把存储起来的数值放入数组
//把要比较的数据存储起来
int tmp = a[cur + 1];
while (cur >= 0)
{
if (a[cur] > tmp)
{
//向后进行一次覆盖
a[cur + 1] = a[cur];
}
else //比较符合预期的话，就说明找到合适的位置
break;
//注意这时的cur指向的是比要排序的数据小的数据
cur--;
}
//把存储起来的数据放进去
a[cur + 1] = tmp;
}
}
直接插入排序的特性总结
- 元素集合越接近有序，直接插入排序算法的时间效率越高
- 时间复杂度:O(N2)
- 空间复杂度:O(1)
时间复杂度其实很好计算，它和我们之前改进过的冒泡排序的时间复杂度是一样的，最差情况下要遍历
(n-1)(n-2)+(n-2)(n-2)+...，那么估计就是n2次。
2. 2 希尔排序
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数(通常是gap=n/3+1)，把待排序文件所有记录分成各组，所有的距离相等的记录分在同一组内，并对每一组内的记录进行排序，然后gap=gap/3+1得到下一个整数，再将数组分成各组，进行插入排序，当gap=1时，就相当于直接插入排序。它是在直接插入排序算法的基础上进行改进而来的，综合来说它的效率肯定是要高于直接插入排序算法的。
这么说可能会不太容易理解，我们根据一个实例来分析一下步骤：
（图中被相同颜色的线连起来数据的是一组）
第一趟排序时，gap=5，我们可以找到2组，对这5组内的2个数据分别进行排序，使他们符合最终排序得相对有序。
第二趟排序时，gap=2，可以找到8组，对这2组内的5个数据分别进行排序，使他们符合最终排序得相对有序。
第三趟排序时，gap=1，可以找到9组，对这1组内的10个数据进行排序，使他们符合最终排序得相对有序。
最后一次排序就相当于直接插入排序，但是由于元素集合越接近有序，直接插入排序算法的时间效率越高，所以效率是远高于直接插入排序的。
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
//对gap进行迭代
gap = gap / 3 + 1;
//这个i是每轮排序中，排序的组数，是每组的第一个数据的下标
for (int i = 0; i < n - gap; i++) //i最大就是n-gap-1，再往后也找不到了
{
//分组，在每个组里使用直接插入排序
int cur = i; //cur是用来控制每个组内成员数据与它之前的组内成员数据进行比较的
int tmp = a[cur + gap]; //实际要比较的数据是[cur+gap]这个数据
//对组内成员进行操作
while (cur >= 0)
{
if (a[cur] < tmp)
//cur的上一个是cur+gap，不是cur+1
a[cur + gap] = a[cur];
else
break;
//cur迭代时要-gap来找到下一个
cur -= gap;
}
a[cur + gap] = tmp;
}
}
}
2. 2. 1 希尔排序的时间复杂度
希尔排序的时间复杂度估算:
外层循环的时间复杂度可以直接给出，为：O(log2n)或者O(log3n)，即O(log n)
内层循环的时间复杂度与gap的取值有关：
因此，希尔排序在最初和最后的排序的次数都为n，即前一阶段排序次数是逐渐上升的状态，当到达某一顶点时，排序次数逐渐下降至n，而该顶点的计算暂时无法给出具体的计算过程。
希尔排序时间复杂度不好计算，因为 gap 的取值很多，导致很难去计算，因此很多书中给出的希尔排序的时间复杂度都不固定。
《数据结构(C语言版)》— 严蔚敏书中给出的时间复杂度为：
3. 选择排序
选择排序的基本思想：
每一次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
3. 1 直接选择排序
- 在元素集合
array[0]--array[n-1]中选择关键码最大(小)的数据元素 - 若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个(第一个)元素交换
- 左右各缩小一个元素的范围，重复上述步骤，直到集合剩余1个元素
直接选择排序十分便于理解，就不进行步骤分析了。
void SelectSort(int* a, int n)
{
int end = n - 1;
int begin = 0;
while (begin < end)
{
//mini和maxi存储找到的最大值和最小值的下标
int mini = begin;
int maxi = begin;
for (int j = begin; j <= end; j++)
{
//遍历数组时寻找最大值和最小值的下标
if (a[mini] > a[j])
mini = j;
if (a[maxi] < a[j])
maxi = j;
}
//处理特殊情况，下文解释
if (begin == maxi)
maxi = mini;
//交换，Swap函数是用于交换两个数的自定义函数，不过多赘述
//注意在传参的同时，对begin和end进行了迭代
Swap(&a[mini], &a[begin++]);
Swap(&a[end--], &a[maxi]);
}
}
解释一下这个特殊情况：如果begin==maxi，并且没有进行if语句中的操作会发生什么？
以这个数组为例：
int a[] = { 9,3,2,1,4 };
此时maxi为0，mini为3，执行两个Swap语句，首先9和1互换，然后4和第一个数字1交换，很显然就出了问题，因为最大值被换走了，而maxi依然指向原来的位置。而maxi=mini之后的步骤就是：1和9交换，然后4和9交换，交换完成后就是：
int a[] = { 1,3,2,4,9 };
这样就能顺利完成任务了。
直接选择排序的特性总结：
- 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
- 时间复杂度:O(N2)
- 空间复杂度:O(1)
3. 2 堆排序
堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。
它是选择排序的一种，通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
注意：显然堆排序需要用到堆这个数据结构，其实现也不再赘述。
步骤为：先将整个数组建堆，然后将堆顶和最后一个元素交换，此时可以保证最后一个元素就是最大（或最小）的，然后把end--，再进行调整，再重复上述过程，就能得到顺序的数组。
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)
{
//交换并调整
Swap(&a[end], &a[0]);
AdjustDwon(a, end, 0);
end--;
}
}
void AdjustDwon(int* a, int n, int root);
注：由于AdjustDown函数并没有要求传入的是堆，只是接受一个数组，所以可以这么写，当然创建一个堆来进行排序也是可以的。
void HeapSort(int* a, int n)
{
HP hp;
for (int i = 0; i < n; i++)
{
HPPush(&hp, a[i]);
}
int i = 0;
while (!HPEmpty(&hp))
{
a[i++] = HPTop(&hp);
HPPop(&hp);
}
HPDestroy(&hp);
}
最终排序的是升序还是降序与建的是大堆（升序）还是小堆（降序）有关。
另外，为什么采取向下调整算法建堆？因为向上调整算法建堆的时间复杂度是O(n*log2n)，而向下调整算法建堆的时间复杂度是O(n)。其计算较为复杂，可以看一眼，没必要记：
3. 3 Top-K问题
（这个问题不属于数据结构排序的内容，但与堆排序有关，所以放到这里）
TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top-K问题，能想到的最简单直接的方式就是排序，但是:如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下:
- 用数据集合中前K个元素来建堆
前k个最大的元素，则建小堆
前k个最小的元素，则建大堆 - 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素
比如说我们要最大的K个数，基本思路就是建大小为K一个小堆，将前K个数据依次入堆并调整，然后开始向后遍历，如果遍历到的数据比堆顶大，就将堆顶换成这个数据，然后调整，循环进行这个过程，最后这个堆中的数据就是最大的K个数据了。
//这个函数调用一次就行了
//这个函数可以生成一个有10000个随机数的data.txt文件
void CreateNDate()
{
// 造数据
int n = 10000;
srand(time(0));
const char* file = "data.txt";
FILE* fin = fopen(file, "w");
if (fin == NULL)
{
perror("fopen error");
return;
}
for (int i = 0; i < n; ++i)
{
int x = rand() % 1000000; //给数据添加最大值
fprintf(fin, "%d\n", x);
}
fclose(fin);
}
void PrintTopK(int k)
{
FILE* fl = fopen("data.txt", "r");
if (!fl)
{
perror("fopen");
exit(1);
}
int* arr = (int*)malloc(k * sizeof(int));
if (!arr)
{
perror("malloc");
exit(2);
}
for (int i = 0; i < k; i++)
fscanf(fl, "%d", &arr[i]);
//建堆
for (int i = (k - 2) / 2; i >= 0; i--)
{
AdjustDown(arr, i, k);
}
int tmp = 0;
//遍历
while (fscanf(fl, "%d", &tmp) != EOF)
{
if (tmp > arr[0])
{
arr[0] = tmp;
AdjustDown(arr, 0, k);
}
}
for (int i = 0; i < k; i++)
{
printf("%d ", arr[i]);
}
}
这个函数中用到了文件操作和fscanf函数。
这里介绍一下fscanf函数：
int fscanf ( FILE * stream, const char * format, ... );
第一个为流，这里就是这个文件，剩下的和scanf函数是一样的格式化输入放到第三个参数中，只是是从文件的流中获取数据，而不是从标准输入流。
怎么测试这个算法的结果是否正确？
我们打开第一个函数生成的文件（这个文件怎么找可以在这篇博客中找到，不再赘述）：
随便找几个数据，为它们添上几位数：
生成随机数时，我们给它添加了范围，所以最后的输出应该就是这几个改过的数字，这样就可以方便调试代码了。
时间复杂度：O(n)=k+(n-k)log2k
谢谢你的阅读，喜欢的话来个点赞收藏评论关注吧！
我会持续更新更多优质文章