插入排序

算法思想

每次排列前n个数据,将第n+1个数据插入到前n个中.在前n个数据中寻找到合适的位置并插入。

实验步骤

1. 从索引1开始,遍历每个元素

2. 遍历第n+1个元素(设为temp)时,将这个元素与前n个元素比较大小(假如为升序排列,遍历至第x个元素)

   • 如果temp<arr[x],将这个元素的值赋给arr[x+1],继续循环

   • 如果temp>=arr[x],跳出循环,继续执行步骤1;

注意点

时间复杂度:O(n^2)

空间复杂度:O(1)

稳定性:稳定

实验代码

	public static void main(String[] args) {
        int[] array={49,38,65,97,76,13,27,49,78,34,12,64,1};
        int[] ints = insertSort(array);
        for (int anInt : ints) {
            System.out.print(anInt+",");
        }
    }
    public static int[] insertSort(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            int j=i-1;
            int temp = arr[i];
            while(j>=0&&arr[j]>temp){
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = temp;
        }
        return arr;
    }