`
飘零羽
  • 浏览: 25406 次
  • 性别: Icon_minigender_1
  • 来自: 沈阳
社区版块
存档分类
最新评论

基础算法复习篇(一)——插入排序算法

阅读更多

经过一个假期对基础算法知识的学习,总算在近期告一段落,正好在刚开学的这一段冷却期,为了加深对算法的记忆与理解,准备对假期所学习的算法知识进行一定的总结与分析,算是对前一阶段所学知识的总结吧,也许在这期间还能发掘出当初没有想到的想法,算是很随性的总结吧,那么从今天开始,便由浅入深的对基本的算法进行一定的复习。

在这篇文章中将介绍一个非常简单的排序算法—插入排序算法(Insertionsort)。插入排序的算法的核心便在于原地排序。所谓原地排序指的是,在算法的运行过程中,在待排序对象的容器外仅仅有确定个数的对象。就像我们在桌子上放了一副扑克牌,我们想把每张牌按照牌上数字的大小按照非降序顺序排列之后堆叠在桌上,那么什么叫原地排序呢,我们把放牌堆的桌子认为是盛放牌的容器,我们的双手认为是牌堆之外的空间,我们在排序的过程中,每次仅仅在牌堆里面取得1张牌和牌堆里面的扑克牌进行比较后找到其应当所在的位置之后放回牌堆,然后再取下一张牌~~~如此反复,在算法的每一步在手中牌的数目是一定的,当然不一定非要是一张啦。这么做的好处便是能够有效的节省内存的占用,如果系统的内存资源紧张,这么做的意义是非常明显的。

那么我们首先对算法的具体步骤进行介绍,该算法的代码实现如下:

public class InsertionsortTest {
	/**
	 * 插入排序算法实现
	 * 
	 * @param tempNumbers 待排序数组
	 * @return
	 */
	public static int[] insertionSort(int[] tempNumbers){
		
		for(int index = 1; index < tempNumbers.length; index++){//从待排序数组第二个元素开始向前作比较
			int target = tempNumbers[index];//取得目标元素
			int targetIndex = index - 1;//待比较元素初始化位目标元素前一个
			
			while(targetIndex >= 0 && target < tempNumbers[targetIndex]){//当待比较元素未越界且待比较元素大于目标元素
				tempNumbers[targetIndex + 1] = tempNumbers[targetIndex];//将待比较元素向后移动一位
				targetIndex --;//把前一个元素作为下一个待比较元素
			}
			tempNumbers[targetIndex + 1] = target;//当待比较元素小于目标元素时,讲目标元素插入至待比较元素之后
		}
		
		return tempNumbers;//返回已排列好的数组
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] tempNumbers = {4,1,7,13,11,57,14,6,58};
		int[] targetNumbers = InsertionsortTest.insertionSort(tempNumbers);
		System.out.println(Arrays.toString(targetNumbers));

	}

}

算法的运行过程很简单,具体步骤的意义已经在注释中进行了解释,总体的运行过程就像给扑克排序一样,把元素容器的第二个元素开始的元素作为目标元素,把目标元素与之前的元素进行比较,把之前的元素作为待比较元素若待比较元素大于目标元素便把待比较元素后移一位,并把它原来的前一个元素作为新的待比较元素,直到待比较元素小于目标元素,便把目标元素插入至待比较元素之后。在算法的整个过程中在元素容器之外的元素只有一个当前的目标元素,因此这种排序方法是原地的,能够有效的节省内存的使用。

然而这种算法也有其缺点,那就是只适合小规模数据的排序,对于大规模数据的排序效率便不令人满意了,因为其时间复杂度是O(n2)级别的,既然是n方级别的,那么随着输入数据数量级的增长,其排序所需时间的增长过于巨大,效率不能令人满意。在处理小规模数据的过程中效率还是可观的,因此,有人的想法便是利用分治法将大规模的数据分解成小规模的数据集,进行排序之后再进行排序。

虽说算法的效率不算太高,不过毕竟是入门算法,而且实现简单,在平时数据量很小时还是能很好的解决问题的,至于比较高效的算法,实现复杂度也会相应的提高,那么我们应该在以后的文章中能够见到。

 

分享到:
评论

相关推荐

    数据结构与算法综合资料库

    插入排序法 程序设计:哈希表的一个应用 多维数组下标操作符重载一法 汉诺塔的非递归 回朔法一例 几道有趣的算法题 阶梯问题的递归解法 精确迭代法 矩阵求逆的快速算法 快 速 排 序 马踏棋盘问题 冒 泡 法 排序算法 ...

    数据结构与算法综合资料库.CHM

    插入排序法 程序设计:哈希表的一个应用 多维数组下标操作符重载一法 汉诺塔的非递归 回朔法一例 几道有趣的算法题 阶梯问题的递归解法 精确迭代法 矩阵求逆的快速算法 快 速 排 序 马踏棋盘问题 冒 泡 法 排序算法 ...

    数据结构及算法编程(阿蒙工作室)

    ☆ 插入排序法 ☆ 程序设计:哈希表的一个应用 ☆ 多维数组下标操作符重载一法 ☆ 汉诺塔的非递归 ☆ 何谓数据结构 ☆ 回朔法一例 ☆ 几道有趣的算法题 ☆ 阶梯问题的递归解法 ☆ 精确迭代法 ☆ 矩阵求逆的快速算法 ...

    数据结构讲义(严蔚敏版)(含算法源码).rar

    一、 基础知识和算法 7 1. 线性表及其特点 7 2. 顺序表——线性表的顺序存储结构 7 3. 单链表——线性表的链式存储结构之一 10 4. 循环链表 15 5. 双向循环链表 15 6. 顺序表与单链表的比较 16 二、 习题 16 第3章 ...

    数据结构与算法分析第二版 ---C语言描述(附加答案)

    排序7.1 预备知识7.2 插入排序7.2.1 算法7.2.2 插入排序的分析7.3 一些简单排序算法的下界7.4 希尔排序7.4.1 希尔排序的最坏情形分析7.5 堆排序7.5.1 堆排序的分析7.6 归并排序7.6.1 归并排序的分析7.7 快速排序...

    数据结构与算法分析

     7.3 一些简单排序算法的下界   7.4 谢尔排序   7.5 堆排序   7.6 归并排序   7.7 快速排序   7.7.1 选取枢纽元   7.7.2 分割策略   7.7.3 小数组   7.7.4 实际的快速排序例程  ...

    数据结构与算法分析_Java语言描述(第2版)

    7.3 一些简单排序算法的下界 7.4 希尔排序 7.5 堆排序 7.6 归并排序 7.7 快速排序 7.7.1 选取枢纽元 7.7.2 分割策略 7.7.3 小数组 7.7.4 实际的快速排序例程 7.7.5 快速排序的分析 7.7.6 选择问题的线性期望时间算法...

    数据结构与算法分析Java语言描述(第二版)

    排序7.1 预备知识7.2 插入排序7.2.1 算法7.2.2 插入排序的分析7.3 一些简单排序算法的下界7.4 希尔排序7.5 堆排序7.6 归并排序7.7 快速排序7.7.1 选取枢纽元7.7.2 分割策略7.7.3 小数组7.7.4 实际的快速排序例程...

    数据结构与算法分析C描述第三版

     7.3 一些简单排序算法的下界   7.4 谢尔排序   7.5 堆排序   7.6 归并排序   7.7 快速排序   7.7.1 选取枢纽元   7.7.2 分割策略   7.7.3 小数组   7.7.4 实际的快速排序例程   7.7.5...

    数据结构与算法分析_Java语言描述(第2版)]

    排序7.1 预备知识7.2 插入排序7.2.1 算法7.2.2 插入排序的分析7.3 一些简单排序算法的下界7.4 希尔排序7.5 堆排序7.6 归并排序7.7 快速排序7.7.1 选取枢纽元7.7.2 分割策略7.7.3 小数组7.7.4 实际的快速排序例程...

    数据结构与算法分析 Java语言描述第2版

    排序7.1 预备知识7.2 插入排序7.2.1 算法7.2.2 插入排序的分析7.3 一些简单排序算法的下界7.4 希尔排序7.5 堆排序7.6 归并排序7.7 快速排序7.7.1 选取枢纽元7.7.2 分割策略7.7.3 小数组7.7.4 实际的快速排序例程...

    数据结构与算法分析-Java语言描述(第2版)_2_2

    练习 参考文献第7章 排序 7.1 预备知识 7.2 插入排序 7.2.1 算法 7.2.2 插入排序的分析 7.3 一些简单排序算法的下界 7.4 希尔排序 7.5 堆排序 7.6 归并排序 7.7 快速排序 7.7.1 选取枢纽元 ...

    数据结构与算法分析-Java语言描述(第2版)_1_2

    练习 参考文献第7章 排序 7.1 预备知识 7.2 插入排序 7.2.1 算法 7.2.2 插入排序的分析 7.3 一些简单排序算法的下界 7.4 希尔排序 7.5 堆排序 7.6 归并排序 7.7 快速排序 7.7.1 选取枢纽元 ...

    软件工程之专题九:数据结构知识

     线性结构——结构中的数据元素之间存在一个对一个的关系。  树形结构——结构中的元素之间存在一个对多个的关系。  图状结构或网状结构——结构中的元素之间存在多个对多个的关系。 数据结构中,结点与结点间...

Global site tag (gtag.js) - Google Analytics