大佬教程收集整理的这篇文章主要介绍了【数据结构】排序算法——选择排序和堆排序,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
以升序为例,假设有n个数据,每一趟在后面n-i的待排序的数据元素集合中选出关键码最小的数据元素,作为有序序列的第i个元素,直至待排序集合中只剩下1个元素。
举一个例子:
时间复杂度:直接选择算法需要遍历每一趟选出最小的一个数,遍历n遍,时间复杂度为O(N^2)
稳定性:是一种不稳定的算法。
void SELEctSort(int* array,int sizE)
{
for (size_t i = 0; i < size-1; i++)
{
size_t maxPos = 0;
for(size_t j = 1; j < size - i; j++)
{
if(array[j] > array[maxPos])
maxPos = j;
}
if(maxPos != size - i - 1)
swap(array[maxPos],array[size - i - 1]);
}
}
我们可以对这种直接选择排序法进行改进,在上述的算法中,我们每一次从前向后的n-i(i从0开始)个数据中找最小的数据,并将其放到第i个位置;这里改变一下,不光从前向后找最下的数据,同时,从后向前找最大的数据,分别把他们放到对应的位置,这样,我们就可以少跑几趟了。
void SELEctSortOP(int* array,int sizE)
{
size_t begin = 0;
size_t end = size-1;
while(begin < end)
{
size_t maxPos = begin;
size_t minPos = begin;
size_t i = begin+1;
while(i <= end)
{
if(arraY[i] > arraY[R_407_11845@axPos])
maxPos = i;
if(arraY[i] < arraY[R_407_11845@inPos])
minPos = i;
i++;
}
if(maxPos != end)
swap(arraY[R_407_11845@axPos],arraY[end]);
if (minPos == end)//最小元素出现在最大元素的位置
minPos = maxPos;
if(minPos != begin)
swap(arraY[R_407_11845@inPos],arraY[begin]);
begin++;
end--;
}
}
堆排序是指利用堆这种数据结构所进行的排序,利用数组的特点快速定位指定索引的元素。利用堆进行排序,比较的次数和交换的次数均比冒泡排序或选择排序少,性能较高。
void Adjust(int* array,int size,size_t parent)
{
size_t child = parent*2+1;
while(child < sizE)
{
if(child+1 < size && array[child+1] > array[child])
child += 1;
if(array[parent] < array[child])
{
swap(array[parent],array[child]);
parent = child;
child = parent*2+1;
}
else
break;
}
}
void HeapSort(int* array,size_t sizE)
{
// 1. 创建堆
int root = (size-2)>>1;
for(; root >= 0; --root)
Adjust(array,size,root);
// 2. 堆排序
size_t end = size-1;
while(end)
{
swap(array[0],array[end]);
Adjust(array,end,0);
end--;
}
}
以上是大佬教程为你收集整理的【数据结构】排序算法——选择排序和堆排序全部内容,希望文章能够帮你解决【数据结构】排序算法——选择排序和堆排序所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。