1.什么是插入排序
- 每一步将一个待排序的数据插入到前面已经排序好的有序序列里,直到插完所有的元素为止。
- 插入排序与打扑克牌很类似,你摸到第一张牌的时候是不需要排序的,后续摸到的牌可以根据第一张牌进行向左或者向右排序。
- 算法实现
- 直接插入排序是把无序的序列里的数据插入到有序的序列中去。
- 在遍历无序序列的时候,首先拿无序序列里的第一个元素跟有序序列里的每一个元素比较,并且插入到合适的位置,一直到无序序列里的所有元素插入完毕为止。
2.插入排序算法图解
- 初始化序列如下所示,分为有序序列(没有任何元素)和无序序列(8,2,6,4,3,7,5),一开始有序序列是没有任何元素的。
第一轮用8和2比较,返现2比8小,交换位置,变成2 8
第二轮用8和6比较,交换位置,然后再用2和6比较,发现6比2大不用交换位置变成 2 6 8
第三轮用8和4比较,交换位置,再用6和4比较交换位置,2和4比较不用交换位置
第四轮8和3比较,交换位置,6和3比较交换位置,4和3比较交换位置,2和3比较不用交换位置
后面以此类推,都是向左比较到第一个元素,也就是当前元素左边都是有序的,右边都是无序的
3.插入排序代码实现
(1)整体编码实现
public class InsertSort { public static void main(String[] args) { int[] arr = {8,2,6,4,3,7,5}; System.out.println("排序前:"); System.out.println(Arrays.toString(arr)); insertSort(arr); System.out.println("排序后:"); System.out.println(Arrays.toString(arr)); } public static void insertSort(int[] arr){ //第一层循环,把数组分成两部分,左边是已将排好序的,右边是未排序的 //当前下表左边的元素已经排好序,右边还未排序 for (int i = 1; i < arr.length; i++) { //内层循环,从当前下标开始祥左比较,如果发现比左边元素小就惊醒交换 //直到比较到左边第一个元素 for (int j = i; j > 0; j--) { //依次交换,依次比较,如果不比前一个元素小,就跳出 if(arr[j-1]>arr[j]){ int temp = arr[j-1]; arr[j-1] = arr[j]; arr[j] = temp; }else{ break; } } System.out.println("第 "+i+" 轮: "+Arrays.toString(arr)); } } }
(2)代码测试