【排序算法篇】---直接插入排序
🌏个人博客主页:意疏-CSDN博客
【排序算法篇】— 直接插入排序
前言
💬欢迎交流:在学习过程中如果你有任何疑问或想法,欢迎在评论区留言,我们可以共同探讨学习的内容。你的支持是我持续创作的动力!
👍点赞、收藏与推荐:如果你觉得这篇文章对你有所帮助,请不要忘记点赞、收藏,并分享给更多的小伙伴!你们的鼓励是我不断进步的源泉!
🚀推广给更多人:如果你认为这篇文章对你有帮助,欢迎分享给更多对算法感兴趣的朋友,让我们一起进步,共同提升!
直接插入排序简介
直接插入排序是一种常见而简单的排序算法,其基本思想是将待排序的元素插入到一个已经排好序的有序序列中,从而生成一个新的有序序列。排序的过程可以被视为将待排序的数组分成两个部分:已排序部分和未排序部分。在每一步中,从未排序部分取出一个元素,并将其插入到已排序部分的适当位置,直到所有元素均被插入为止。
具体的实现步骤如下:
- 初始化:将第一个元素视为一个有序序列,后续元素逐个取出进行插入操作。
插入操作: - 从第二个元素开始,依次取出当前元素,将其与已排序序列中的元素进行比较。
- 如果当前元素小于已排序序列中的元素,则将较大的元素右移一位,这样为当前元素腾出位置。
- 一直比较直到找到当前元素的合适位置,将其插入其中。
重复上述步骤:对每个元素执行插入操作,直到未排序的元素全部插入完成。
插入排序代码
public class InsertionSort {
public static void main(String[] args) {
int[] array = {29, 10, 14, 37, 16};
// 执行插入排序
insertionSort(array);
// 打印排序后的数组
System.out.println("排序后的数组:");
for (int num : array) {
System.out.print(num + " ");
}
}
public static void insertionSort(int[] array) {
// 从第二个元素开始遍历数组
for (int i = 1; i < array.length; i++) {
int current = array[i]; // 当前元素
int j = i - 1;
// 找到当前元素的位置
while (j >= 0 && array[j] > current) {
array[j + 1] = array[j]; // 右移
j--;
}
array[j + 1] = current; // 插入当前元素
}
}
}
时间复杂度和空间复杂度
直接插入排序的时间复杂度取决于输入数据的状态:
最好的情况是数据已经是有序的,这时只需要进行 n - 1 次比较,时间复杂度为 O(n)。
最坏的情况是数据是逆序的,此时每个元素都需要与已排序的所有元素比较,时间复杂度为 O(n^2)。 空间复杂度为 O(1),因为该算法是原地排序,不需要额外的存储空间。
稳定性
直接插入排序是一种稳定的排序算法,即相同的元素在排序后仍然保持原来的相对位置。这对于某些应用来说是非常重要的[5]。
总结
综上所述,直接插入排序是一种简单易懂但效率较低的排序方法,适合于小规模数据的排序。在实际应用中,当数据量较小时,它的效率可能超过更复杂的排序算法。
意气风发,漫卷疏狂
学习是成长的阶梯,每一次的积累都将成为未来的助力。我希望通过持续的学习,不断汲取新知识,来改变自己的命运,并将成长的过程记录在我的博客中。
如果我的博客能给您带来启发,如果您喜欢我的博客内容,请不吝点赞、评论和收藏,也欢迎您关注我的博客。
您的支持是我前行的动力。听说点赞会增加自己的运气,希望您每一天都能充满活力!
愿您每一天都快乐,也欢迎您常来我的博客。我叫意疏,希望我们一起成长,共同进步。
我是意疏 下次见!
原文地址:https://blog.csdn.net/2302_79751907/article/details/142595181
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!