直接插入排序_直接插入排序

直接插入排序的算法

直接插入排序基本思想是：仅有一个元素的序列总是有序的，因此，对 n 个记录的序列，可从第二个元素开始直到第 n 个元素，逐个向有序序列中执行插入操作，从而得到 n 个元素按关键字有序的序列。

一般来说，在含有 j-1 个元素的有序序列中插入一个元素的方法是：

从 第 j-1 个元素 开始依次 向前搜索 应当插入的位置，并且在搜索插入位置的同时可以 后移元素 ，这样当找到适当的插入位置时即可直接插入元素

直接插入排序的实现

import java.util.Arrays;

public class TestInsertSort {

public static void sort( int arr []) {

// 外层循环，从第二个元素开始 , 到最后一个结束

for ( int i = 1; i <= arr . length -1; i ++){

// 如果第 i 个大于第 i-1 个，无需排序，此轮排序结束，进入下一轮

if ( arr [ i ] < arr [ i -1]){

// 从后向前比较 i-1,i-2,i-3.....1,0

int temp = arr [ i ];

int j ;

// 内循环，从 i-1 个元素开始向前比较，比较到小于 temp 的元素为止（可能首元素都大于 temp ）

// for(j = i-1;j>=0;j--){

// if( temp < arr [j]){

// arr [j+1] = arr [j];// 后移一个元素

// }else{

// break;

// }

// }

for ( j = i -1; j >=0 && temp < arr [ j ]; j --){

arr [ j +1] = arr [ j ]; // 后移一个元素

}

// 将元素插入指定位置

arr [ j +1] = temp ;

}

}

}

public static void main(String[] args ) {

int arr [] = {26, 53,48,11,13,48,32,15};

sort ( arr );

System. out .println(Arrays. toString ( arr ));

}

}

直接插入排序的分析

空间效率 ：仅使用一个辅存单元。

时间效率 ：假设待排序的元素个数为 n，则向有序表中逐个插入记录的操作进行了 n-1趟，

每趟操作分为比较关键码和移动记录，而比较的次数和移动记录的次数取决于待排序列

按关键码的初始排列。

⑴ 在最好情况下，即待排序序列已按关键字有序，每趟操作只需 1 次比较 0 次移动。此时有：

总比较次数 = n-1 次

总移动次数 = 0 次

⑵ 在最坏情况下，即待排序序列按关键字逆序排序，这时在第 j 趟操作中，为插入元

素需要同前面的 j 个元素进行 j 次关键字比较，移动元素的次数为 j+1 次。此时有：

⑶ 平均情况下：即在第 j 趟操作中，插入记录大约需要同前面的 j/2 个元素进行关键字比较，移动记录的次数为 j/2+1 次。

此时有：

总比较次数 ≈ n 2 /4 次

总移动次数 ≈ n 2 /4 次

由此，直接插入排序的时间复杂度为O(n 2 )

稳定性 ：稳定