Java中的七大排序_1插入排序

一：七种排序

插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序

创新互联成立10余年来，这条路我们正越走越好，积累了技术与客户资源，形成了良好的口碑。为客户提供成都网站建设、成都做网站、网站策划、网页设计、域名注册、网络营销、VI设计、网站改版、漏洞修补等服务。网站是否美观、功能强大、用户体验好、性价比高、打开快等等，这些对于网站建设都非常重要，创新互联通过对建站技术性的掌握、对创意设计的研究为客户提供一站式互联网解决方案，携手广大客户，共同发展进步。

二、排序思想（以非降序排列为例）

简单点说：将待排元素分为有序区间和无序区间，并假设第一个元素已经有序。每次取出无序区间的第一个值记作key吧，将它与有序区间的元素从后往前进行比较，大于等于有序区间最后一个数，就放后边当成新的有序区间的最后一个数；小于的话，就继续往前比较，直到找到一个比它还小的有序区间的数，并把key插入到该值的后边。
注意：我们在有序区间插入元素时，一定要提前空好位置在做插入操作，如果直接插入，会导致原来数据被覆盖而丢失。所以要先将插入位置之后的有序区间的元素从后往前依次向后移动一下，（从后往前，还是为了避免数据被覆盖）。这样操作后，就会将插入位置空出，此时，在将key插入

三、图示：以排18292415224为例

1.将元素分为有序区间和无序区间，并假设第一个元素已经有序

2.key从无序区间第一个开始有序的下一个），key=8大于等于有序区间最后一个数，就放后边当成新的有序区间的最后一个数，接着进行下一步的key值比较定位

3.key=2,小于有序区间的最后一个数8，就继续往前比较，直到找到一个比它还小的有序区间的数，在该数之后做插入

4.先将插入位置之后的有序区间的元素从后往前依次向后移动一下，腾出空位，插入key

5.key=9,key>=8,成为新有序区间的最后一个数
6.key=2, key<9, 向前遍历比较，直到找到一个小于等于2的数，在该数之后做腾位、再插入key=2


9.依次类推，最终将所有元素按非降序排号

四、代码实现

public static void insertSort2(int[] array) {//插入排序代码
for (int i = 0; i < array.length - 1; i++) {//循环的次数，也监控着每一轮开始key的位置
int key = array[i + 1];
int j;
for (j = i; j >= 0 && key < array[j]; j--) {//一边比较一边为key的插入腾空位
array[j + 1] = array[j];
}
array[j + 1] = key;
}
}