排序算法之插入排序

已知关键字序列为｛29，75，45，17，56，45，33｝请分别用插入排序、选择排序、希尔排序、冒泡排序、快速排序对其进行排序，并写出排序过程。

插入排序概念：插入即表示将一个新的数据插入到一个有序数组中，并继续保持有序。例如有一个长度为N的无序数组，进行N-1次的插入即能完成排序；第一次，数组第1个数认为是有序的数组，将数组第二个元素插入仅有1个有序的数组中；第二次，数组前两个元素组成有序的数组，将数组第三个元素插入由两个元素构成的有序数组中......第N-1次，数组前N-1个元素组成有序的数组，将数组的第N个元素插入由N-1个元素构成的有序数组中，则完成了整个插入排序。

插入排序过程图：

插入排序代码：

public class InsertSort {

    public static void main(String[] args) {

        int[] arr = {29, 75, 45, 17, 56, 45, 33};
        InsertSort is = new InsertSort();

        is.sort(arr);

        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + "  ");
        }
    }

    // 插入排序法
    public void sort(int arr[]) {
        for (int i = 1; i < arr.length; i++) {
            int insertVal = arr[i];
            // insertValue准备和前一个数比较
            int index = i - 1;

            while (index >= 0 && insertVal < arr[index]) {
                //  将把arr[index]向后移动
                arr[index + 1] = arr[index];
                // 让index向前移动一位
                index--;
            }

            // 将insertValue插入到适当位置
            arr[index + 1] = insertVal;
        }
    }
}

算法复杂度分析见最后排序算法总结篇。