一个喜欢插队的算法：直接插入排序（Java实现）

113 阅读 0 评论 75 点赞

我是靠谱客的博主等待航空，这篇文章主要介绍一个喜欢插队的算法：直接插入排序（Java实现），现在分享给大家，希望可以做个参考。

插队算法：

一、排序思路

将原有的数组看为两块，一块是有序去（排好的顺序），一块是无序区（待排序的），不断地从无序区中取出其第一个元素，搜寻该元素应该放在有序区的哪个位置，并将该元素放入该位置，完成这个步骤后，有序区长度+1，无序区长度-1，直至无序区长度为0，即无序区中不再有元素，排序就完成啦。

二、插入元素

找到合适的位置之后，我们将有序区内该位置及该位置之后的元素都往右移一位，这样就将该位置空出来了，再将插入元素插入其中。

三、举个例子

我们用图形来说明一下直接插入排序的过程，下面将对数组{8,3,2,7,4,5}进行排序：

1.首先确定有序区和无序区，由于一个元素无论如何排放都可以看做有序的，那么我们将第一个元素作为有序区，其余的作为无序区；
2.其次进行插入操作，每次插入都是选用无序区的第一个元素，如上图，确定好有序区和无序区后，即可确定即将插入的元素，即是原有数组的第二个元素 “3”，现将插入元素放入有序区，再搜寻合适位置;
3.发现插入的元素“3”比有序区中最后一个元素“8”小，所以把“3”放在元素“8”之前，比较结束之后，元素“3”之前再无元素，可以看做元素“3”之前的元素比其小，结束比较，将元素“8”往右移一位，并将元素“3”插入搜寻到的位置，第一轮插入结束，(--->{ 3 8 2 7 4 5 } ）是不是感觉很简单？我们继续往下看

简单易懂的总结 eg: 起初有序区是一组数据的第一个数，其余数划分到无序区，每次用无序区的第一个数跟有序区的最后一个数比较，如果无序区的第一个数小于有序区的最后一个数则放在有序区最后这个数的前面，否则直接跟在有序区的最后；继续遍历，直到无序区的这组数据完成后，再划分序区，第二次插入时有序区有两个数，也就是有序区的长度+1，无序区的长度-1

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 2      * 直接插入排序的方法
 3      * @param a 需要排序的数组
 4      */
 5     public void insertSort(int[] a) {
 6         //遍历除了第一个元素外的所有元素，即将初始无序区内的元素一一插入有序区
 7         for (int i = 1; i < a.length; i++) {
 8             //存放插入元素
 9             int temp = a[i];
10             //定义j变量，并初始化，j变量用于插入位置的定位
11             int j = 0;
12             //搜寻插入位置
13             for (j = i - 1; j >= 0; j--) {
14                 //从有序区最后一个元素开始比较，若比较的元素比插入的元素大则比较的元素往右移一位
15                 if (temp < a[j]) {
16                     a[j + 1] = a[j];
17                 }
18                 //若比较的元素比插入元素小，结束比较
19                 if(temp > a[j]) {
20                     break;
21                 }
22             }
23             //将插入元素插入到搜寻到的合适位置
24             a[j + 1] = temp;
25             //查看每一步插入的情况
26             System.out.println(Arrays.toString(a));
27         }
28     }