网站备案被取消,公司自己做网站,旅游网站建设设计公司,网站后台维护主要做什么目录 前言
一.插入排序
1.思想
2.实现
3.特点
二,希尔排序
1.思想
2,实现
3.特点 前言 排序算法是计算机科学中的基础工具之一#xff0c;对于数据处理和算法设计有着深远的影响。了解不同排序算法的特性和适用场景#xff0c;能够帮助程序员在特定情况下选择最合适的…
目录 前言
一.插入排序
1.思想
2.实现
3.特点
二,希尔排序
1.思想
2,实现
3.特点 前言 排序算法是计算机科学中的基础工具之一对于数据处理和算法设计有着深远的影响。了解不同排序算法的特性和适用场景能够帮助程序员在特定情况下选择最合适的算法从而提高程序的效率和性能。本节我们讲述插入排序和希尔排序。
一.插入排序
1.思想
插入排序基本思想是将一个元素逐个插入到已经排好序的元素序列中从而得到一个新的有序序列。插入排序的步骤如下 初始状态 假设第一个元素已经是有序序列可以将其视为一个只包含一个元素的序列。 从第二个元素开始 将当前元素与已经排好序的元素比较找到合适的位置插入。 插入操作 将当前元素插入到合适的位置同时调整其他元素的位置以保持已有序序列的有序性。 重复 重复步骤2和步骤3直到所有元素都被插入到有序序列中整个序列变得有序。
2.实现
void InsertSort(int* a, int n)
{for (int i 0; i n - 1; i){int end i;int tmpa[end1];while (end 0){if (tmp a[end]){a[end 1] a[end];end--;}else{break;}}a[end 1] tmp;}
}
时间复杂度:O(n^2)
空间复杂度O(1)
稳定性:稳定
3.特点
1.优势: 对小型数据集的适用性 插入排序在对小型数据集或基本有序的数据集进行排序时表现良好。 适用于链表 插入排序在对链表进行排序时也是一种有效的选择因为它可以通过改变节点的链接来进行排序而无需移动大量数据。 稳定性 插入排序是一种稳定的排序算法即相等元素的相对顺序在排序前后保持不变。
2,缺点: 时间复杂度 插入排序的平均和最坏情况时间复杂度均为O(n^2)其中n是数组的长度。这使得插入排序在处理大规模数据时效率相对较低 对逆序数据的性能较差 当输入数据基本逆序排列时插入排序的性能会显著下降。每次插入都需要移动大量的元素导致算法效率低下。
二,希尔排序
1.思想 插入排序在数组接近有序的时候效率较高,我们就先尝试让数组接近有序.再使用插入排序,这是希尔排序 基本思想是通过将待排序的元素分组对每组使用插入排序然后逐步减小每组的元素数量最终完成整个序列的排序。希尔排序的主要思想包括以下几个步骤 分组数 选择一个递减的序列这个序列的最后一个元素通常是1。常见的步长序列选择有希尔自己提出的 N/2其中N是数组长度或其他更复杂的序列。 分组 将待排序的元素按照步长分成若干个子序列每个子序列相互独立。 对每个子序列进行插入排序 对每个子序列应用插入排序算法将子序列内的元素进行排序。 减小组 缩小步长重复步骤2和步骤3直到步长为1。 最终插入排序 当步长为1时整个序列基本有序此时使用插入排序对整个序列进行一次排序。
2,实现
void ShellSort(int* a, int n)
{int gapn;while (gap 1){gap gap / 3 1;for (int j 0; j gap; j){for (int i 0; i n - gap; i gap){int end i;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];end-gap;}else{break;}}a[end gap] tmp;}}}
} 第一个while循环控制每一组的元素个数,当每一组的元素个数为1是,相当于插入排序,第一个for循环和第二个for循环控制对每一组进行插入排序
时间复杂度:大约O(n^1.3)
空间复杂度O(1)
稳定性:不稳定
3.特点
1.优势: 相对简单 希尔排序的实现相对简单不需要使用递归只涉及到循环和插入排序的基本思想。这使得它在理解和实现上相对容易。 原地排序 希尔排序是一种原地排序算法它只需要一个常数级别的额外空间用于存储临时变量而不需要额外的数据结构。 相对高效 对于中等规模的数据集希尔排序通常比插入排序和冒泡排序等简单排序算法更高效。它通过逐步减小间隔先对较远距离的元素进行排序然后逐渐缩小间隔最终完成整体排序。这样可以使得部分元素在更早的阶段就趋于有序减少了插入排序的工作量。
2.缺点 不稳定性 希尔排序不是稳定的排序算法。当存在相等元素时它可能会改变它们的相对顺序。在某些应用场景中需要保持相等元素的相对位置关系这时候希尔排序可能不是最佳选择。 不适合小规模数据集 尽管希尔排序对于中等规模的数据集表现较好但对于小规模数据集其性能可能不如一些简单的排序算法。例如对于10个或更少的元素插入排序可能更为高效。
