插入排序

插入排序

一.什么是插入排序?

每步将一个待排序的纪录,按其数值的大小插入前面已经排序的文件中适当位置上,直到全部插入完为止,其适用于少量数据的排序

图片描述

二.java实现

public void insertion_sort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int i,j,temp;
        for (i=1; i<arr.length; i++) {
            temp = arr[i];
            for (j = i-1; j>=0 && arr[j]>temp; j--) {
                arr[j+1] = arr[j];
            }
            arr[j+1] = temp;
        }
    }

三.算法复杂度

  • 最好复杂度:序列为正序时复杂度为O(n)
  • 最好复杂度:序列为反序时复杂度为O(n^2)
  • 平均复杂度:O(n^2)

四.算法稳定性

  • 插入排序是稳定的

插入排序是在有序的序列上,一次插入一个元素。当然,刚开始这个有序的小序列只有1个元素,就是第一个元素。比较是从有序序列的末尾开始,也就是想要插入的元素和已经有序的最大者开始比起,如果比它大则直接插入在其后面,否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。所以,相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳定的。

评论

暂无评论