首页 > 代码库 > 插入排序(Insertion Sort)

插入排序(Insertion Sort)

一、思路

1、在长度为N的数组,将数组中第i【1~(N-1)】个元素,插入到数组【0~i】适当的位置上。

2、在排序的过程中当前元素之前的数组元素已经是有序的了。

3、在插入的过程中,有序的数组元素,需要向右移动为更小的元素腾出空间,直到为当前元素找到合适的位置。

 

二、代码实现

    public static void sort(Comparable[] a) {
        
        int N = a.length;
        
        for(int i = 1; i < N; i++) {
            for(int j = i; j > 0 && less(a[j], a[j-1]); j--) {
                exch(a, j, j-1);
            }
//            show(a);
        }
        
    }

 

三、性能分析

结论:对于随机排列长度为N且主键不重复的数组,插入排序平均需要~N2/4次比较和~N2/4次交换。

最坏情况需要~N2/2次比较和~N2/2次交换,最好情况需要N-1次比较和0次交换。

分析:

由代码可知,对外循环每个i(1,N-1):

内部循环最坏情况下做i次比较,i次交换;即(1+2+……+N-1)= N(N-1)/2  ~N2/2次交换和比较。

内部循环最好情况下做1次比较,0次交换;即N-1次比较,0次交换。

内部循环平均做i/2次比较,i/2次比较(简化处理);即~N2/4次交换和比较。

 

注:Nc = Ne + (N-1-Ninsmallest

Nc是比较的次数,Ne是交换的次数,Ninsmallest是插入的元素刚好是最小元素的个数。

 

插入排序(Insertion Sort)