谷歌建站哪家好,马关县网站建设,网站开发的响应式和兼容性问题,游戏推广群目录 #x1f552; 1. 直接选择排序#x1f552; 2. 堆排序 #x1f552; 1. 直接选择排序
#x1f4a1; 算法思想#xff1a;第一次从待排序的数据元素中选出最小#xff08;或最大#xff09;的一个元素#xff0c;存放在序列的起始#xff08;末尾#xff09;位置… 目录 1. 直接选择排序 2. 堆排序 1. 直接选择排序 算法思想第一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始末尾位置然后选出次小或次大的一个元素存放在最大最小元素的下一个位置重复这样的步骤直到全部待排序的数据元素排完。
代码实现如下这里可以进行一个优化最小值和最大值同时选然后将最小值与起始位置交换将最大值与末尾位置交换。
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}void SelectSort(int* a, int n)
{int begin 0; // 起始位置int end n - 1; // 结束位置// 循环直到整个数组都被排序while (begin end){int mini begin; // 保存最小元素下标int maxi begin; // 保存最大元素下标// 在当前未排序部分查找最小和最大元素的下标for (int i begin 1; i end; i){if (a[i] a[mini]){mini i; // 更新最小元素下标}if (a[i] a[maxi]){maxi i; // 更新最大元素下标}}// 将找到的最小元素交换到起始位置Swap(a[begin], a[mini]);// 如果最大元素的位置在起始位置更新最大元素下标为 miniif (maxi begin){maxi mini;}// 将找到的最大元素交换到末尾位置Swap(a[end], a[maxi]);// 缩小排序范围begin;--end;}
}选择排序的特性总结
选择排序步骤非常好理解但是效率不是很好不论数组是否有序都会执行原步骤实际中很少使用。时间复杂度O(N2)空间复杂度O(1)稳定性不稳定 2. 堆排序 算法思想堆排序即利用堆的思想来进行排序总共分为两个步骤1. 建堆升序建大堆降序建小堆 2. 利用堆删除思想来进行排序建堆和堆删除中都用到了向下调整因此掌握了向下调整就可以完成堆排序。
这里以升序为例
首先应该建一个大堆不能直接使用堆来实现。可以将需要排序的数组看作是一个堆但需要将数组结构变成堆结构。我们可以从堆从下往上的第二行最右边开始依次向下调整直到调整到堆顶这样就可以将数组调整成一个堆且如果建立的是大堆堆顶元素为最大值。然后按照堆删的思想将堆顶和堆底的数据交换但不同的是这里不删除最后一个元素。这样最大元素就在最后一个位置然后从堆顶向下调整到倒数第二个元素这样次大的元素就在堆顶重复上述步骤直到只剩堆顶时停止。 // AdjustDown函数在数组a中从节点root开始向下调整使得以root为根的子树满足大顶堆的性质。
void AdjustDown(int* a, int n, int root)
{assert(a);int parent root; // 当前子树的根节点int child parent * 2 1; // 左孩子节点// 循环直到没有孩子节点while (child n){// 如果右孩子存在且比左孩子大则选择右孩子作为比较对象if (child 1 n a[child 1] a[child]){child;}// 如果孩子节点比父节点大则交换父节点和孩子节点的值并更新父节点和孩子节点继续向下比较if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break; // 如果孩子节点不再比父节点大则退出循环}}
}void HeapSort(int* a, int n)
{assert(a);// 建立大顶堆for (int i (n - 1 - 1) / 2; i 0; i--){AdjustDown(a, n, i); // 对每个非叶子节点进行向下调整建立大顶堆}// 交换堆顶元素和末尾元素并重新调整堆for (int i n - 1; i 0; i--){Swap(a[i], a[0]); // 将当前堆顶最大值与数组末尾元素交换AdjustDown(a, i, 0); // 调整剩余堆为大顶堆范围缩小为0到i-1}
}堆排序的特性总结
堆排序使用堆来选数效率较高适用于需要频繁插入和删除的场景。时间复杂度O(N*logN)空间复杂度O(1)稳定性不稳定 ❗ 转载请注明出处 作者HinsCoder 博客链接 作者博客主页
