目录
🎨基本介绍
🎹算法思想
🏸实例
🎠思路分析
🪁代码实现
🛹算法性能分析
🚀时间复杂度
🛴空间复杂度
🛸稳定性
🎨基本介绍
插入式排序属于内部排序法,是对待排序的元素以插入的方式寻找该元素的适当位置,以达到排序的目的。
🎹算法思想
插入排序(Insertion Sorting)的基本思想是:把n个待排序的元素看成为一个有序表和一个无序表,开始时有序表中只包含一个元素,无序表中包含有n-1个元素,排序过程中每次从无序表中取出第一个元素,在有序表中从后往前进行比较,将它插入到有序表中的适当位置,使之成为新的有序表。
🏸实例
将101,34,119,1进行从小→大的排序
🎠思路分析
101,34,119,1
第一趟:此时有序表为101,无序表为:34,119,1
从后往前遍历有序表,将34和101进行比较,34<101,此时将101后移一个位置。此时已经遍历完有序表中的所有元素,故将34插入在101的前面,即有序表的第一个位置,得到新的有序表:34,101
34,101,119,1
第二趟:从后往前遍历有序表,将119与34和101进行比较,发现119均大于两者。故将119直接插在101后面,即有序表的最后一个位置,得到新的有序表:34,101,119
34,101,119,1
第三趟:从后往前扫描有序表,1<119,故将119往后移一个位置;1<101,将101往后移一个位置;1<34,将34往后移一个位置。此时已经遍历完有序表中的所有元素,故将1插入在34的前面,即有序表的第一个位置。
此时所有元素已经完全有序:1,34,101,119
🪁代码实现
public static void main(String[] args) {
int []arr={101,34,119,1};
insertSort(arr);
System.out.println("排序后的数组为:"+Arrays.toString(arr));
}
public static void insertSort(int[]arr){
if (arr==null||arr.length==1){
return;
}
//从第二个元素开始,和前面的有序表进行比较
for (int i=1;i<arr.length;i++){
int temp=arr[i];//记录要插入的值,将待插入的值取出并保存在temp中,防止数据移动时该元素丢失
int j=i-1;
//从后往前进行遍历比较
for (;j>=0;j--){
if (arr[j]>temp){
arr[j+1]=arr[j];//后移一个位置
}
else {
arr[j+1]=temp;//直接将待插入的元素,插入在有序表的尾部
break;
}
}
arr[j+1]=temp;//遍历完有序表所有大于temp的元素后,将temp插入
}
}
实现结果:
🛹算法性能分析
🚀时间复杂度
最坏情况:当待排序序列为逆序状态,首先遍历整个序列,之后一个一个地将待插入元素放在已排好序的序列最前面,之后的所有元素都需要向后移动一位,时间复杂度为O(n^2)
最好情况:当待排序序列为正序状态,则遍历完整个序列,当插入元素时,只比较一次就够了,所以时间复杂度为O(n)
平均情况:当被插入的元素放在已排序的序列中间位置时,为平均情况,比较和移动的时间复杂度为O(n/2),所以总的时间复杂度依然为O(n^2)
🛴空间复杂度
空间复杂度为O(1)
🛸稳定性
当待插入元素与有序序列中比较的元素相等时,将待插入元素直接插入在该相等元素的后面。所以,两个元素位置的前后顺序没有改变,故插入排序是稳定的
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)