转载

数据结构之插入排序--直接插入排序

排序思路：每次将一个待排序的元素与已排序的元素进行逐一比较，直到找到合适的位置按大小插入。

第一趟比较示图：

数据结构之插入排序--直接插入排序

算法实现：

public static void insertsort(int arr[]){       for(int i = 1;i < arr.length; i ++){    if(arr[i] < arr[i-1]){//注意[0,i-1]都是有序的。如果待插入元素比arr[i-1]还大则无需再与[i-1]前面的元素进行比较了，反之则进入if语句     int temp = arr[i];     int j;     for(j = i-1; j >= 0 && arr[j] > temp; j --){           arr[j+1] = arr[j];//把比temp大的元素全部往后移动一个位置        }     arr[j+1] = temp;//把待排序的元素temp插入腾出位置的(j+1)    }      }  }  public static void main(String[] args) {   int array[] = {4,2,1,5};   System.out.println("排序之前：");   for(int element : array){    System.out.print(element+" ");   }   insertsort(array);   System.out.println("/n排序之后：");     for(int element : array){    System.out.print(element+" ");   }  } }

结果：

排序之前：   4 2 1 5  排序之后： 1 2 4 5

算法分析：1.当元素的初始序列为正序时，仅外循环要进行n-1趟排序且每一趟只进行一次比较，没有进入if语句不存在元素之间的交换(移动)。此时比较次数(C _min )和移动次数(M _min )达到最小值。

C _min = n-1 M _min = 0;

此时时间复杂度为O(n)。

2.当元素的初始序列为反序时，每趟排序中待插入的元素都要和[0,i-1]中的i个元素进行比较且要将这i个元素后移(arr[j+1] = arr[j])，i个元素后移移动次数当然也就为i 了，再加上temp = arr[i]与arr[j+1] = temp的两次移动，每趟移动的次数为i+2,此时比较次数(C _min )和移动次数(M _min )达到最小值。

C _max = 1+2+...+(n-1) = n*(n-1)/2 = O(n ² )

M _max = (1+2)+(2+2)+...+(n-1+2) = (n-1)*(n+4)/2 = O(n ² ) (i取值范围1~n-1)

此时时间复杂度为O(n ² )。

3.在直接插入排序中只使用了i,j,temp这3个辅助元素，与问题规模无关，所以空间复杂度为O(1).

4.在整个排序结束后，即使有相同元素它们的相对位置也没有发生变化，

如：5, 3 ,2, 3 排序过程如下

A-- 3 ,5,2, 3

B--2, 3 ,5, 3

C--2, 3 , 3 ,5

排序结束后两个元素3的相对位置没有发生改变，所以直接插入排序是一种稳定排序。

正文到此结束