【数据结构】选择排序——选择排序 和 堆排序
一、选择排序
选择排序的思路及其代码
选择排序思路很简单
就是经过将数组遍历选择最小值
将最小值位置的数与数组最前面位置的数进行交换
如此反复，完成排序
为了提高效率我们在一次遍历过程中同时找最大和最小值
代码如下：
//选择排序
void SelectSort(int* a, int n)
{
int maxi = n - 1;
int mini = 0;
while (mini < maxi)
{
//找出最大最小值的下标
int max = maxi;
int min = mini;
for (int i = mini; i <= maxi; i++)
{
if (a[i] > a[max])
{
max = i;
}
if (a[i] < a[min])
{
min = i;
}
}
//将最大最小值进行更新，将最大最小值放到数组两边
Swap(&a[mini], &a[min]);
//若最大值在原最小值的位置，将位置更新
if (max == mini)
{
max = min;
}
Swap(&a[maxi], &a[max]);
maxi--;
mini++;
}
}
运行结果：
选择排序的弊端
因为无论数组中原数组是如何排列
选择排序都要遍历数组
所以它的最好与最坏的情况下
时间复杂度都是 O(N ^ 2)
效率低下，正常情况下是不会使用这个排序的
二、堆排序
以下的链接又对堆和堆排序的讲解：
堆以及堆排序
下面我就直接把代码贴出来：
//向下调整（建大堆）
void AdjustDown(int* a, int parent, int n)
{
//左孩子
int child = parent * 2 + 1;
while (child + 1 < n)
{
//先找左右孩子中大的一个
if (child + 1 < n && a[child] < a[child + 1])
{
child++;
}
//将父亲节点与孩子节点进行比较，将大的移到父亲节点
if (a[parent] < a[child])
{
Swap(&a[parent], &a[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
//堆排序
void HeapSort(int* a, int n)
{
//向下调整建堆
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(a, i, n);
}
//进行堆排序
int size = n - 1;
while (size > 0)
{
//先将堆的第一个数与最后一个数交换
Swap(&a[0], &a[size--]);
//向下调整
AdjustDown(a, 0, size);
}
}
运行结果：
堆排序的时间复杂度为 O(N * logN)
三、速度对比
同时排10000个数
同时排100000个数
同时拍500000个数
排序到这里选择排序就已经非常慢了
我们笔记本是 i9 的 cpu 配置还算可以
跑的时候风扇已经呜呜转了
堆排 1 亿个数
原文地址：https://blog.csdn.net/2302_79968411/article/details/143604763
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！