【数据结构】排序算法——选择排序和堆排序
发布时间:2020-12-15 06:34:29 所属栏目:安全 来源:网络整理
导读:选择排序 1.基本思想 以升序为例,假设有n个数据,每一趟在后面n-i的待排序的数据元素集合中选出关键码最小的数据元素,作为有序序列的第i个元素,直至待排序集合中只剩下1个元素。 2.操作步骤 举一个例子: 3.算法性能 时间复杂度:直接选择算法需要遍历每
选择排序1.基本思想以升序为例,假设有n个数据,每一趟在后面n-i的待排序的数据元素集合中选出关键码最小的数据元素,作为有序序列的第i个元素,直至待排序集合中只剩下1个元素。 2.操作步骤 举一个例子: 3.算法性能 时间复杂度:直接选择算法需要遍历每一趟选出最小的一个数,遍历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[maxPos])
maxPos = i;
if(array[i] < array[minPos])
minPos = i;
i++;
}
if(maxPos != end)
swap(array[maxPos],array[end]);
if (minPos == end)//最小元素出现在最大元素的位置
minPos = maxPos;
if(minPos != begin)
swap(array[minPos],array[begin]);
begin++;
end--;
}
}
堆排序1.基本思想堆排序是指利用堆这种数据结构所进行的排序,利用数组的特点快速定位指定索引的元素。利用堆进行排序,比较的次数和交换的次数均比冒泡排序或选择排序少,性能较高。 2.具体步骤
3.算法性能
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--;
}
} (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |