欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

重走算法路之简单排序(插入)

程序员文章站 2022-07-14 08:47:09
...

         今天继续排序之路,今天要贴出的是插入排序,也属于简单的排序,对于数量小的排序,它还是一个很有效的算法,

     

      以下属于本人 粗暴讲解

     

       原理

       它的工作方式很像人们打牌插牌一样,从起得第一张牌开始,然后接下来的到的牌如果比手里的牌大就放后面,如果比前面的牌小就放在前面,一样大的就和当前的牌搁一起就可以了,起完所有的牌,按照这样的方法就能把手里的牌排好序了所以会从待排序的第二个元素开始,然后和前面的数进行比较。依次下去,直到最后一个元素。

     

        时间复杂度:

        和前面的冒泡排序有的一拼http://mntms.iteye.com/admin/blogs/2044246也是O(n2);所以当要处理的数据量很大的时候效率还是有那么低,当然,当处理少量数据的时候,它和冒泡排序一样是值得选择的,因为比较简单嘛,而且也容易理解。

     

 

         图文理解:

        
重走算法路之简单排序(插入)
            
    
    博客分类: 算法(Algorithm) 算法简单排序插入 
 

   

 

          代码:

   

package 插入排序;

/**
 * 插入排序
 * @author TMs
 *
 */
public class InsertionSort {
	private long[] array;
	private int count;
	
	public static void main(String[] args) {
		InsertionSort is = new InsertionSort(10);
		is.insert(34);
		is.insert(4);
		is.insert(3);
		is.insert(234);
		is.insert(334);
		is.insert(24);
		is.insert(0);
		is.insert(3224);
		is.insert(134);
		is.insert(0);
		
		is.getSize();
		System.out.println("排序前:");
		is.display();
		is.insertionSort();
		System.out.println("排序后:");
		is.display();
	}
	
	/**
	 * 构造一个大小为max的数组大小
	 * @param max 数组的元素个数的最大值
	 */
	public InsertionSort(int max) {
		array = new long[max];
		count = 0;
	}
	
	/**
	 * 向数组中插入一个值
	 * @param value 插入的值
	 */
	public void insert(long value) {
		array[count] = value;
		count++;
	}
	
	/**
	 * 打印 当前数组中的个数
	 */
	public void getSize() {
		System.out.println("数组中当前元素的总数为:"+count);
	}
	
	/**
	 * 打印数组中的元素
	 */
	public void display() {
		for(int i = 0; i < count; i++) {
			System.out.println("array["+i+"]="+array[i]+" ");
		}
		System.out.println();
	}
	
	/**
	 * 对数组进行插入排序
	 */
	public void insertionSort() {
		for(int i=count-1; i > 0; i--) {
			for(int j = count-i; j>0; j--) {
				if(array[j]<array[j-1]) {
					exchange(j,j-1);
				}
			}
		}
	}
	
	/**
	 * 交换元素 
	 * @param x 下标x
	 * @param y 下标y
	 */
	public void exchange(int x,int y) {
		long  temp;
		temp = array[x];
		array[x] = array[y];
		array[y] = temp;
	}
}

           输入输出结果:

 

数组中当前元素的总数为:10
排序前:
array[0]=34 
array[1]=4 
array[2]=3 
array[3]=234 
array[4]=334 
array[5]=24 
array[6]=0 
array[7]=3224 
array[8]=134 
array[9]=0 

排序后:
array[0]=0 
array[1]=0 
array[2]=3 
array[3]=4 
array[4]=24 
array[5]=34 
array[6]=134 
array[7]=234 
array[8]=334 
array[9]=3224 

 

 

 PS:第二个简单的排序,希望自己能坚持每天能搞懂一个东西,然后贴出来(这可能是 最好的了)学  校的课也多,大二狗也只能每天在这个时候安安静静的写写blog,对一天的总结,也对自己的一个交  代,睡觉,晚上吃多了会长胖!

       

       

 

  • 重走算法路之简单排序(插入)
            
    
    博客分类: 算法(Algorithm) 算法简单排序插入 
  • 大小: 46.2 KB