算法可视化系列——排序算法——插入排序

排序算法可视化系列——篇一“插入排序”

     排序算法是我们经常会用到的基础算法，虽然是基础但是却很重要。而且自己也为了自己学习算法和巩固，所以我选择从基本的排序算法开始实现。

 

插入排序

      基本思想分析：

假设我们现在书柜上有一排高低不同的书，我们需要按照从最矮的到最高的顺序从左到右排列这些书本，那么我们进行的就是对这些书本的排序。现在我们使用插入排序来进行排序，我们从左边开始，比较左边第一本书和相邻的第二本书的高度，如果第一本书高，那么我们就将第一本书放到第二本书后面，这是第二本书就成了第一本书，且我们知道现在前两本书是有序的了；如果第二本书高，那么前两本本来就是有序的，不需要我们排序，我们接着比较第二本书与第三本书，同样，如果第三本书比第二本书低，那么我们将第二本书移动到第三本书的位置，在比较与第一本书的高低，如果比第一本书高，那么就将它放在第二本书的位置，否则将第一本书再放到第二本书的位置，然后再将它放到第一个位置。以此类推，就可以将整个书架的书排成有序的。

 

算法的描述：

    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;
		}
	}
}

 

上面是对于插入排序的一个基本实现，用来体会插入排序的思想，下面是对插入排序的动态演示截图：

 

一. 排序中......

 二. 排序中......

 三. 排序完成

 上面就是插入排序的动态视图，其中界面上的其它排序，会依次再接着的几篇博客中继续进行分析和动态演示。。。。。。敬请期待！嘿嘿！

 

程序源代码附在下面，有需要的可下载：

 

评论

5 楼 wojiaolongyinong 2013-05-21  

消失的气泡 写道

博主，您在这篇博客中贴的代码有几个问题，看下边的代码

while(temp_data < a[index] && index >= 0){  
                a[index + 1] = a[index];  
                index--;   
            }  
            /** 
            *将元素插入 
            */  
            a[index] = temp_data; 

1.如果判断到数组的开始头部门，index是可以等于-1的，所以while判断中，应该先判断index是否大于0，不然如上边的代码一样，数组肯定是越界。
2。最终将元素插入的代码应该是a[index+1] = temp_data，当把元素后移之后，此时的index就是插入的位置，但是下边还有个index--，所以这边肯定是index+1

嗯嗯，是我的大意，对的，应该先判断index，下面那里确实少加了1，是我的疏忽，多谢指教。。。。嘿嘿嘿

4 楼 消失的气泡 2013-05-21  

博主，您在这篇博客中贴的代码有几个问题，看下边的代码

while(temp_data < a[index] && index >= 0){  
                a[index + 1] = a[index];  
                index--;   
            }  
            /** 
            *将元素插入 
            */  
            a[index] = temp_data; 

1.如果判断到数组的开始头部门，index是可以等于-1的，所以while判断中，应该先判断index是否大于0，不然如上边的代码一样，数组肯定是越界。
2。最终将元素插入的代码应该是a[index+1] = temp_data，当把元素后移之后，此时的index就是插入的位置，但是下边还有个index--，所以这边肯定是index+1

3 楼 mnpqxz 2013-05-20  

博主已经很厉害了，膜拜博主啊

2 楼 wojiaolongyinong 2013-05-20  

mnpqxz 写道

只有这个能运行，其它的程序都有DrawLine这个类，

嗯嗯，因为其它有的需要画那条绿线，所以有那个类，是我失误。。。。

1 楼 mnpqxz 2013-05-20  

只有这个能运行，其它的程序都有DrawLine这个类，