java直接插入排序实现与优化

超、凢脫俗 2021-11-11 09:06 222阅读 0赞

# 插入排序－－直接插入排序，shell排序 #

## 直接插入排序： ##

### 　　　　一、定义： ###

直接插入排序是将未排序的数据一个一个的插入到已经排好序的数据中；

所以，直接插入的实现，外层循环表示未排序的数据，为length-1（默认第一个数据为已排好序的数据）

内存循环表示已经排好序的数据；

将一个未排序的数据，与已经排好序的数据进行循环比较，找到插入的正确位置。

### 　　　　二、实现： ###

１．　　　　StringArray类，生成随机数，数据源

package com.sort;
    
    import java.util.Random;
    
    public class StringArray {
    	
    	public static int[] getArray(){
    		int[] datas=new int[1000];
    		Random r=new Random();
    		for(int i=0;i<1000;i++){
    			datas[i]=r.nextInt(100);
    		}
    		return datas;
    	}
    }

２．自定义数据结构IntegerArray，内部包含了一个字符串数组。主要实现的目的是为了能够获取数组中真实元素个数。

package com.sort;
    
    public class IntegerArray {
    
    	private int size;//整数数组的大小
    	
    	public int length;//整数数组包含真实元素的个数
    	
    	private String[] strs;
    	
    	/**
    	 *构造方法，初始化字符串数组
    	 */
    	public IntegerArray(int size){
    		this.size=size;
    		strs=new String[size];
    	}
    	
    	public Integer get(int index){
    		return Integer.valueOf(strs[index]);
    	}
    	
    	public void set(int index,int data){
    		if(strs[index]==null){
    			length++;
    		}
    		strs[index]=String.valueOf(data);
    	}
    	
    	public void insert(int index,int data){
    		if(strs[index]!=null){
    			String[] newStrs=new String[size];
    			for(int j=0;j<length;j++){
    				newStrs[j]=strs[j];
    			}
    			strs[index]=String.valueOf(data);
    			for(int i=index+1;i<size;i++){
    				strs[i]=newStrs[i-1];
    			}
    			length++;
    			return;
    		}
    		set(index,data);
    	}
    	
    	public String toString(){
    		StringBuffer sb=new StringBuffer();
    		for (String string : strs) {
    			sb.append(string+" ");
    		}
    		return sb.toString();
    	}
    }

３．主方法，DirectSort类，里面包含了两种数据结构来实现直接插入排序，

package com.sort;
    
    public class DirectSort {
    
    	public static void main(String[] args) {
    		int[]  datas=StringArray.getArray();
    		long start=	System.currentTimeMillis();
    		System.out.println(sort(datas));
    		//System.out.println(sortRe(datas));
    		long end=System.currentTimeMillis();
    		System.out.println(String.valueOf(end-start));
    	}
    	
    	//自定义数据结构排序
    	public static String sort(int[] datas){
    		IntegerArray ia=new IntegerArray(datas.length);
    		ia.set(0, datas[0]);
    		boolean temp;
    		for(int i=1;i<datas.length;i++){
    			temp=false;
    			for(int j=0;j<ia.length;j++){
    				if(datas[i]<ia.get(j)){
    					ia.insert(j, datas[i]);
    					temp=true;
    					break;
    				}
    			}
    			if(!temp){
    				ia.set(ia.length, datas[i]);
    			}
    		}
    		return ia.toString();
    	}
    	
    	//普通直接插入排序
    	public static String sortRe(int[] datas){
    		int[] newDatas=new int[datas.length];
    		newDatas[0]=datas[0];
    		boolean temp;
    		for(int i=1;i<datas.length;i++){
    			temp=false;
    			for(int j=0;j<newDatas.length;j++){
    				if(datas[i]<newDatas[j]){
    					//将datas[i]插入到newDatas[j]处
    					insert(datas[i],newDatas,j);
    					temp=true;
    					break;
    				}
    			}
    			if(!temp){
    				newDatas[i]=datas[i];
    			}
    		}
    		
    		return print(newDatas);
    	}
    	
    	private static String print(int[] newDatas) {
    		StringBuffer sb=new StringBuffer();
    		for (int data : newDatas) {
    			sb.append(String.valueOf(data)+" ");
    		}
    		return sb.toString();
    	}
    	
    	private static void insert(int data, int[] newDatas, int j) {
    		int[] myDatas=new int[newDatas.length];
    		//复制数组newDatas
    		for(int i=0;i<newDatas.length;i++){
    			myDatas[i]=newDatas[i];
    		}
    		
    		newDatas[j]=data;
    		j++;
    		for(;j<newDatas.length;j++){
    			newDatas[j]=myDatas[j-1];
    		}
    	}
    	
    	
    }

### 三、结果分析　 ###

1.普通实现时间２１;自定义数据结构时间３２；

２.自定义数据结构怎么耗时还长了呢，我们自己设计数据结构不就是为了减少时间复杂度嘛。

３.先看一下自定义数据结构是怎么减少时间复杂度的。

首先在普通实现中，有两层循环，内存循环是遍历已排序好的数据，但是ｉｎｔ\[\]初始化时每个数据都默认为0。

所以这会造成，如果一个未排序数据在已排序的数据中找不到比自己大的。那意味着内层循环将遍历这个数组。

其实，我们不需要遍历整个数组，只需要比较数组中实际元素的个数就行，没有手动赋过值的下标不需要遍历。以此来减少时间复杂度。

由于字符串数组初始化默认为null；所以可以通过是否为ｎｕｌｌ来判断该下标是否被赋值过。

虽然这样可以获取到数组中实际元素的个数，但是有一个弊端就是，每一次ｉｎｔ数据都得转化为Ｓｔｒｉｎｇ类型。

Ｓｔｒｉｎｇ类型又得转换回去。

所以时间复杂度按理来说应该是减少的，可偏偏耗时还多了，应该其中一部分时间就花在类型转换中。