即使走的再远,也勿忘启程时的初心
C/C++ 游戏开发
Hello,米娜桑们,这里是君兮_,首先在这里祝大家中秋国庆双节同乐!!今天用一篇文章为大家把八大排序算法都过一遍,当然由于篇幅的原因不是每一种算法都详解,这篇文章更多是作为让初学者有一个初步的了解以及学过的人某个排序算法忘了的话的快速回忆,后续我也会把每种算法的重点以及难点挑出来单独为大家讲解的
// 插入排序
void InsertSort(int* a, int n) //a为所需排序的数组,n为该数组数据的个数
{
for (int i = 0; i < n - 1; i++)
{
//从0开始,多趟插入
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;
}
}
这一步其实可有可无,注意看,如果下一次tmp还小于a[end],此时a[end+1]也就是上一轮的a[end]就会被赋值,当tmp大于a[end]时,循环结束a[end+1]也会被赋值,因此无论是哪种情况这段代码都是进行了相应的处理的,因此是否把tmp赋值给a[end]也就无关紧要了。
直接插入排序的特性总结:
1. 元素集合越接近有序,直接插入排序算法的时间效率越高
2. 时间复杂度:O(N^2)
3. 空间复杂度:O(1),它是一种稳定的排序算法
4. 稳定性:稳定
// 希尔排序
void ShellSort(int* a, int n) // a为待排序数组,n为数据个数
{
//让gap等于n,第一次排序时gap为n/2,之后gap/=2,直到gap==1,进行最后一次希尔排序,完成对所需排序数据的排序
int gap = n;
while (gap>1)
{
gap /= 2;
for (int i = 0; i < n - gap; i++)
{
//从第0个元素开始
int end = i;
//每个元素间隔为gap
int tmp = a[end + gap];
//每一趟预排序
while (end >= 0)
{
if (tmp < a[end])
{
a[end + gap] = a[end];
//所需比较元素的间隔为gap
end-=gap;
}
else
break;
}
a[end + gap] = tmp;
}
}
// 选择排序
void SelectSort(int* a, int n)
{
int begin = 0;
int end = n - 1;
while (begin < end)//等于与大于时只剩下1个或0个元素,停止选择排序
{
//暂时让最大和最小的都指向begin
int minSize = begin;
int maxSize = begin;
//最大最小都指向begin,从begin+1开始
for (int i = begin+1; i <= end; i++)
{
//找该组数据中最大的元素,通过maxSize保存其下标
if (a[i] > a[maxSize])
{
maxSize = i;
}
//找该组数据中最小的元素,通过minSize保存其下标
if (a[i] < a[minSize])
{
minSize = i;
}
}
Swap(&a[begin], &a[minSize]);//交换最小和此时的begin
//修正
if (maxSize == begin)
maxSize = minSize;
Swap(&a[end], &a[maxSize]);//交换最大和此时的end
begin++;//找次大和次小的
end--;
}
}
//修正
if (maxSize == begin)
maxSize = minSize;
堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。它是
通过堆来进行选择数据。需要注意的是排升序要建大堆,排降序建小堆
以排升序为例
1、将待排序的数据构造成一个大堆,当前堆的根节点(堆顶)就是该组数组中最大的元素;
2、将堆顶元素和最后一个元素交换,将剩下的节点重新构造成一个大堆;
3、重复步骤2,每次循环构建都能找到当前堆中的最大值,并通过交换的方式把它放到该大堆的尾部,直至所有元素全部有序
具体实现
1、从根节点开始,选出左右孩子中值较大的一个
2、如果选出的孩子的值大于父亲的值,那么就交换两者的值,不大于,说明此时孩子和父亲都处于合适的位置,不再向下调整
3、将大的孩子看做新的父亲,继续向下调整,直到调整到叶子节点为止
// 堆排序
void AdjustDwon(int* a, int n, int parent)
{
int child = parent * 2 + 1;
//到叶子节点就停止
while (child < n)
{
//选出孩子中最大的
if (child + 1 < n && a[child + 1] > a[child])
{
child++;
}
//孩子比父亲大就交换,并使此时的孩子成为下一次循环的父亲
if (a[parent] < a[child])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
//父亲更大,由于左右子树一定是大堆,不需要进一步朝下进行,直接退出循环
else
{
break;
}
}
}
//这里n是数组元素个数,i作为下标-1,同时在由孩子找父亲时,parent=(child-1)/2 因此这里的i为(n-2)/2
for (int i = (n - 1 - 1) / 2; i >=0; i--)
{
AdjustDwon(a, n, i);
}
1、建好堆之后,将堆顶的数字与最后一个数字交换(建的是大堆,堆顶一定是最大的数)
2、将最后一个数字排除,剩下的n-1个元素再向下调整成堆再循环进行第一步
3、直到最后只剩一个数时就停止排序。
首先,我们能确保的是,堆顶的数一定是最大的,因此把它交换的数排在此时的最后一位是合理的。
其次,我们交换上去的数字会向下调整到正确的位置,这样既保证了根节点的左右子树是大堆又能使每个交换上去的节点处于合适的位置。
重点是从后往前排的,我们一定能确保最后的数是交换下去的最大的,次大的依次类推就能保证我们排好的数据有序。
void HeapSort(int* a, int n)
{
//建大堆
for (int i = (n - 1 - 1) / 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--;
}
}
新人博主创作不易,如果感觉文章内容对你有所帮助的话不妨三连一下再走呗。你们的支持就是我更新的动力!!!
**(可莉请求你们三连支持一下博主!!!点击下方评论点赞收藏帮帮可莉吧)**