算法描述:
伪代码:
注:伪代码中的下标从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; } }
相关推荐
* 插入排序算法的伪代码:INSERTION-SORT (A, n)⊳ A[1 . . n] for j ← 2 to n do key ← A[ j] i ← j – 1 while i > 0 and A[i] > key do A[i+1] ← A[i] i ← i – 1 A[i+1] = key 算法分析 * 算法分析的定义...
#### 算法导论课后习题答案 **知识点概述:** 本文档提供了《算法导论》一书中的部分课后习题解答,旨在帮助学习者更好地理解算法原理及其应用。文档作者Philip Bille强调了独立解决问题的重要性,并将此文档视为...
- **插入排序 vs 归并排序**:在某些情况下,插入排序可能比归并排序更优,尤其是在小规模数据集上。文档中提到,当满足条件 `8n^2 时,插入排序的性能优于归并排序。 - **解析**:通过代入不等式计算得到,对于 ...
### 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编写,他...
综上所述,《算法导论》中的习题解答笔记提供了对经典算法的理解和应用实例,包括插入排序、归并排序、线性搜索和选择排序等算法的深入探讨,以及它们在特定场景下的表现和优化策略。这些知识点对于学习和研究算法...
#### 算法导论习题答案 - **知识点1:插入排序与归并排序性能对比** - 插入排序和归并排序是两种常用的排序算法,它们在不同的数据规模下表现不同。 - 插入排序在小规模数据上表现优秀,而归并排序在大规模数据上...
### 麻省理工学院-算法导论讲义 #### 一、课程介绍与目标 在麻省理工学院开设的《算法导论》课程(课程编号:6.046J/18.401J/SMA5503)中,教授Charles E. Leiserson将带领学生深入理解算法的基础知识及其应用。该...
### 第二版《算法导论》习题答案分析 #### 标题与描述解析 - **标题**:“第二版的算法导论习题答案(1-35章)” - **描述**:“第二版的算法导论习题答案(1-35章),非常之经典,大家都可以看看” 该资料提供了...
- **2.1-2:逆序插入排序**:通过修改INSERTION-SORT算法中的条件语句,可以实现元素的非递增排序。 - **2.1-3:线性搜索算法**:提供了LINEAR-SEARCH算法的伪代码实现。该算法用于在一维数组中查找特定值。此外,给...
1. **排序算法**:包括快速排序(Quick Sort)、归并排序(Merge Sort)、堆排序(Heap Sort)和插入排序(Insertion Sort)。快速排序是一种效率极高的分治策略,通过选取一个“枢轴”元素将数组划分为两个部分,...
#### 一、关于《算法导论》第二版及答案文档概述 《算法导论》(第二版)是一本经典的计算机科学教材,由Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest等知名学者编写。该书深入浅出地介绍了算法的...
本文通过《算法导论》这本书的C语言实现,深入介绍了插入排序、随机化以及归并排序等核心概念和技术细节。这些算法在实际应用中非常广泛,理解它们的实现机制有助于更好地掌握算法的设计与优化。同时,学习如何在...