排序算法——插入排序（排序算法十大经典方法）

大家好，今天弓长给大家带来的是排序算法中的插入算法。

插入算法也是我们常见的排序算法之一，我们小时候应该有排过队吧 ，就是那种老师指挥着然后叫一个人过去，再叫一个人过去，最后排成一个小个打头的队伍出来。而我们的插入排序算法就是利用了这种思想方法进行的一种排序算法。

在排序算法中我们认为第一个数字为有序的，第二位与第一位进行对比，如果小，则向前一移动，如果大，则未遂其后，类似于同时有了两个数列，一个为有序的，一个为无序的。我们要做的就是将无序数列中的数字，一个个的拿出来，通过和有序数列中的数字进行对比，插入到自身合适的位置。

举例说明：假设一组数字 11,5,13,22,17,6

那么我们第一轮 默认11为有序的，拿出5与11对比，发现 11>5, 那么将5插入到11前方，得到 5，11 | 13，22，17，6。 这里我们可以看到，|前的为有序的 5，11 |后的剩余的无序数列。

我们接着进行第二轮：拿出13，与 有序数列中的数字对比，发现 13比最大的11还大 则尾随其后 得到 3，11，13 | 22 ，17 ，6。

第三轮，我们拿出22与有序数列对比，同样 22>13,继续尾随 得到 3，11，13，22 | 17，6。

第四轮，我们拿出17 与有序数列对比，17<22, 那么接着对比，17>13,那么 17插入到13和22之间，得到了

3，11，13，17，22 | 6。

第五轮，我们拿到最后的6进行对比，最后得到 6<11,并且 6>3 ,那么将6插入3和11之间。

到这里我们的排序已经完成，就得到了我们的最终有序数列。

代码实现：

    public void sort() {
		int[] arr = {11,5,13,22,17,6};
		int x = 0; //用于存放对比数据
		int index = 0; //用于存放有序下标
		System.out.println("插入排序开始");
		for(int i=1;i<arr.length;i++) {
			x=arr[i];
			index = i-1;
			while(index>=0 && arr[index]>x) {  //循环控制，当对比数据比有序数列最大值小时，数列向后移动一位直至对比数大于数列中某位数字
				  arr[index+1] = arr[index];
				  index--;
			}
			arr[index+1] = x;  //跟在比其小的数字后。
			
		
			System.out.println("第"+i+"轮排序："+Arrays.toString(arr)+"    插入位置："+(index+1) );
		}
	}

今天的插入排序就到这里，感谢阅读