排序算法之直接插入排序原理与实战

算法是一门很深的学问，也是程序员必学的一项技能，其中最为简单和出名的当属排序算法。算法尤其是在游戏行业，或者数据挖掘等都有广泛的应用。说道算法，就不能不说排序算法，常见的排序算法有8中，如下：

上篇我们讲了快速排序，本篇小编将带领大家学习直接插入排序。
基本思想：在要排序的一组数中，假设前面(n-1) [n>=2] 个数已经是排好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。
直接插入排序分步解析如下：

排序实现代码如下：

public class InsertSort{
    public void insertSort(int[] array){
        for(int i=1;i<array.length;i++){ //第0位独自作为有序数列，从第1位开始向后遍历
            if(array[i]<array[i-1]){ //0~i-1位为有序，若第i位小于i-1位，继续寻位并插入，否则认为0~i位也是有序的，忽略此次循环，相当于continue
                int temp=array[i];//保存第i位的值
                int k = i - 1;
                for(int j=k;j>=0 && temp<array[j];j--){ //从第i-1位向前遍历并移位，直至找到小于第i位值停止
                    array[j+1]=array[j];
                    k--;
                }
                array[k+1]=temp;//插入第i位的值
            }
        } 
    }
    public static void printArray(int[] array) {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]);
        }
    }
}

版权声明：本文为博主原创文章，未经博主允许不得转载。原文地址http://www.xttblog.com/?p=437

： » 排序算法之直接插入排序原理与实战