算法基础：排序概念与插入排序

排序

root(排序)
    内部排序
        插入排序
            直接插入排序
            折半插入排序
            希尔排序
        交换排序
            冒泡排序
            快速排序
        选择排序
            简单选择排序
            堆排序
        归并排序
        基数排序
    外部排序
        多路归并排序

排序的概念

排序就是重新排列表中的元素，使表中的元素满足按关键字有序的过程。在排序的过程中，根据数据元素是否完全在内存中，可将排序排序算法分为两类，内部排序：是指在排序期间元素全部存放在内存中的排序；外部排序：是指在排序期间元素无法全部同时存放在内存中，必须在排序过程中根据要求不断的在内外存之间移动的排序。

每种排序算法都有各自的优缺点，适合在不同的环境下使用，就其全面性能而言，很难提出一种被认为是最好的算法。

插入排序

插入排序是一种简单直观的插入排序，其基本思想是每次将一个带排序的记录按照其关键字大小插入到前面已排好序的子序列，直到全部记录插入完成。

直接插入排序

最简单直观的直接插入排序就是假设从第一位开始已经排好顺序，向后的比较过程中如果出现反序的数字遍向前移动，相对的比较后的元素也逐步往后移动为新元素提供插入空间。

直接插入排序在空间上使用了常数个辅助单元，所以空间复杂度为 O(1)，而时间上需要逐个对比元素进行操作和移动元素，所以平均下来复杂度为 O(n^2^)。

因为插入元素都是从后面顺序向前进行，所以不会出现相对位置的移动，所以直接插入排序是一个稳定的排序方法，适用于顺序存储或者链式存储的线性表。

示例：Servlet demo

public void insertSort(E[] arr) {
    for (int i = 1; i < arr.length; i++) {

        E tempElement = arr[i];
        int j = i - 1;

        while (j >= 0 && tempElement.compareTo(arr[j]) < 0) {
            arr[j + 1] = arr[j];
            j--;
        }

        arr[j + 1] = tempElement;
    }
}