写在前面
- 楼主整理经典的排序算法
- 记录学习
1. 插入排序(InsertionSort)
1.1 概念
插入排序(InsertionSort)，一般也被称为直接插入排序。
概念解释百度百科
1.2 算法描述
- 把待排序的数组分成已排序和未排序两部分，初始的时候把第一个元素认为是已排好序的。
- 从第二个元素开始，在已排好序的子数组中寻找到该元素合适的位置并插入该位置。
- 重复上述过程直到最后一个元素被插入有序子数组中
示意图
1.3 代码演示
package com.zhuang.algorithm;
import java.util.Arrays;
/**
* @Classname InsertionSort
* @Description 插入排序
* @Date 2021/6/13 15:20
* @Created by dell
*/
public class InsertionSort {
public static void main(String[] args) {
int[] arr =new int[]{0,5,6,1,8,2};
insertionSort(arr);
System.out.println(Arrays.toString(arr));//[0, 1, 2, 5, 6, 8]
}
public static void insertionSort(int[] arr){
//第二个元素开始遍历
for (int i = 1; i < arr.length; i++) {
int value = arr[i];
int position=i;
while (arr[position-1]>value){
arr[position]=arr[position - 1];
position--;
}
arr[position]=value;
}
}
}
1.4 算法分析
- 最佳情况：T(n) = O(n)
- 最坏情况：T(n) = O(n2)
- 平均情况：T(n) = O(n2)
1.5 稳定性
由于只需要找到不大于当前数的位置而并不需要交换，因此，直接插入排序是稳定的排序方法。
1.6 适用场景
插入排序由于O( n2 )的复杂度，在数组较大的时候不适用。但是，在数据比较少的时候，是一个不错的选择，一般做为快速排序的扩充。例如，在STL的sort算法和stdlib的qsort算法中，都将插入排序作为快速排序的补充，用于少量元素的排序。又如，在JDK 7 java.util.Arrays所用的sort方法的实现中，当待排数组长度小于47时，会使用插入排序
写在最后
- 学习阶段，描述不当地方，还请大家在评论区指出
- 继续加油💪
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/140722.html
