`

算法回顾之二:直接插入排序

 
阅读更多

算法回顾系列第二篇:直接插入排序算法

-------------------------------------------

直接插入排序

基本原理:

把n个待排序的元素看成为一个有序表和一个无序表。

开始时有序表中只包含一个元素,无序表中包含有n-1个元素。排序过程中每次从无序表中取出第一个元素,将它插入到有序表中的适当位置,使之成为新的有序表,重复n-1次可完成排序过程。

程序实现:

public void sort(int[] data) {
	int temp;
	for(int i=1;i<data.length;i++){//已排序(有序表)的元素个数(第一个元素默认看作已排序).
		//有序表的下一个元素(j)如果小于已排序的最大元素(j-1),则交换位置.
		//如此向前(j--)与每个元素比较直到找到小于它的元素(data[j]<data[j-1])或者到第一个元素(j>0).
		for(int j=i; (j>0)&&(data[j]<data[j-1]); j--){//for的初始化条件j=i只执行1次.
			temp = data[j];
			data[j] = data[j-1];
			data[j-1] = temp;
		}
		System.out.println("Sort"+i+":"+Arrays.toString(data));//每趟排序后的结果.
	}
}

上面程序中:

外层循环i代表已经排序的元素个数(即有序表的元素个数)。从1开始计数,表明第一个元素默认是有序的。

内层循环j代表无序表的第一个元素,j-1即有序表的最后一个元素。两个元素比较:

如果无序表的第一个元素大于有序表的最后一个元素,则结束本趟排序(因为有序表的最后一个元素一定是最大的,无序表的第一个元素如果比它还大,不需要交换位置)。

如果无序表的第一个元素小于有序表的最后一个元素,则交换位置,然后继续与有序表的倒数第二个元素进行比较,直到找到有序表中比它小的元素或者它排在了第一个时,结束本趟排序。

如此直到排序完N-1个元素(第一个元素无需排序)。

 

性能分析:

1、待排序元素已从小到大排好序(正序)或接近排好序时,所用的比较次数和移动次数较少;

2、当待排序元素已从大到小排好序(逆序)或接近排逆序时,所用的比较次数和移动次数较多。

最坏时间复杂度:O(n^2)

 

空间复杂度:1。

稳定性:稳定的排序。

 

分享到:
评论

相关推荐

    数据结构排序实验报告

    - 算法原理:先将整个待排序的记录序列分割成若干子序列分别进行直接插入排序,最后再对整个序列进行一次直接插入排序。 - 时间复杂度:取决于增量序列的选择,通常介于O(n)到O(n^2)之间。 - 空间复杂度:O(1)。 ...

    实验五:内部排序.docx

    - 插入排序:直接插入排序是将元素逐个插入到已排序部分,如插入排序。 - 交换排序:通过交换元素来排序,如快速排序、冒泡排序。 - 选择排序:每次选择最小(或最大)元素放入正确位置,如简单选择排序。 - ...

    算法设计与分析课件和习题

    2. **排序与搜索算法**:包括冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等,以及二分查找、哈希查找等搜索方法。 3. **分治策略**:如快速排序、归并排序、大整数乘法(Karatsuba和Toom-Cook算法)...

    算法设计英文版课件:ALG_review.ppt

    排序算法如冒泡排序、插入排序、选择排序以及更高效的算法如堆排序和快速排序,它们的时间复杂度各有不同。二维排名查找则在二维数组中寻找特定元素,其效率也直接影响算法的实用性。 此外,课程还会讨论问题的难度...

    数据结构第九章排序讲稿.doc

    4. **插入排序**:这是最基础的排序算法之一,包括直接插入排序(逐个将元素插入已排序部分)、折半插入排序(利用二分查找减少比较次数)和表插入排序(如希尔排序,通过增量序列改进插入排序的效率)。 5. **快速...

    算法分析与设计 试卷

    1. **排序算法**:冒泡排序、插入排序、选择排序、快速排序、归并排序、堆排序等的原理、优缺点及适用场景。 2. **查找算法**:顺序查找、二分查找、哈希查找等的实现和效率。 3. **图论算法**:深度优先搜索、...

    数据结构与算法分析 C++版 Clifford 第二版 答案

    ### 数据结构与算法分析 C++版 Clifford 第二版 答案 #### 一、概述 本书《数据结构与算法分析》(C++版)由Clifford A. Shaffer编写,是计算机科学领域内非常重要的教材之一。本书旨在帮助读者深入理解数据结构的...

    《数据结构与算法》课后习题答案

    - **算法描述**:本题要求在已排序的线性表中插入一个新元素,并保持列表的有序性。通过遍历线性表找到合适位置,然后进行元素移动并插入。 - **时间复杂度分析**:最坏情况下需要遍历整个线性表,因此时间复杂度...

    JAVA近百种算法大全打包.zip

    1. **排序算法**:包括快速排序、归并排序、冒泡排序、插入排序、选择排序、堆排序等。这些排序算法各有特点,例如快速排序平均时间复杂度为O(nlogn),归并排序适合大数据量,而冒泡排序则适用于小规模数据。 2. **...

    数据结构与算法:C#语言描述(中文)

    - **主要内容**:介绍简单的排序算法,如冒泡排序和插入排序。 - **学习目标**:理解并能够实现基础的排序算法。 - **第四章:基本查找算法** - **主要内容**:探讨顺序查找和二分查找这两种基本的查找算法。 ...

    C语言版数据结构与算法分析-严蔚敏经典视频教程

    10-001排序的定义、直接插入排序、冒泡排序、快速排序 10-002堆排序、多关键字的排序、基数排序、排序时间复杂度的分析 10-003外部排序的基本过程、索引文件、哈希文件的结构 10-004多关键字文件的特点、倒排文件、...

    Java数据结构和算法(第二版)

    接着,“算法的概述”章节将涵盖排序、查找和其他常见算法,如冒泡排序、选择排序、插入排序、快速排序、归并排序、二分查找等。这些算法是解决问题的基础工具,理解它们的工作原理能够帮助开发者在面对特定问题时...

    算法复习要点整理

    减治法在算法设计中有着广泛的应用,如插入排序、深度优先与广度优先搜索等,都是通过逐步减少问题规模来达到求解目的。 #### 变治法:转化与解决的智慧 变治法是一种基于变换思想的算法设计策略,其核心在于通过...

    数据结构与算法课程总结

    六种排序算法(直接插入、希尔、冒泡、快速、直接选择、归并)是本章的重点,其中快速排序和归并排序的时间复杂度分析需要进一步理解。 第三章“链表及其应用”涉及线性逻辑结构在链式存储下的数据结构——链表。...

    《数据结构算法与应用》中文教材

    排序算法的种类繁多,包括简单的冒泡排序、选择排序、插入排序,到效率更高的快速排序、归并排序、堆排序。这些算法在不同的应用场景和数据规模下,选择不同,各自具备不同的时间复杂度和空间复杂度特性。搜索算法...

    java数据结构和算法实现

    冒泡排序是最简单的排序算法之一,通过不断交换相邻的错误顺序元素来实现排序。在Java中,可以使用嵌套循环来实现冒泡排序。虽然冒泡排序效率相对较低,但对于小规模数据或教学用途,它是很好的选择。冒泡排序的时间...

    Sorting-Visualizer:排序算法可视化器

    2. **算法种类**:该工具支持多种经典的排序算法,如冒泡排序、插入排序、选择排序、快速排序、归并排序、堆排序等。每种算法都有详细的步骤展示,便于用户分析和比较它们的效率和性能。 3. **代码实现**:作为一个...

Global site tag (gtag.js) - Google Analytics