前言
插入排序算法任然需要O(N^2)的时间，但是一般情况下，他要比冒泡排序快一倍，比选择排序要快一点。
[图片上传失败...(image-39380d-1628999776603)]
一、插入排序
假定排序从中间开始，可以更好的理解插入排序。此时，队列左边已经排好序，在队列中间标记一个元素，在这个作为标记的元素左边已经是局部有序，（注意，局部有序在冒泡排序和选择排序中不会出现）这个被标记的元素右边是未排序的。我们需要做的是在左边有序的队列中的适当位置插入被标记的元素。这意味着左边有序的队列需要先向右移腾出空间。而被标记的元素需要出列，以提供位移空间。
<font color=#999AAA >示例：pandas 是基于NumPy 的一种工具，该工具是为了解决数据分析任务而创建的。
插入排序的代码如下：
public void insertionSort(){
int left , right;
for (right = 1;right<arr.length;right++){
int temp = arr[right];
left = right;
while (left>0&&arr[left-1] >=temp){
arr[left] = arr[left-1];
left--;
}
arr[left] = temp;
System.out.println("排序前："+ Arrays.toString(arr));
}
}
image.png
测试
public class Main {
public static void main(String[] args) {
Random random = new Random();
int[] arr = new int[10];
for (int i = 0; i < arr.length; i++) {
arr[i] = random.nextInt(100);
}
System.out.println("排序前："+Arrays.toString(arr));
InsertSort insertSort = new InsertSort(arr);
insertSort.insertionSort();
System.out.println("排序后："+Arrays.toString(arr));
}
}
结果:
排序前：[45, 92, 15, 27, 45, 18, 8, 24, 43, 56]
排序前：[45, 92, 15, 27, 45, 18, 8, 24, 43, 56]
排序前：[15, 45, 92, 27, 45, 18, 8, 24, 43, 56]
排序前：[15, 27, 45, 92, 45, 18, 8, 24, 43, 56]
排序前：[15, 27, 45, 45, 92, 18, 8, 24, 43, 56]
排序前：[15, 18, 27, 45, 45, 92, 8, 24, 43, 56]
排序前：[8, 15, 18, 27, 45, 45, 92, 24, 43, 56]
排序前：[8, 15, 18, 24, 27, 45, 45, 92, 43, 56]
排序前：[8, 15, 18, 24, 27, 43, 45, 45, 92, 56]
排序前：[8, 15, 18, 24, 27, 43, 45, 45, 56, 92]
排序后：[8, 15, 18, 24, 27, 43, 45, 45, 56, 92]
总结
在每趟结束时，在将temp位置项插入后，比right变量下标小的数据项都是局部有序的。
在第一趟中，它对多比较一次，第二趟最多比较两次，一次类推。最后一趟最多，比较N-1次。因此有
然而，因为每趟排序发现插入插入点之前，平均只有全体数据项的一半真的进行了比较，我们chuyi2得到
复制的次数大致等于比较次数，然而，一次复制与一次交换的事件耗费不同，所以相对于随机数据，这个算法比冒泡排序快一倍，比选择排序略快。
