直接插入排序

算法思想

每一趟将一个待排序关键字按照其值大小插入到已经排好序部分的适当位置上。
原始序列：49 38 65 97 76
第一次：49 | 38 65 97 76
第二次：38 49 | 65 97 76
第三次：38 49 65 | 97 76
第四次：38 49 65 97 | 76
第五次：38 49 65 76 97

public void insertSort(int array[]){
    int temp, i ,j;
    for (i = 1; i < array.length; i++){
        //暂存待排序关键字
        temp = array[i];
        j = i - 1;
        //扫描已排序部分并移动
        while ((j >= 0) && (temp < array[j])){
            //若待排关键字小于当前比较值，则当前值后移一位
            array[j+1] = array[j];
            j--;
        }
        //待排关键字比较完毕，插入到合适位置
        //这里是j+1，因为跳出循环时j比起上次位置多执行了一次j--；
        array[j+1] = temp;
    }
}

算法复杂度分析

时间复杂度

1. 最坏情况，整个数组是逆序的，则temp < array[j]始终成立，对于每一次外循环，内循环都执行i次，i取值为1到n-1，则总次数为n(n-1)/2，即O(n2)。
2. 最好情况，整个数组是顺序的，则temp < array[j]始终不成立，只执行外循环而不执行内循环，即O(n)。
3. 综上，平均复杂度为O(n2)。

空间复杂度
算法所需的辅助空间不随待排序列规模的变化而变化，是个常量O(1)。

折半插入排序

算法思想

采用折半查找法查找插入位置。折半查找法的一个基本条件是序列已经有序。

public void halfInsertSort(int array[]){
    int temp, low, mid, high, i, j;
    for (i = 1; i < array.length; i++){
        //暂存待排序关键字
        temp = array[i];
        //二分查找插入位置
        low = 0;
        high = i - 1;
        while (low <= high){
            mid = (low + high) / 2;
            //若待排序关键字小于中间位置值，则应寻找low-mid部分；
            //反之则寻找mid-high部分
            if (array[mid] > temp)
                high = mid - 1;
            else
                low = mid + 1;
        }
        //找到待插入位置后移动元素
        for (j = i-1; j >= high+1; j--){
            array[j+1] = array[j];
        }
        //移动结束后插入元素
        array[high+1] = temp;
    }
    }

算法复杂度分析

时间复杂度：折半插入适合关键字较多的场景，与直接插入排序相比 ，查找插入位置的时间大大减少，关键字移动次数和直接插入排序一样。折半插入排序的关键字比较次数和初始序列无关。最好情况是O(nlog2n)，最差是O(n2)，平均是O(n2)。
空间复杂度：O(1)。

希尔排序

算法思想