java排序算法——插入排序

     有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。

     插入排序的基本思想是：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。

                                                                                                                            来源（百度百科）

       实现思路如下：
              1，从第一个元素开始，该元素默认已经被排序；
              2，取出下一个元素，在已经排序的元素序列中从后向前扫描；
              3，如果该元素已排序或大于新元素，将该元素移到下一位置；
              4，直到找到已排序的元素小于或者等于新元素的位置；
              5，将新元素插入到该位置；
              6，重复2~5步骤
        
                                                                时间复杂度为 O(n^2) 
                                                                    (稳定)

     实现代码

public static int[]  InsertionSort(int[] array){

	if(array.length == 0){

		return array;

	}

	int current;

	for(int i = 0;i < array.length -1;i++){

        //定义基准值
		current = array[i+1];

        //当前循环遍历的索引
		int preIndex = i;
        
		//当前基准值如果小于当前索引的值
		while(preIndex > 0 && current < array[preIndex]){
            
			//当前索引与（未排序）基准值交换位置
			array[preIndex + 1]  = array[preIndex];

            //当前索引向左遍历。重复while循环，直到不满足while条件
			preIndex--;

		}
	
        //基准值与当前索引的值交换位置（确定当前基准值的位置）
		array[preIndex + 1] = current;			

	}

	return array;

}

 如有兴趣可以关注我的公众号：