`
mixer_a
  • 浏览: 368838 次
社区版块
存档分类
最新评论

排序算法第一篇——插入排序

 
阅读更多

算法描述:

从一个无序的集合中取出一个元素,插入到一个有序的集合的合适位置,有序的集合插入新元素之后,仍然是有序的。所以该算法最核心的部分是要在有序集合中找到合适的插入位置

Java代码:

运行结果:

排序前:
300 748 262 274 284 263 135 283 388 477
第1次排序:
300 748 262 274 284 263 135 283 388 477
第2次排序:
262 300 748 274 284 263 135 283 388 477
第3次排序:
262 274 300 748 284 263 135 283 388 477
第4次排序:
262 274 284 300 748 263 135 283 388 477
第5次排序:
262 263 274 284 300 748 135 283 388 477
第6次排序:
135 262 263 274 284 300 748 283 388 477
第7次排序:
135 262 263 274 283 284 300 748 388 477
第8次排序:
135 262 263 274 283 284 300 388 748 477
第9次排序:
135 262 263 274 283 284 300 388 477 748

算法分析:

在最坏的情况下,内层循环的次数为i才可以找到合适的插入位置,每一次排序,对于一个元素为n的集合,都需要循环n-1次,所以

T(n) = 1 + 2 + ······ + n-1 = O(n^2)

最好的情况下,内层循环的次数为0次就可以找到合适的插入位置,所以总循环次数(不算插入操作时以为的循环)为

T(n) = 1 + 1 + ······ + 1 = n-1 = O(n)

在平均情况下,插入位置随机出现,假设出现的概率相等,这样子内层循环的次数平均为i/2。所以排序总循环次数(不算插入操作时以为的循环)为

T(n) = 1/2+ 2/2 + ······ + (n-1)/2 = (n-1)n/4 = O(n^2)

所以该算法的时间复杂度为O(n^2)。

原地排序:原地排序是指排序过程中不使用临时空间,即排序前和排序后元素都在同一地方的排序。

根据原地排序的定义,插入排序也是一种原地排序。

排序算法稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,ri=rj,且ri在rj之前,而在排序后的序列中,ri仍在rj之前,则称这种排序算法是稳定的;否则称为不稳定的。

从排序算法稳定性的概念来看,插入排序算法是稳定的

分享到:
评论

相关推荐

    算法可视化系列——排序算法——插入排序

    插入排序是原地排序算法,只需要一个额外的空间来存储当前元素,因此空间复杂度为O(1)。 **五、优化策略** 1. **二分插入排序**:在查找插入位置时,采用二分查找可以减少比较次数,提高效率,但总的时间复杂度仍...

    算法可视化系列——排序算法——希尔排序

    1. 定义初始间隔`gap`,一般选择序列的第一个值。 2. 对每个子序列`arr[i], arr[i+gap], ..., arr[n-1]`进行插入排序。 3. 缩小`gap`,通常是除以某个常数或使用特定序列的下一个值。 4. 重复步骤2和3,直到`gap`为1...

    用C语言实现常用排序算法

    本项目旨在实现并比较六种经典的排序算法——直接插入排序、折半插入排序、起泡排序、简单选择排序、堆排序以及2-路归并排序,使用C语言编程。为了全面评估这些算法,我们将在一组随机生成的30000个整数上运行它们,...

    面向对象——排序

    本项目聚焦于面向对象编程中的一个重要应用——排序,通过设计一个程序包来实现多种排序算法,包括插入排序、冒泡排序和快速排序。下面我们将详细探讨这些排序算法。 1. **插入排序**: 插入排序是一种简单直观的...

    常用排序算法——冒泡 选择 插入 快速

    2. 从第一趟开始,每次选出当前无序区中的最小元素,放在已排好序的数列的最后。 3. 重复步骤2,直到所有元素都排好序。 选择排序的时间复杂度为 O(n^2),空间复杂度为 O(1)。 三、冒泡排序(Bubble Sort) 冒泡...

    数据结构算法源代码(插入排序和选择排序)

    在本文中,我们将深入探讨两种基础且重要的排序算法——插入排序和选择排序。这两种排序算法在数据结构和算法的学习中占据着核心地位,因为它们帮助初学者理解排序的基本原理。 首先,我们来看**插入排序...

    java算法——插入排序

    插入排序: * 始终定义第一个元素为有序, 将无序元素 * 逐个插入到有序排列之中,不断的移动数据, * 空出一个适当的位置,把待插入的元素放到里 * 面去。

    (陈慧南 第3版)算法设计与分析——课后习题答案(1~8章)

    1. **第一章:算法基础** 这一章主要介绍了算法的基本概念,包括算法的定义、特性、表示方法以及算法分析的基本方法。其中,算法的时间复杂度和空间复杂度是评估算法效率的关键指标。 2. **第二章:数据结构** ...

    排序算法——选择排序.docx

    1. **理解选择排序**:选择排序从数组的第一个元素开始,遍历数组寻找当前未排序部分的最小(或最大)元素。找到后,将这个最小(或最大)元素与数组的第一个元素交换位置。然后对剩下的元素重复这个过程,直到所有...

    最快的排序算法 图解八大排序算法——我见过的最详细的讲解(转),排序算法数据结构

    选择排序是一种简单的排序算法,思路是选择数组中的最小元素,和第一个元素交换,然后在剩下的元素中选择最小元素,和第二个元素交换,以此类推,直到排序完成。时间复杂度为 O(n^2),空间复杂度为 O(1)。Java 代码...

    8种排序算法(选择排序 冒泡排序 快速排序等~)

    - 遍历整个数组,找到最小元素并将其与第一个元素交换。 - 在剩下的元素中找到最小元素与第二个元素交换。 - 重复此过程,每次从未排序的部分找到最小元素,放到已排序部分的正确位置,直到所有元素排序完成。 2...

    常用排序算法总结——数据结构

    1. 插入排序:例如直接插入排序,它通过将元素逐个插入到已排序的部分中来构建整个有序序列。算法的基本思想是从第二个元素开始,将其与已排序部分的元素逐一比较并插入合适的位置,直到所有元素插入完毕。 2. 交换...

    内部排序的方法——半插入排序

    半插入排序,也称为二分插入排序,是一种在内部排序...尽管在大数据集上可能不如其他高效排序算法(如快速排序、归并排序),但在小规模数据或部分有序数据中,半插入排序提供了一种平衡效率和实现复杂度的解决方案。

    排序算法介绍——冒泡排序+插入排序+选择排序

    本文将重点介绍三种基础的排序算法:冒泡排序、插入排序和选择排序。 首先,我们来看冒泡排序。冒泡排序是一种简单的排序算法,其基本思想是通过重复遍历数组,比较相邻的两个元素并根据需要交换它们的位置,使得每...

    插入排序 减治法——C语言代码

    总的来说,"插入排序 减治法——C语言代码"是一个学习和实践C语言基础排序算法的好例子,通过阅读和理解这段代码,你可以深入理解插入排序的工作原理,以及如何用C语言来实现它。同时,也可以探讨如何将问题解决策略...

    算法与数据结构——c语言版+张乃孝

    书中可能涵盖了排序算法(如冒泡排序、插入排序、快速排序、归并排序)、查找算法(如线性搜索、二分查找)以及图算法(如深度优先搜索、广度优先搜索)等。这些基本算法的理解和熟练运用是每个程序员必备的技能。 ...

    实验1_排序_算法设计与分析_

    在本实验"实验1_排序_算法设计与分析_"中,我们将探讨计算机科学中的核心概念——排序算法。排序是处理数据的重要步骤,特别是在数据分析、数据库管理和计算机图形学等领域。本实验的目标是理解和实现五种经典的排序...

    算法设计与分析——C++ 语言描述[陈慧南编][电子教案].

    3. **第五章:排序算法** - 排序是计算机科学中最常见的问题,本章会介绍多种排序算法,如冒泡排序、选择排序、插入排序、快速排序、归并排序等,通过比较它们的时间复杂度和空间复杂度,理解不同排序方法的适用场景...

    冒泡与插入排序 两个排序算法

    本文将深入探讨两种基本的排序算法——冒泡排序与插入排序,通过对这两种算法的核心思想、实现原理以及优缺点进行详细分析,帮助读者更全面地理解其在实际应用中的地位和作用。 ### 冒泡排序 冒泡排序是一种简单的...

Global site tag (gtag.js) - Google Analytics