🚀write in front🚀
📜所属专栏：初阶数据结构
🛰️博客主页：睿睿的博客主页
🛰️代码仓库：🎉VS2022_C语言仓库
🎡您的点赞、关注、收藏、评论，是对我最大的激励和支持！！！
关注我，关注我，关注我，你们将会看到更多的优质内容！！
文章目录
- 前言
- 1. 排序的概念及其运用
- 1.1 排序的概念
- 1.2 排序运用
- 1.3 常见的排序算法
- 1.4排序的基本思想与分析方法：
- 2. 常见排序算法的实现
- 2.1 插入排序
- 2.1.1 基本思想
- 2.1.2 直接插入排序
- 代码实现：
- 性能分析：
- 2.1.3 希尔排序( 缩小增量排序 )
- 希尔排序的特性总结
- 代码实现：
- 性能分析：
- 2.2 选择排序
- 2.2.1 基本思想
- 2.2.2直接选择排序
- 代码实现：
- 性能分析：
- 2.2.3 堆排序
- 代码实现：
- 性能分析：
- 2.3 交换排序
- 2.3.1基本思想
- 2.3.2冒泡排序
- 代码实现：
- 性能分析：
- 2.3.3 快速排序
- 1. hoare版本
- 代码实现：
- 2. 挖坑法
- 代码实现：
- 3. 前后指针版本
- 4.非递归法
- 2.3.4 快速排序优化
- a.key的选择：
- 随机找key：
- 三数取中
- b.小区间优化：
- 性能分析：
- 2.4 归并排序
- 2.4.1 基本思想
- 2.4.2 递归实现
- 2.4.3 非递归实现
- 代码实现：
- 性能分析：
- 3.计数排序
- 性能分析：
- 4.排序算法复杂度及稳定性分析
- 5.源代码
- Sort.h
- Stack.h
- Stack.c
- Sort.c
- test.c
- 总结
前言
从今天开始，我们就进入了初阶数据结构的最后一章——排序！在文章开始之前，我们先来介绍一下分析排序性能的方式：
- 时间复杂度
- 空间复杂度
- 稳定性
前两个相信大家都比较清楚，我们来介绍一下稳定性的定义：
举个🌰：
1. 排序的概念及其运用
1.1 排序的概念
排序 ：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
1.2 排序运用
很多地方都会用到排序，比如学校排名的排序，价格的排序……
1.3 常见的排序算法
在这里我们可以知道，希尔排序是插入排序的优化,堆排序是选择排序的优化，快数排序是交换排序的优化。
1.4排序的基本思想与分析方法：
写每个排序要先写一趟的排序，在写完整的排序！
2. 常见排序算法的实现
2.1 插入排序
2.1.1 基本思想
直接插入排序是一种简单的插入排序法，其基本思想是：
把待排序的记录按其码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止，得到一个新的有序序列。实际中我们玩扑克牌时，就用了插入排序的思想
2.1.2 直接插入排序
我们先来看看动图：
由动图我们可以分析出直接插入排序是从第二个数据开始遍历，与前面的数据进行比较。
如果小于自己，则让前面的数据向前移动 ，自己接着和前面的数据比较
如果大于等于自己的数据或者没有数据能进行比较时停止 ，插入当前的位置。
代码实现：
一趟的排序：
//end指比较的元素下标，tmp指插入到元素
int end;
int tmp;
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + 1] = a[end--];
}
else
{
break;
}
}
a[end + 1] = tmp;
最后的a[end+1]就是为了防止上图越界的情况。并且本身插入就是要插在end的后面一个元素，这是一个易错点。
完整代码：
void InsertSort(int* a, int n)
{
for (int i = 1; i < n; i++)
{
int end = i - 1;
int tmp = a[i];
//将tmp插入到[0,end]区间中，保持有序
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}
性能分析：
时间复杂度：
在最坏(插入时逆序）的情况下是O(n^2)
在最好(顺序的时候）的情况下是O(n)
空间复杂度 ：O(1)
稳定性： 稳定
2.1.3 希尔排序( 缩小增量排序 )
希尔排序的特性总结
我们先来看这个动图：
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成n个组，所有距离为n的记录分在同一组内，并对每一组内的记录进行排序。然后随着n的减小取，重复上述分组和排序的工作。当到达n=1时，所有记录在统一组内排好序。
代码实现：
单趟排序：
int gap = 2;
for (int i = gap; i < n; i ++)
{
int tmp = a[i];
int end = i - gap;
while (end >= 0)
{
if (tmp < a[end])
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
a[end + gap] = tmp;
}
}
那么，gap是多少比较合适呢？
gap越大，跳得越快，越不接近有序
gap越小，跳得越慢，越接近有序。
所以gap我们通常用除2或除3加一来处理
完整代码：
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
gap =gap/3+1;
for (int i = 0; i < n - gap; i++)
{
int end = i;
int tmp = a[i + gap];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
a[gap + end] = tmp;
}
}
}
}
性能分析：
时间复杂度：
gap等于n，就相当于每组有n+1个数字。所以对于每一组数据，在n等于3时，最坏情况的插入排序为3+2+1=6，为常数，所以每组的最坏情况都为6次。
当 gap > 1 时都是预排序，目的是让数组更快的接近于有序（因为每次跨越大）。当 gap == 1 时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
但是，希尔排序的时间复杂度不好计算，因为 gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定：
不过经过大量的统计，大家只要记住希尔排序的时间复杂度大概是O(n^1.3)即可
空间复杂度：O(1)
稳定性： 不稳定（gap大的时候相同元素位置会出现乱序）
2.2 选择排序
2.2.1 基本思想
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。
2.2.2直接选择排序
作为所有排序里最简单的排序，我们就快速实现一下：
代码实现：
void my_SelectSort(int* a, int n)
{
int min=0;
for (int j = 0; j <n ; j++)
{
min = j;
for (int i = j; i < n; i++)
{
if (a[min] > a[i])
{
min = i;
}
}
Swap(&a[j], &a[min]);
}
}
性能分析：
时间复杂度： 不管好坏都是O(n^2).
空间复杂度： O(1)
稳定性： 不稳定（因为要交换位置，在很多情况交换会出问题）
2.2.3 堆排序
（点我看前面堆排序详解博客）
堆排序 (Heapsort) 是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
代码实现：
void HeapSort(int* a, int n)
{
//向上调整建堆
/*for (int i = 0; i < n; i++)
{
AdjustUp(a, i);
}*/
//向下调整建堆
for (int i = (n - 2) / 2; i >= 0; i--)
{
AdjustDown(a, n, i);
}
//堆删除
int end = n - 1;
for (int i = end; i > 0; i--)
{
Swap(&a[i], &a[0]);
AdjustDown(a, i, 0);
}
}
性能分析：
时间复杂度：
无论好坏都是O(n*logn)次，上方链接博客有所推导。
空间复杂度： O(1)
稳定性：
不稳定（升序建大堆，会使位置交换）
2.3 交换排序
2.3.1基本思想
所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
2.3.2冒泡排序
代码实现：
void BubbleSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
bool exchange = false;
for (int j = 0; j < n - 1-i; j++)
{
if (a[j] > a[j + 1])
{
Swap(&a[j], &a[j + 1]);
exchange = true;
}
}
if (!exchange)
{
break;
}
}
}
性能分析：
时间复杂度：
最好和最坏都是O(n^)，如果加了那句话，那最好就是O(n).
空间复杂度： O(1)
稳定性： 稳定
2.3.3 快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止
同学们在写递归框架时可想想二叉树前序遍历规则即可快速写出来，后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。
将区间按照基准值划分为左右两半部分的常见方式有：
1. hoare版本
代码实现：
void QuickSort(int* a, int left, int right)
{
if (left >= right)
{
return;
}
int randi = left+rand()%(right-left);
Swap(&a[randi], &a[left]);
int begin = left, end = right;
int keyi = left;
while (left < right)
{
while (left<right&&a[right] >=a[keyi])
{
right--;
}
while (left<right&&a[left] <= a[keyi])
{
left++;
}
Swap(&a[right], &a[left]);
}
Swap(&a[left], &a[keyi]);
QuickSort(a, begin, left - 1);
QuickSort(a, left + 1, end);
}
这里有好几个细节值得我们注意！
1.为什么要进行这个操作？
2. 为什么相等的时候一定要往前/后跳？
如果不往后跳在下面的情况下会出现死循环：
3.为什么在每一个判断之前要多一个判断？冗余吗？
在之前加入了相等的条件以后，如果出现很多相同数字的情况下，可能左右指针会错开。还有一种可能是数组本身就有序，没有这个判断使其错开。
4.为什么相遇的位置一定是keyi的位置？
这就是为什么我们在规定左边为keyi以后一定要让右边先走。
- 右边找到小，但是左边找大没有找到，此时相遇，交换小的数据
- 右边没有找到小，直接遇到相遇，此时左边的位置不是keyi的位置就是比keyi小的位置。
2. 挖坑法
个人认为和上面的hoare类似，只是稍微做了些改动，我们直接看代码：
代码实现：
int QuickSort(int* a, int left, int right)
{
if (left >= right)
{
return;
}
int hole = left;
int key = a[left];
int begin = left, end = right;
while (right > left)
{
while (left<right&&a[right] >= key)
{
right--;
}
a[hole] = a[right];
hole = right;
while (left<right&&a[left] <= key)
{
left++;
}
a[hole] = a[left];
hole = left;
}
a[hole] = key;
QuickSort(a, begin, hole - 1);
QuickSort(a, hole + 1, end);
}
3. 前后指针版本
通过动图可知，一直让cur++找小，当cur找到比key小的值,++prev，随后让prev位置的值交换，直到cur越界为止。所以prev要么紧跟cur，要么其下一个就是cur。prev和cur之间的元素就是比key大的元素，就像推土机一样，把比key大的往右翻，比key小的值翻到左边。
int QuickSort(int* a, int left, int right)
{
if (left >= right)
{
return;
}
int keyi = left;
int prev=left, cur=left+1;
while (cur <= right )
{
if (a[cur] < a[keyi])
{
prev++;
Swap(&a[cur], &a[prev]);
}
cur++;
}
Swap(&a[keyi], &a[prev]);
QuickSort(a, left, prev - 1);
QuickSort(a, prev + 1, right);
}
4.非递归法
上文快速排序的三个版本都使用了递归，当数据量过大，建立的栈帧空间过多时，容易产生栈溢出，导致错误。所以我们要学习 将代码从递归改为非递归避免错误 是以后我们工作的必备技能。
通过画之前快排的递归图我们会发现，其递归方式很像二叉树的前序遍历，也就是操作完一个数据以后，操作该数据的子数据。所以，快速排序的非递归需要使用到栈 使用栈辅助改为循环。
如何利用栈将快排改为循环呢？我们将数组左右下标压入栈，为了出栈顺序为先左后右，我们则要先压右下标，再压左下标。每次排完一组，就将key左右两边的数组的左右下标压入。然后当栈非空时,就持续弹出区间给快排函数排序，当左右区间数据为空时，停止压栈。
void QuickSortNonR(int* a, int begin, int end)
{
Stack q;
StackInit(&q);
StackPush(&q,begin);
StackPush( &q,end);
while (!empty(&q))
{
int right = StackTop(&q);
StackPop(&q);
int left = StackTop(&q);
StackPop(&q);
int key = a[left];
int prev = left, cur = left + 1;
while (cur <= right)
{
if (a[cur] < key)
{
prev++;
Swap(&a[cur], &a[prev]);
}
cur++;
}
Swap(&a[prev], &a[left]);
if (left < prev - 1)
{
StackPush(&q, left);
StackPush(&q, prev - 1);
}
if (prev + 1 < right)
{
StackPush(&q, prev + 1);
StackPush(&q, right);
}
}
StackDestroy(&q);
}
2.3.4 快速排序优化
a.key的选择：
在这里就不得不提一下快排的缺点了，如果我们要排的数组是有序的或逆序的，会出现什么糟糕的情况呢？
因为是有序的，如果每次都拿最左边的元素做key，那么每一次递归只能减少一个元素，所以最后要递归1+2+3+4+……N次，此时的时间复杂度为夸张的O(N^2)，所以寻找key的值十分重要。
随机找key：
顾名思义，就是在数组中随机找一个数作为key，为了与之前的代码联系起来，我们可以将其与left所指元素交换位置，这样key就相当于还在left处。
int randi = left+rand() % (right - left);
Swap(&a[left], &a[randi]);
在这里一定要记得＋left，因为每一次的key不一定都是0作为下标。
三数取中
三数取中比上面随机取更优一些，因为随机取数仍有可能取到最大的和最小的，而三数取中大大减小了这种概率。
int Getmid(int left, int right,int *a)
{
int mid = (left + right) / 2;
if (a[mid] > a[left])
{
if (a[mid] < a[right])
{
return mid;
}
else if(a[mid]>a[right]&&a[right]>a[left])
{
return right;
}
else
{
return left;
}
}
else
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[mid] < a[right] && a[right] > a[left])
{
return left;
}
else
{
return right;
}
}
}
int mid = Getmid(left, right,a);
Swap(&a[mid],& a[left]);
b.小区间优化：
在递归的最后一层，递归的次数占所有递归次数的一半，如果我们在很小的数据量时使用插入排序，就能减小很多次递归。
void InQuickSort(int* a, int left, int right)
{
if (left >= right)
return;
if (right - left + 1 > 10)
{
//int keyi = PartSort1(a,left,right);
int keyi=PartSort2(a,left,right);
//int keyi = PartSort3(a, left, right);
// [begin, keyi-1] keyi [keyi+1, end]
// 递归
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}
else
{
InsertSort(a + left, right - left+1);
}
}
性能分析：
时间复杂度：
其实logN的功能非常强大，对100w个数，在理想情况下我们只用递归20层。所以一共logN层，每层大概操作N次，时间复杂度为N*logN。
最好情况：O(n*logn)
最坏情况：O(n^2)
空间复杂度： O(logN)~O(N)
稳定性： 不稳定（当存在与key相同的数时会导致其位置错位）
2.4 归并排序
2.4.1 基本思想
在学完快排之后，归并排序就可以很快掌握。该算法是采用分治法的一个非常典型的应用。
归并排序核心步骤
先使每个子序列有序，再使子序列段间有序。最后将两个大的有序表合并成一个有序表。
2.4.2 递归实现
void _MergeSort(int* a, int* tmp, int begin, int end)
{
if (end <= begin)
{
return;
}
int mid = (begin + end) / 2;
_MergeSort(a, tmp, begin, mid);
_MergeSort(a, tmp, mid + 1, end);
int begin1 = begin, end1 = mid;
int begin2 = mid + 1, end2 = end;
int j = begin;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] > a[begin2])
{
tmp[j++] = a[begin2++];
}
else
{
tmp[j++] = a[begin1++];
}
}
while (begin1 <= end1)
{
tmp[j++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[j++] = a[begin2++];
}
memcpy(a+begin, tmp+begin, sizeof(int)*(end - begin + 1));
}
void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
return;
}
_MergeSort(a, tmp, 0, n - 1);
free(tmp);
}
在这里我们需要开辟一个新的数组，每归并完一次，都要将tmp数组的这个区间拷贝回a数组，在拷贝时一定要注意拷贝的区间，不然会出错。
2.4.3 非递归实现
由上面的归并排序代码我们可知，排序开始先找到mid 将数据分为两个区间，接着不断递归到区间内只有一个数据才开始进行返回。
所以，我们可以模仿这种方法，按顺序，第一次让相邻区间为1的数据一一归并，第二次让相邻区间为2的数据一一归并……
肯定会有同学疑惑，如果n为奇数，每次不能平均分配怎么办？这里分三类情况讨论：
这里我们有两种方式处理：
-
当我们后面的拷贝是全拷贝的时候，可以通过修改路线法修改边界，最后一把梭哈（拷贝）。
-
当归并一部分拷贝一部分的时候，对于后面begin2，end2超过的部分可以直接不拷贝。
1.end1就越界了，begin2和end2肯定也就越界了，这时只有左区间的部分数据有效，所以无法进行比较＋排入，所以这时的gap是错误了，此次循环不进行直接break。
2.begin2和end2越界时，这时只有左区间有效，无法进行比较＋排入与第一种情况相同直接break
3.最后一种情况只有end2越界了，我们只需将end2赋为正常区间之内即可。
代码实现：
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail\n");
return;
}
int gap = 1;
while (gap < n)
{
for (int i = 0; i < n; i += 2 * gap)
{
// [begin1,end1][begin2, end2]
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
//printf("[%d,%d][%d,%d] ", begin1, end1,begin2,end2);
if (end1 >= n || begin2 >= n)
{
break;
}
if (end2 >= n)
{
end2 = n - 1;
}
printf("[%d,%d][%d,%d] ", begin1, end1, begin2, end2);
int j = i;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[j++] = a[begin1++];
}
else
{
tmp[j++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[j++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[j++] = a[begin2++];
}
// 归并一部门拷贝一部分
memcpy(a+i, tmp+i, sizeof(int) *(end2-i+1));
}
printf("\n");
gap *= 2;
}
free(tmp);
}
性能分析：
时间复杂度： 无论好坏：O(N*logN)
空间复杂度： O(N)
稳定性： 稳定
3.计数排序
计数排序是非比较排序里最常用的一种,适合范围集中，并且范围不大的整形数组排序。
计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤：
- 统计相同元素出现次数
- 根据统计的结果将序列回收到原来的序列中
动图如下：
由于要开辟数组，对于数组的大小我们怎么开辟呢？实际中我们使用的是相对位置映射计数，找到数组的最大值和最小值，其差值就是要开辟的空间大小，最后排序的时候加上最小值即可。
void CountSort(int* a, int n)
{
int max = a[0], min = a[0];
for (int i = 0; i <n ; i++)
{
if (a[i] > max)
{
max = a[i];
}
if (a[i] < min)
{
min = a[i];
}
}
int range = max - min+1;
int* countA = (int*)calloc( range, sizeof(int));
if (countA == NULL)
{
perror("malloc::fail");
return;
}
for (int i = 0; i < n; i++)
{
countA[a[i] - min]++;
}
int j = 0;
for (int i = 0; i < range; i++)
{
while (countA[i]--)
{
a[j++] = i + min;
}
}
free(countA);
}
性能分析：
时间复杂度: O(n+range)
空间复杂度: O(range)
4.排序算法复杂度及稳定性分析
5.源代码
Sort.h
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<assert.h>
#include<stdlib.h>
#include<string.h>
#include"Stack.h"
void Print(int* arr, int sz);
//2
void InsertSort(int* arr, int sz);
//3
void ShellSort(int* arr, int sz);
//1
void BubbleSort(int* arr, int sz);
//4
void SelectSort(int* arr, int sz);
//6
void HeapSort(int* arr, int sz);
//5
void QuickSort(int* arr, int begin, int end);
void QuickSortNonR(int* arr, int begin, int end);
//7
void MergeSort(int* arr, int begin, int end);
void MergeSortNonR(int* arr, int n);
Stack.h
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int STDateType;
typedef struct Stack {
STDateType* arr;
int top;
int capacity;
}Stack;
//初始化
void InitStack(Stack* pst);
//入栈
void PushStack(Stack* pst, STDateType x);
//出栈
void PopStack(Stack* pst);
//取栈顶
STDateType StackTop(Stack* pst);
//判空
bool EmptyStack(Stack* pst);
//求数据个数
int StackSize(Stack* pst);
//销毁
void DestoryStack(Stack* pst);
Stack.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
//初始化
void InitStack(Stack* pst)
{
//int newcapacity = pst->capacity = 0 ? 4 : pst->capacity * 2;
Stack* new = (Stack*)malloc(sizeof(Stack));
if (new == NULL)
{
perror("InitStack:");
exit(-1);
}
pst->arr = new;
pst->capacity = 1;
pst->top = 0;
}
//入栈
void PushStack(Stack* pst, STDateType x)
{
assert(pst);
if (pst->capacity == pst->top)
{
int newcapacity = pst->capacity * 2;
STDateType* new = (STDateType*)realloc(pst->arr,sizeof(STDateType) * newcapacity);
if (new == NULL)
{
perror("InitStack:");
exit(-1);
}
pst->arr = new;
pst->capacity = newcapacity;
}
pst->arr[pst->top] = x;
pst->top++;
}
//出栈
void PopStack(Stack* pst)
{
assert(pst);
assert(pst->top > 0);
pst->top--;
}
//取栈顶
STDateType StackTop(Stack* pst)
{
assert(pst);
assert(pst->top > 0);
return pst->arr[pst->top - 1];
}
//判空
bool EmptyStack(Stack* pst)
{
assert(pst);
return pst->top == 0;
}
//求数据个数
int StackSize(Stack* pst)
{
assert(pst);
return pst->top;
}
//销毁
void DestoryStack(Stack* pst)
{
assert(pst);
free(pst->arr);
pst->capacity = 0;
pst->top = 0;
}
Sort.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Sort.h"
//后面用的多,直接写成函数方便一点
void Swap(int* p, int* q)
{
int tmp = *p;
*p = *q;
*q = tmp;
}
void Print(int* arr, int sz)
{
for (int i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
//思想：冒泡其实没啥说的，注意第二个循环的-1，因为我们
//这里用的是arr[j]和arr[j+1]小心越界的问题
void BubbleSort(int* arr,int sz)
{
int i = 0;
int j = 0;
for (i = 0; i < sz; i++)
{
for (j = 0; j < sz-i-1; j++)
{
if (arr[j] > arr[j + 1])
Swap(&arr[j], &arr[j + 1]);
}
}
}
//思想：开始让第一个数有序，然后从后一个数插入，
//如果后一个数小于前面的数，前面的数就往后挪动
//注意不管是哪种情况退出，最后都是把数据放到
//end+1，所有干脆我们就放在外面
void InsertSort(int* arr, int sz)
{
for(int i = 0; i < sz - 1;i++)
{
int end = i;
int tmp = arr[end + 1];
while (end >= 0)
{
if (arr[end] > tmp)
{
arr[end + 1] = arr[end];
end--;
}
else
{
break;
}
}
arr[end + 1] = tmp;
}
}
//思想：先对数组进行预排序，预排序是为了
//直接插入更快，越有序，直接插入就越快，这
//也是希尔快的原因，预排序完了就直接插入排序
//预排序：分组(离相同gap)为一组进行插入排序
void ShellSort(int* arr, int sz)
{
// 1、gap > 1 预排序
// 2、gap == 1 直接插入排序
int gap = sz;
while (gap>1)
{
//保证最后为直接插入排序
gap = gap / 3 + 1;
//这里i++是使多组预排序同时进行
for (int i = 0; i < sz - gap; i++)
{
int end = i;
int tmp = arr[end + gap];
while (end >= 0)
{
if (tmp < arr[end])
{
arr[end + gap] = arr[end];
end -= gap;
}
else
{
break;
}
}
arr[end + gap] = tmp;
}
}
}
//思路:选两个值的下标,开始都在左边，然后用一个记录下标的cur去遍历数组，
// 一个记录最大(maxi)，一个记录最小(mini)，然后遍历数组把最小的放
// 在左边，最大的，放在右边，直到left,right相遇
void SelectSort(int* arr, int sz)
{
int left = 0;
int right = sz - 1;
while (left<right)
{
int cur = left+1;
int mini = left;
int maxi = left;
//这里注意要等于哈，不然最后一个值就比掉了
//作者开始写的时候就画图搞了半天QAQ
while (cur <= right)
{
if (arr[cur] > arr[maxi])
{
maxi = cur;
}
if (arr[cur] < arr[mini])
{
mini = cur;
}
cur++;
}
Swap(&arr[left], &arr[mini]);
//如果left==maxi left就会
//和mini交换，要更新maxi
if (left == maxi)
{
maxi = mini;
}
Swap(&arr[right], &arr[maxi]);
left++;
right--;
}
}
//hoare
//思路：左边为key，右边先走，找小，左边再走，找大，然后左右交换
//一直循环直到相遇，因为是右边先走，左边已经是找小
//停住了，所有能保证相遇位置大于等于a[jeyi]，然后
//交换a[keyi]和相遇位置的值，这样a[keyi]左边值就
//比他小，右边值就比他大
int PartSort1(int* arr, int left, int right)
{
int keyi = left;
while (left < right)
{
//右找小 注意：keyi在左边就右边先走
//要注意left>right的条件，不然可能越界
while (left < right && arr[right] >= arr[keyi])
{
right--;
}
//左找大
while (left < right && arr[left] <= arr[keyi])
{
left++;
}
Swap(&arr[left], &arr[right]);
}
Swap(&arr[left], &arr[keyi]);
return left;
}
//挖坑法
//思路:左边为key，先存起来，变成坑，左右两边一个变量
//右边先走，找小，然后交换，左边找大，然后交换
//最后把key的值给相遇位置
int PartSort2(int* a, int left, int right)
{
int pi = left;
int qi = right;
int key = a[left];
while (pi < qi)
{
//右找小
while (a[qi] > key && pi < qi)
{
qi--;
}
a[pi] = a[qi];
//左找大
while (a[pi] < key && pi < qi)
{
pi++;
}
a[qi] = a[pi];
}
a[qi] = key;
return qi;
}
int GetMidIndex(int* a, int left, int right)
{
//int mid = (left + right) / 2;
int mid = left + (right - left) / 2;
// left mid right
if (a[left] < a[mid])
{
if (a[mid] < a[right])
{
return mid;
}
else if (a[left] > a[right])
{
return left;
}
else
{
return right;
}
}
else // a[left] > a[mid]
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
}
//前后指针法
//左边为keyi，用两个变量存储left和left+1，cur去找小，
//找到了prev++再交换然后cur++，没有找到就cur++,
//这样可以保证让prev到cur的值都大于等于a[keyi]
//最后交换a[keyi]和a[prev]
int PartSort3(int* a, int left, int right)
{
//yysy，自己实现不加也行
//下面这两句也是优化，处理了有序O(N^2)的情况
int midi = GetMidIndex(a, left, right);
Swap(&a[midi], &a[left]);
int cur = left + 1;
int prev = left;
int keyi = left;
while (cur <= right)
{
//这一步很巧哈，可以多理解一下
//注意是前置++
if (a[cur] < a[keyi] && a[++prev] != a[cur])
{
Swap(&a[cur], &a[prev]);
}
cur++;
}
Swap(&a[keyi], &a[prev]);
return prev;
}
//递归
void QuickSort(int* arr, int begin, int end)
{
// 子区间相等只有一个值或者不存在那么就是递归结束的子问题
if (begin >= end)
return;
//小区间优化
// 小区间直接插入排序控制有序
//yysy，自己实现不加也行
if (end - begin + 1 <= 10)
{
InsertSort(arr + begin, end - begin + 1);
}
else
{
int keyi = PartSort3(arr, begin, end);
// [begin, keyi-1]keyi[keyi+1, end]
QuickSort(arr, begin, keyi - 1);
QuickSort(arr, keyi + 1, end);
}
}
//非递归
void QuickSortNonR(int* arr, int begin, int end)
{
Stack st;
InitStack(&st);
PushStack(&st, begin);
PushStack(&st, end);
while (!EmptyStack(&st))
{
int right = StackTop(&st);
PopStack(&st);
int left = StackTop(&st);
PopStack(&st);
//left keyi-1 keyi+1 right
int keyi = PartSort1(arr, left, right);
if (left < keyi-1)
{
PushStack(&st, left);
PushStack(&st, keyi-1);
}
if (keyi + 1 < right)
{
PushStack(&st, keyi + 1);
PushStack(&st, right);
}
}
}
//升序建大堆
先找左右小的孩子
//再和root的比 比root小就交换
//root等于那个要交换的孩子 孩子再选 然后迭代
void AdjustDown(int* arr,int root,int sz)
{
//默认左孩子
int child = root * 2 + 1;
int parent = root;
while (child<sz)
{
1、选出左右孩子中大的那个
if (child + 1 < sz && arr[child + 1] > arr[child])
child++;
//2、如果孩子大于父亲，则交换，并继续往下调整
if (arr[child] > arr[parent])
{
Swap(&arr[parent], &arr[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
//思想：用向下调整算法建大堆(升序)，然后把堆顶的数据
//换到最后，然后缩小数据范围，再次向下调整，反复如此
void HeapSort(int* arr, int sz)
{
//向下调整--建大堆 O(N)
int curpos = (sz - 1 - 1) / 2;
while (curpos >= 0)
{
AdjustDown(arr, curpos, sz);
curpos--;
}
//end为最后一个元素下标
int end = sz - 1;
while (end >0)
{
Swap(&arr[0], &arr[end]);
//每次从0开始向下调
AdjustDown(arr, 0, end);
end--;
}
}
void _MergeSort(int* arr, int* tmp, int begin, int end)
{
if (begin >= end)
return;
//先分后合
//为了防止数据溢出
int mid = begin + (end - begin) / 2;
//注意这里我们分成 begin - mid 和 mid+1 - end
//分成 begin - mid-1 和 mid - end 有bug (1,2)会死循环
int begin1 = begin; int end1 = mid;
int begin2 = mid+1; int end2 = end;
_MergeSort(arr, tmp, begin1, end1);
_MergeSort(arr, tmp, begin2, end2);
//printf("begin1:%d end1:%d \nbegin2:%d end2:%d\n", begin1, end1, begin2, end2);
//开始归
int i = begin;
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] < arr[begin2])
tmp[i++] = arr[begin1++];
else
tmp[i++] = arr[begin2++];
}
while(begin1 <= end1)
tmp[i++] = arr[begin1++];
while (begin2 <= end2)
tmp[i++] = arr[begin2++];
//注意第三个参数是字节大小.....开始还以为是上面错了，找半天
//注意要加上begin 因为并不是每次都是初始位置
memcpy(arr + begin, tmp + begin, (end - begin + 1)*sizeof(int));
}
//思想：先分再合
//注意我们要先把排号的数据先放进tmp数组，
//然后把数组的数据拷回arr
void MergeSort(int* arr, int begin, int end)
{
int* tmp = (int*)malloc((end-begin+1) * sizeof(int));
assert(tmp);
//避免重复开辟空间就用副本函数
_MergeSort(arr, tmp, begin, end);
free(tmp);
}
//思想：不分，直接和，注意和快排转非递归不一样，快排是前序，
//所以转非递归用栈和队列都可以，但是后续不好那么搞，
//我们直接暴力求
void MergeSortNonR(int* arr, int n)
{
int* tmp = (int*)malloc(n * sizeof(int));
assert(tmp);
int gap = 1;
int begin1 = 0; int end1 = 0;
int begin2 = 0; int end2 = 0;
while (gap < n)
{
for (int i = 0; i < n; i += 2 * gap)
{
begin1 = i; end1 = i + gap - 1;
begin2 = i + gap; end2 = i + 2 * gap - 1;
//如果 end1 越界
if (end1 >= n)
end1 = n - 1;
//如果 begin2 越界 end2 越界
if (begin2 >= n && end2 >= n)
{
begin2 = n;
end2 = n - 1;
}
//如果 end2 越界
if (begin2 < n && end2 >= n)
end2 = n - 1;
int index = i;
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] < arr[begin2])
tmp[index++] = arr[begin1++];
else
tmp[index++] = arr[begin2++];
}
while (begin1 <= end1)
tmp[index++] = arr[begin1++];
while (begin2 <= end2)
tmp[index++] = arr[begin2++];
}
memcpy(arr,tmp,n*sizeof(int));
gap *= 2;
}
free(tmp);
}
test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Sort.h"
void TestOP()
{
srand((unsigned int)time(0));
const int N = 10000000;
int* a1 = (int*)malloc(sizeof(int) * N);
assert(a1);
int* a2 = (int*)malloc(sizeof(int) * N);
assert(a2);
int* a3 = (int*)malloc(sizeof(int) * N);
assert(a3);
int* a4 = (int*)malloc(sizeof(int) * N);
assert(a4);
int* a5 = (int*)malloc(sizeof(int) * N);
assert(a5);
int* a6 = (int*)malloc(sizeof(int) * N);
assert(a6);
int* a7 = (int*)malloc(sizeof(int) * N);
assert(a7);
for (int i = 0; i < N; ++i)
{
a1[i] = rand();
a2[i] = a1[i];
a3[i] = a1[i];
a4[i] = a1[i];
a5[i] = a1[i];
a6[i] = a1[i];
a7[i] = a1[i];
}
int begin1 = clock();
//InsertSort(a1, N);
int end1 = clock();
int begin2 = clock();
ShellSort(a2, N);
int end2 = clock();
int begin3 = clock();
//SelectSort(a3, N);
int end3 = clock();
int begin4 = clock();
HeapSort(a4, N);
int end4 = clock();
int begin5 = clock();
QuickSort(a5, 0, N - 1);
int end5 = clock();
int begin6 = clock();
MergeSort(a6, 0, N-1);
int end6 = clock();
int begin7 = clock();
//BubbleSort(a7, N);
int end7 = clock();
printf("InsertSort:%d\n", end1 - begin1);
printf("ShellSort:%d\n", end2 - begin2);
printf("BublleSort:%d\n", end7 - begin7);
printf("SelectSort:%d\n", end3 - begin3);
printf("HeapSort:%d\n", end4 - begin4);
printf("QuickSort:%d\n", end5 - begin5);
printf("MergeSort:%d\n", end6 - begin6);
printf("MergeSort:%d\n", end7 - begin7);
free(a1);
free(a2);
free(a3);
free(a4);
free(a5);
free(a6);
free(a7);
}
void test1()
{
int arr[] = { 1,7,2,5,3,4,9,8 };
int sz = sizeof(arr) / sizeof(arr[0]);
//InsertSort(arr, sz);
//BubbleSort(arr, sz); //1
//SelectSort(arr, sz);
//QuickSort(arr, 0,sz-1);
//QuickSortNonR(arr, 0, sz - 1);
//HeapSort(arr, sz);
//ShellSort(arr, sz);
//MergeSort(arr, 0, sz-1);
//MergeSortNonR(arr, sz);
Print(arr, sz);
}
int main()
{
//test1();
TestOP();
return 0;
}
总结
这就是八大排序的所有内容，这篇文章真的花了三天时间来完成，希望大家支持一下啊呜呜呜
更新不易，辛苦各位小伙伴们动动小手，👍三连走一走💕💕 ~ ~ ~ 你们真的对我很重要！最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！
专栏订阅：
每日一题
c语言学习
算法
智力题
初阶数据结构
更新不易，辛苦各位小伙伴们动动小手，👍三连走一走💕💕 ~ ~ ~ 你们真的对我很重要！最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！
文章出处登录后可见！
已经登录？立即刷新
