排序算法可视化系列——篇一“插入排序”
排序算法是我们经常会用到的基础算法,虽然是基础但是却很重要。而且自己也为了自己学习算法和巩固,所以我选择从基本的排序算法开始实现。
插入排序
基本思想分析:
假设我们现在书柜上有一排高低不同的书,我们需要按照从最矮的到最高的顺序从左到右排列这些书本,那么我们进行的就是对这些书本的排序。现在我们使用插入排序来进行排序,我们从左边开始,比较左边第一本书和相邻的第二本书的高度,如果第一本书高,那么我们就将第一本书放到第二本书后面,这是第二本书就成了第一本书,且我们知道现在前两本书是有序的了;如果第二本书高,那么前两本本来就是有序的,不需要我们排序,我们接着比较第二本书与第三本书,同样,如果第三本书比第二本书低,那么我们将第二本书移动到第三本书的位置,在比较与第一本书的高低,如果比第一本书高,那么就将它放在第二本书的位置,否则将第一本书再放到第二本书的位置,然后再将它放到第一个位置。以此类推,就可以将整个书架的书排成有序的。
算法的描述:
InsertSortAlgorithm
for(循环从第二个比较元素到最后一个元素){
while(循环条件判断i是否满足小于i - 1和是否越数组界){
移动比较过的元素
改变索引
}
经过循环,说明找到了合适位置,则插入
}
从上面的算法描述可以看出,外层循环会执行n-1次,内层循环执行的次数最坏执行i次,所以我们知道整个算法最坏循环会执行1 + 2 + ... + (n - 1) = n*(n-1)/2,则我们知道算法的时间复杂度为O(n^2)
算法的Java简单语言实现:
/** * Java语言对插入排序的基本实现 * 在本实现算法中,采用对基本的整数数组进行排序 * 排序的顺序是从大到小 * */ public void insertSort(int[] a){ /** * 如果只有一个元素,则不需要排序 */ if(a.length > 1){ /** * 依次取出待插入的元素 */ for(int i = 1; i < a.length; i++){ /** * 记录待插入元素 */ int temp_data = a[i]; /** *初始移动索引为当前元素的前一个 */ int index = i - 1; /** *移动前面的元素,直到找到插入位置 */ while(temp_data < a[index] && index >= 0){ a[index + 1] = a[index]; index--; } /** *将元素插入 */ a[index] = temp_data; } } }
上面是对于插入排序的一个基本实现,用来体会插入排序的思想,下面是对插入排序的动态演示截图:
一. 排序中......
二. 排序中......
三. 排序完成
上面就是插入排序的动态视图,其中界面上的其它排序,会依次再接着的几篇博客中继续进行分析和动态演示。。。。。。敬请期待!嘿嘿!
程序源代码附在下面,有需要的可下载:
相关推荐
NULL 博文链接:https://wojiaolongyinong.iteye.com/blog/1867491
NULL 博文链接:https://wojiaolongyinong.iteye.com/blog/1871731
NULL 博文链接:https://wojiaolongyinong.iteye.com/blog/1868188
NULL 博文链接:https://wojiaolongyinong.iteye.com/blog/1867321
代码 基于遗传算法的优化计算——建模自变量降维代码代码 基于遗传算法的优化计算——建模自变量降维代码代码 基于遗传算法的优化计算——建模自变量降维代码代码 基于遗传算法的优化计算——建模自变量降维代码代码...
计算机系的教材,算法导论————————————————————————————————
算法与数据结构——快速排序
算法之NlogN排序算法(csdn)————程序
(10)数据结构之红黑树(三)——删除操作 (11)排序算法(一)——冒泡排序及改进 (12)排序算法(二)——选择排序及改进 (13)排序算法(三)——插入排序及改进 (14)排序算法(四)——归并排序与递归...
排序数据随机产生,针对随机案例,对冒泡排序、箱子排序、堆排序、归并算法,提供排序执行过程的动态图形演示。
设计一个负责排序的程序包,实现多种排序算法,至少包括插入排序、冒泡排序和快速排序算法。 内含代码和实验报告
《算法竞赛入门经典——训练指南》中例题和习题的参考代码,由刘汝佳编写
多个排序算法的比较———C++,欢迎大家下载
算法设计与分析课程——冒泡排序结果
VB常用算法——排序.doc
数据结构课程设计五——排序算法综合分析.doc