直接插入排序算法的原理及Java版实现方式

直接插入排序基本思想是：仅有一个元素的序列总是有序的，
    因此，对 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 次。
此时有：
总比较次数 ≈ n2 /4 次
总移动次数 ≈ n2 /4 次
由此，直接插入排序的时间复杂度为O(n2 )
稳定性：稳定

最后

以上就是热心大象为你收集整理的直接插入排序算法的原理及Java版实现方式的全部内容，希望文章能够帮你解决直接插入排序算法的原理及Java版实现方式所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。