插入排序

一、插入排序

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

　　具体算法描述如下：

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

　　效果图如下：

 

二、代码

　　该算法使用java代码实现，代码如下：

    public static void doInsertSort(int[] src)
    {
        int j, temp;
        for (int i = 1; i < src.length; i++)//循环数组的长度-1次 
        {
            j = i - 1;// j指向索引的前一个
            temp = src[i];// 把当前索引的那个数保存
            while (j >= 0 && src[j] > temp)// 如果索引的前一个比当前索引的那个大
            {
                src[j + 1] = src[j];// 索引的前一个数放到当前索引的那个位置
                j--;// 再寻找索引的前面的前面的数
            }
            // 此时前面的数比temp小，后面的数比temp大
            src[j + 1] = temp;
            System.out.println("第"+i +"趟结果如下："+Arrays.toString(src));
        }
    }

　　使用6 5 3 1 8 7 2 4排序每一趟结果如下：

第1趟结果如下：[5, 6, 3, 1, 8, 7, 2, 4]
第2趟结果如下：[3, 5, 6, 1, 8, 7, 2, 4]
第3趟结果如下：[1, 3, 5, 6, 8, 7, 2, 4]
第4趟结果如下：[1, 3, 5, 6, 8, 7, 2, 4]
第5趟结果如下：[1, 3, 5, 6, 7, 8, 2, 4]
第6趟结果如下：[1, 2, 3, 5, 6, 7, 8, 4]
第7趟结果如下：[1, 2, 3, 4, 5, 6, 7, 8]