插入排序

---

算法简介

  插入排序（插入分页）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

算法描述

一般来说，插入排序都采用就地在数组上实现具体算法描述如下：

1、从第一个元素开始，该元素可以认为已经被排序;
2、取出下一个元素，在已经排序的元素序列中从后向前扫描;
3、如果该元素（已排序）大于新元素，将该元素移到下一位置;
4、重复步骤3，直到找到已排序的元素小于或者等于新元素的位置;
5、将新元素插入到该位置后;
6、重复步骤2〜5，直至排序完成

动图演示

sort.gif

代码实现

import java.util.Arrays;
import java.util.Scanner;

public class InsertionSort {

    public static void main(String[] args) {
        int[] intArray = new int[5];
        int preIndex,current;
        int num = 0;
        int len = intArray.length;

        // 数组赋值
        System.out.println("请输入数组各元素的值,以空格为单位:");
        Scanner scanner = new Scanner(System.in);
        for (int i = 0; i < len; i++) {
            intArray[i] = scanner.nextInt();
        }
        System.out.print("你输入的数组为:");
        System.out.println(Arrays.toString(intArray));
        
        for(int i = 1; i< len;i++){
            preIndex = i - 1; //找到已排序的最后一个数组元素
            current = intArray[i];
            //当未达到数组的第一个元素或者待插入元素小于当前元素
            while(preIndex >= 0 && intArray[preIndex] >current){
                //就将该元素后移
                intArray[preIndex + 1] = intArray[preIndex];
                //下标减一，继续比较
                preIndex--;
            }
            //插入位置已经找到，立即插入
            intArray[preIndex + 1] = current;
            num += 1;
            System.out.printf("第%s趟排序的数组顺序为:%s",num, Arrays.toString(intArray));
            System.out.println();
            
        }
        System.out.println("排完序的数组顺序为" + Arrays.toString(intArray));
    }   
}

运行结果

请输入数组各元素的值,以空格为单位:
12 34 76 22 8
你输入的数组为:[12, 34, 76, 22, 8]
第1趟排序的数组顺序为:[12, 34, 76, 22, 8]
第2趟排序的数组顺序为:[12, 34, 76, 22, 8]
第3趟排序的数组顺序为:[12, 22, 34, 76, 8]
第4趟排序的数组顺序为:[8, 12, 22, 34, 76]
排完序的数组顺序为[8, 12, 22, 34, 76]

算法分析

  插入排序在实现上，通常采用就地排序（即只需用到O（1）的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。