【广州校区】Java语言插入排序详解 - 黑马程序员技术交流社区

最近这段时间比较忙，几乎都忘了写博客这件事情，今天周末下着小雨，坐在桌前不知该干啥，就想起了把之前写的东西继续写下去。废话不多说，今天给大家介绍一下插入排序，直接进入主题。

插入排序思想：从第二个位置开始插入，依次与该数据之前所有数据进行比较，数据比该数据大，数据往后顺移。否则该数据插入到第一个比该数据小的数据后面。

是不是比较绕口，比较难理解？解释一下：“该数据”指的要插入的数据。下面通过图与文字来说明插入排序的思想。

同样以5个数据为例。数据为：8、5 、2 、6 、1。由于排序思想中涉及到顺移，数组顺移会覆盖数据，因此需要一个变量记录“该数据”。

第一次比较过程：

从第二位置开始插入：第二个位置的数据为5，5也就是“该数据”。

依次与该数据之前所有数据进行比较：5是第二个位置数据，也就是说5要与第一个位置上的数据进行比较。

数据比该数据大，往后顺移：数据指的是8,8比5大。8往后顺移，即8移到第二个位置。那么5也就排在第一个位置。

第二次比较过程：

第一次已经从第二位置插入了，这次就从第三个位置开始插入：第三个位置的数据为2，“该数据”指的也就是2。

2要与第二、第一位置上的数据依次比较。很明显，第二、第一位置上的数据都比2大。8和5数据都要往后顺移。比较后的数据顺序是2、5、8。

第三次比较过程：

这次从第四个位置开始插入，第四个位置数据为6，“该数据”指的也就是6。

6要与第三、第二、第一位置上的数据比较。6与第三个位置数据8比较，8往后顺移到底四个位置。6与第二个位置数据5比较，5比6要小，6就插入到第一个比6小的数据 5 的后面。至此第三次比较结束。

第四次比较过程：

这次比较从第五个位置开始插入，第五个数据为1，“该数据”指的也就是1。

1要与第四、第三、第二、第一位置上的数据进行比较。由于1在这组数据中是最小数据，因此第四、第三、第二、第一位置上的数据都往后顺移一位。1则插入到第一个位置上。

到这里整个数据的插入过程已经分析完。

我们可以看出，该数据只要找到插入位置，就不会在与插入位置之前的数据比较。因为插入数据之前的数据都比该数据小。也就是说，找到插入位置后，插入位置之前的数据已经是有序的了。

整个过程我们已经清晰明了，下面就需要对插入排序思想转换成我们的代码。

[Java] 纯文本查看 复制代码

public static void main(String[] args) {

                // 定义10个数据的数组

                int data[] = new int[10];

                // 初始化数组

                initData(data);

                // 打印排序前数组数据

                print(data);

                // 插入排序

                insertSort(data);

                // 打印排序后的数组数据

                print(data);

        }



        /**

         * 插入排序：从第二个位置开始插入，依次与该数据之前所有数据进行比较，数据比该数据大，数据往后顺移。否则该数据插入到第一个比该数据小的数据后面。

         * 

         * @param data

         */

        private static void insertSort(int[] data) {



                // 定义一个变量用于记录该数据，因为数据数据顺移会覆盖数据。

                int temp = 0;

                // 比较次数

                for (int i = 1; i < data.length; i++) {

                        // 该数据

                        temp = data;



                        //该for循环比较的是   找到第一个比该数据小的数据的位置。

                        int j = i - 1;

                        for (;j >= 0; j--) {

                                

                                //判断数据与该数据大小

                                if (data[j] > temp) {



                                        // 数据比该数据大，数据往后顺移

                                        data[j + 1] = data[j];



                                } else {



                                        // 找到了第一个比该数据小的数据的位置，j。跳出循环

                                        break;

                                }



                        }



                        // break走到这里，找到了第一个比该数据小的数据的位置，j；插入位置就是 j+1.

                        //或者内for循环结束，找到了第一个比该数据小的数据的位置，j的值为-1；插入位置就是 j+1，也就是0的位置.

                        data[j + 1] = temp;



                }

                //==============================对上面代码进行改造后是注释下面这部分代码=================================

                /*

                 *

                 * int temp = 0; 

                 * for (int i = 1; i < data.length; i++) { 

                 * // 该数据 temp = data;

                 * 

                 * int j = i - 1;

                 *  //该for循环比较的是   找到第一个比该数据小的数据的位置。

                 *  while (j >= 0) {

                 * 

                 * if (data[j] > temp) {

                 * 

                 * // 数据往后顺移

                 *  data[j + 1] = data[j];

                 * 

                 * } else {

                 * 

                 * // 找到了第一个比该数据小的数据的位置，j.

                 *  break;

                 * }

                 * 

                 * j--; }

                 * 

                 * // 走到这里，找到了第一个比该数据小的数据的位置，j；插入位置就是 j+1.

                 * 

                 * data[j + 1] = temp;

                 * 

                 * }

                 */

                //=================================================================

        }



        // 该方法随机生成10个1-100的随机数

        private static void initData(int[] data) {



                for (int i = 0; i < data.length; i++) {



                        data = (int) Math.ceil(Math.random() * 100);

                }



        }



        // 该方法用于打印数组数据

        private static void print(int[] data) {



                System.out.print("[");

                for (int i = 0; i < data.length; i++) {



                        if (i != data.length - 1) {

                                System.out.print(data + ",");

                        } else {

                                System.out.println(data + "]");

                        }

                }



        }

到这里插入排序详解完毕。

下一篇：递归思想与汉诺塔详解，敬请期待......