插入排序的实现与分析

本是古典何须时尚 2022-05-11 11:40 140阅读 0赞

让你对一副杂乱无序的扑克牌进行排序，最常用的方法就是插入排序了。

插入排序的原理很简单，在杂乱的牌中选出一张牌，然后把它插入到应有的位置，假设是从左到右依次递减的。以斗地主的规则为例，现在你手上的牌有\{3, 2, J, K, A\}，那么“2”就应该插在“3”前面，变成\{ **2**, 3, J, K, A\}，然后\{2, **J**, 3, K, A\} \{2, **K**, J, 3, A\} \{2, **A**, K, J, 3\}。

看个例子：

*************************
    插入前:1 7 5 4 6 -3 8 
    待插入元素a[0]=1, 插入位置:0
    插入后:1 7 5 4 6 -3 8 
    *************************
    插入前:1 7 5 4 6 -3 8 
    待插入元素a[1]=7, 插入位置:1
    插入后:1 7 5 4 6 -3 8 
    *************************
    插入前:1 7 5 4 6 -3 8 
    待插入元素a[2]=5, 插入位置:1
    插入后:1 5 7 4 6 -3 8 
    *************************
    插入前:1 5 7 4 6 -3 8 
    待插入元素a[3]=4, 插入位置:1
    插入后:1 4 5 7 6 -3 8 
    *************************
    插入前:1 4 5 7 6 -3 8 
    待插入元素a[4]=6, 插入位置:3
    插入后:1 4 5 6 7 -3 8 
    *************************
    插入前:1 4 5 6 7 -3 8 
    待插入元素a[5]=-3, 插入位置:0
    插入后:-3 1 4 5 6 7 8 
    *************************
    插入前:-3 1 4 5 6 7 8 
    待插入元素a[6]=8, 插入位置:6
    插入后:-3 1 4 5 6 7 8 
    *************************

附上代码：

public class insert_sort {
    	public static void sort(int[] a){
    		int n=a.length;
    		for (int i=0; i<n; i++){			
    			for (int j=i; j>0&&(a[j-1]>a[j]); j--)
    				swap(a, j-1, j);//for 2
    		}//for 1
    	}
    	public static void swap(int a[], int i, int j){
    		int temp=a[i];
    		a[i]=a[j];
    		a[j]=temp;
    	}
    	public static void main(String[] args){
    		int[] a={1, 7, 5, 4, 6, -3, 8};
    		insert_sort.sort(a);
    	}
    }

算法分析：

假设数组的长度为n，每次插入操作都要移动一些元素的位置，如果要把最后一个元素恰好最小，那么就需要移动n-1个元素。这是最坏的情况，最好的情况依然是数组一开始就是有序排列的。对于随机排列的长度为N且不重复的数组，平均情况下插入排序要~(N^2)/4次比较以及~(N^2)/4次交换。最坏情况下需要~(N^2)/次比较和~(N^2)/2次交换，最好情况下需要N-1次比较和0次交换。总的来说，插入排序的时间复杂度为O(N^2)。

验证：

//C为比较次数，S为交换次数
    public static void sort(int[] a){
    		int n=a.length;
    		int C=0, S=0;
    		int i, j, k;
    		for (i=0; i<n; i++){			
    			for (j=i; j>0&&(a[j-1]>a[j]); j--, C++, S++)
    				swap(a, j-1, j);//for 2
    		}//for 1
    		System.out.println("C="+C+", S="+S);
    	}
    ********************************************
    假设N=100
    最坏情况:
    public static void main(String[] args){
    		int []a=new int[100];
    		for (int i=99; i>=0; i--)
    			a[99-i]=i;
    	    insert_sort.sort(a);
    	}
    结果：
    C=4950, S=4950, (N^2)/2=5000
    ********************************************
    最好情况:
    public static void main(String[] args){
    		int []a=new int[100];
    		for (int i=0; i<100; i++)
    			a[i]=i;
    		insert_sort.sort(a);
    	}
    结果：
    C=0（实际上比较了N-1次，因为没有动作所以没有记录）, S=0
    ********************************************
    平均情况:
    public static void main(String[] args){
    		int []a=new int[100];
    		for (int i=0; i<100; i++)
    			if (i%2==0)
    				a[i]=i;
    			else
    				a[i]=-i;
    		insert_sort.sort(a);
    	}
    结果：
    C=2500, S=2500, (N^2)/4=2500
    ********************************************

通过测试可以看到，程序与理论吻合得相当好。还可以得出一个结论：插入排序需要的交换次数和数组中倒置的数量相同，因为每次交换都改变了一组倒置的元素，当倒置的元素数量为0时就完成了排序。

实际上插入排序的性能优于选择排序，但它和冒泡排序一样，需要大量移动元素。你可以尝试用链表来完成插入排序，那样会免去移动元素的操作，但同时会付出更多空间的代价。