`

【算法导论】插入排序 Insertion-Sort

阅读更多

算法描述:



 

伪代码:


              注:伪代码中的下标从1开始 

 

过程示意图:

 

 

 

个人简单理解解释:

        这个算法其实是个比较基础的算法了,也是一个常见的问题,其思想主要是将一个元素插入到一个已经排好序的序列中,操作就是从第二个元素开始,将这个元素保存在一个临时变量中,依次与前面的所有元素从后到前进行比较,如果小于等于(或者大于等于)前面的元素,则把前面的元素向后移动,直至不符合条件为止。

          就好比拿着一张牌,将这张牌依次与前面的每一张牌进行比较,然后插到相应的位置上。

 

 Java实现:

 

 

/**
 * 插入排序算法
 * @author henushang
 */
public class InsertionSort {
	public static void main(String[] args) {
		int[] array = {5, 2, 4, 6, 1, 3};
		int[] sortedArray = insertionSort(array);
		System.out.println(Utils.printArray(sortedArray));
	}
	
	/**
	 * 插入排序算法(升序)
	 * @param array
	 * @return
	 * @author henushang
	 */
	static int[] insertionSort(int[] array) {
		for(int j=1; j < array.length; j++) {
			int key = array[j];
			int i = j -1;
			while (i >= 0 && array[i] > key) {
				array[i + 1] = array[i];
				i --;
			}
			array[i + 1] = key;
		}
		return array;
	}
}

 

 


 

 

 

  • 大小: 25.3 KB
  • 大小: 34.3 KB
  • 大小: 58.3 KB
1
1
分享到:
评论

相关推荐

    麻省理工学院算法导论笔记.pdf

    * 插入排序算法的伪代码:INSERTION-SORT (A, n)⊳ A[1 . . n] for j ← 2 to n do key ← A[ j] i ← j – 1 while i &gt; 0 and A[i] &gt; key do A[i+1] ← A[i] i ← i – 1 A[i+1] = key 算法分析 * 算法分析的定义...

    算法导论课后习题答案

    #### 算法导论课后习题答案 **知识点概述:** 本文档提供了《算法导论》一书中的部分课后习题解答,旨在帮助学习者更好地理解算法原理及其应用。文档作者Philip Bille强调了独立解决问题的重要性,并将此文档视为...

    柯尔曼-算法导论-第2版-习题解答

    - **插入排序 vs 归并排序**:在某些情况下,插入排序可能比归并排序更优,尤其是在小规模数据集上。文档中提到,当满足条件 `8n^2 时,插入排序的性能优于归并排序。 - **解析**:通过代入不等式计算得到,对于 ...

    MIT算法导论课件

    ### MIT算法导论课件知识点概述 #### 一、课程介绍 - **课程代码与名称**:本课程的代码为6.046J/18.401J/SMA5503,名为《算法导论》。 - **授课教师**:由Charles E. Leiserson教授主讲。 - **开课时间**:Fall ...

    算法导论讲义

    ### 算法导论讲义 #### 一、课程介绍 本课程为麻省理工学院(MIT)开设的《算法导论》课程,编号为6.046J/18.401J/SMA5503。本课程由Charles E. Leiserson教授授课,旨在为学生提供算法设计与分析的基础知识。 ###...

    算法导论答案

    《算法导论答案》是针对计算机科学领域内经典教材《算法导论》(Introduction to Algorithms,简称CLR,因三位作者Cormen、Leiserson、Rivest的姓氏首字母而得名)的习题解答集合。这份文档由Philip Bille编写,他...

    麻省理工学院算法导论中英文版习题笔记全\solution to CLR(算法导论习题答案).pdf

    综上所述,《算法导论》中的习题解答笔记提供了对经典算法的理解和应用实例,包括插入排序、归并排序、线性搜索和选择排序等算法的深入探讨,以及它们在特定场景下的表现和优化策略。这些知识点对于学习和研究算法...

    算法导论习题答案

    #### 算法导论习题答案 - **知识点1:插入排序与归并排序性能对比** - 插入排序和归并排序是两种常用的排序算法,它们在不同的数据规模下表现不同。 - 插入排序在小规模数据上表现优秀,而归并排序在大规模数据上...

    麻省理工学院-算法导论讲义

    ### 麻省理工学院-算法导论讲义 #### 一、课程介绍与目标 在麻省理工学院开设的《算法导论》课程(课程编号:6.046J/18.401J/SMA5503)中,教授Charles E. Leiserson将带领学生深入理解算法的基础知识及其应用。该...

    第二版的算法导论习题答案(1-35章)

    ### 第二版《算法导论》习题答案分析 #### 标题与描述解析 - **标题**:“第二版的算法导论习题答案(1-35章)” - **描述**:“第二版的算法导论习题答案(1-35章),非常之经典,大家都可以看看” 该资料提供了...

    MIT算法导论pdf版本英文版版课后答案

    - **2.1-2:逆序插入排序**:通过修改INSERTION-SORT算法中的条件语句,可以实现元素的非递增排序。 - **2.1-3:线性搜索算法**:提供了LINEAR-SEARCH算法的伪代码实现。该算法用于在一维数组中查找特定值。此外,给...

    MIT算法导论-Introduction to Algorithms-算法实现

    1. **排序算法**:包括快速排序(Quick Sort)、归并排序(Merge Sort)、堆排序(Heap Sort)和插入排序(Insertion Sort)。快速排序是一种效率极高的分治策略,通过选取一个“枢轴”元素将数组划分为两个部分,...

    算法导论第二版答案

    #### 一、关于《算法导论》第二版及答案文档概述 《算法导论》(第二版)是一本经典的计算机科学教材,由Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest等知名学者编写。该书深入浅出地介绍了算法的...

    算法导论 源代码 C语言实现

    本文通过《算法导论》这本书的C语言实现,深入介绍了插入排序、随机化以及归并排序等核心概念和技术细节。这些算法在实际应用中非常广泛,理解它们的实现机制有助于更好地掌握算法的设计与优化。同时,学习如何在...

Global site tag (gtag.js) - Google Analytics