做网站3个月,建设内容管理网站的目的,嘉兴关键词优化服务,网站开发总结简写目录
前言
一.选择排序
1.思想
2.实现
3.特点
二.堆排序
1.思想
2.实现
3.特点 前言 排序算法是计算机科学中的基础工具之一#xff0c;对于数据处理和算法设计有着深远的影响。了解不同排序算法的特性和适用场景#xff0c;能够帮助程序员在特定情况下…目录
前言
一.选择排序
1.思想
2.实现
3.特点
二.堆排序
1.思想
2.实现
3.特点 前言 排序算法是计算机科学中的基础工具之一对于数据处理和算法设计有着深远的影响。了解不同排序算法的特性和适用场景能够帮助程序员在特定情况下选择最合适的算法从而提高程序的效率和性能。本节我们讲述选择排序和堆排序。
一.选择排序
1.思想
基本思想是在未排序的部分中选择最小和最大的元素然后将其与未排序部分的第一个元素和最后一个交换位置。重复这个过程直到整个序列有序。
选择排序的步骤如下 初始状态 将整个序列分为已排序部分和未排序部分初始时已排序部分为空未排序部分包含所有元素。 选择最小元素 在未排序部分中找到最小和最大的元素并记录其位置。 交换位置 将找到的最小元素与未排序部分的第一个元素交换位置。最大元素与最后一个元素交换。 更新已排序部分和未排序部分 将交换后的元素视为已排序将原未排序部分减少二个元素继续从未排序部分重复步骤2和步骤3。 重复直至完成 重复上述过程直到整个序列有序。
2.实现
void SelectSort(int* a, int n)
{int gap 0;int end n - 1;while (gap end){int maxi gap, mini gap;for (int i gap1; i end; i){if (a[mini] a[i]){mini i;}if (a[maxi] a[i]){maxi i;}}Swap(a[gap], a[mini]);if (gap maxi){maxi mini;}Swap(a[end], a[maxi]);gap;end--;}
} 注意:为了避免最大值为第一个时,被最小值交换时换走,我们修正一下,如果第一个值就是最大值,那么当第一个值与最小值交换后,修正最大值的位置
时间复杂度:O(n^2)
空间复杂度O(1)
稳定性:不稳定
3.特点
1.优势: 交换操作相对较少 选择排序的交换操作次数相对较少每次只进行一次交换。这使得它在某些场景下可能比冒泡排序更有效。 适用于小规模数据集 在数据规模较小的情况下选择排序的性能可能相对较好因为其简单性和交换操作的相对少。
2.缺点 时间复杂度高 选择排序的时间复杂度为O(n^2)其中n是待排序序列的长度。这意味着对于大规模数据集选择排序的性能可能相对较差尤其是与一些O(nlog n)时间复杂度的算法相比。 不稳定 选择排序是一种不稳定的排序算法。当存在相等元素时它可能会改变它们的相对顺序使得选择排序在某些应用场景中不适用。 对逆序数据的不足 在对逆序数据完全逆序排列的情况进行排序时选择排序的性能较差。每次选择最小元素时都需要在未排序的部分中进行线性搜索导致交换操作次数较多。
二.堆排序
1.思想
堆排序是一种基于二叉堆Binary Heap数据结构的排序算法。堆是一个特殊的树状数据结构其中每个节点的值都不大于或不小于其子节点的值。堆可以分为最大堆和最小堆。(可以看这个堆的实现与操作-CSDN博客)
堆排序的基本思想如下 建堆 将待排序序列构建成一个二叉堆。对于最大堆父节点的值大于或等于其子节点的值对于最小堆父节点的值小于或等于其子节点的值。 排序 不断将堆顶元素与堆的最后一个元素交换然后对除最后一个元素外的部分重新调整成堆。这样每次交换后最大或最小元素就被放置在了正确的位置。重复这个过程直到整个序列有序。
2.实现
void AdjustDown(int* a,int parent,int size)//向下调整建堆
{int child parent *2 1;while (child size){if (child1sizea[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) / 2; i 0; i--){AdjustDown(a, i, n);}int end n-1 ;while (end){Swap(a[0], a[end]);AdjustDown(a, 0, end );end--;}
} 这里我们采用向下调整建堆,从第一个非叶子节点开始,建大堆后,每次将堆顶元素调整到数组后面,再调整堆
时间复杂度:O(nlogn)
空间复杂度O(1)
稳定性:不稳定
3.特点
1.优势: 时间复杂度稳定 堆排序的时间复杂度为O(n log n)其中n是待排序序列的长度。这使得堆排序在大规模数据集上具有相对较好的性能。 适用于大规模数据 由于其O(n log n)的时间复杂度堆排序对于大规模数据集的排序任务是一个较好的选择特别是相对于一些O(n^2)复杂度的排序算法。
2.缺点: 不稳定性 堆排序是一种不稳定的排序算法。在交换的过程中可能会改变相同元素的相对顺序。对于需要保持相等元素相对位置关系的应用场景不稳定性可能是一个不可接受的缺点。 对于小规模数据 尽管堆排序在大规模数据集上表现良好但在小规模数据集上它的性能可能不如一些简单且更容易实现的排序算法如快速排序或插入排序。
