排序:插入排序

16uni 2021年04月17日 828次浏览

插入排序: 插入排序的基本思想为是

  1. 将第一个元素标记为已排序
  2. 遍历每个没有排序过的元素,“提取” 元素 X
  3. i = 最后排序过元素的指数 到 0 的遍历
  4. 如果现在排序过的元素 > 提取的元素,将排序过的元素向右移一格
  5. 否则:插入提取的元素
    选择排序的时间复杂度最差O(n²)最优O(n) 。稳定性:稳定

插入排序.gif

举个例子

public static void main(String[] args){
    int[] ins = {6,9,5,13,15,4,5,8,3,3};
    for(int i = 1; i < ins.length; i++){
        for(int j=i; j>0; j--){
	    if(ins[j]<ins[j-1]){
	        int temp = ins[j-1];
	        ins[j-1] = ins[j];
	        ins[j] = temp;
	    }
        }
    }
    for(int in: ins){
	System.out.print(in);
    }
}