排序算法-插入排序

插入排序

1.直接插入排序

• 思想：每次将一个待排序的数据按照其关键字的大小插入到前面已经排序好的数据中的适当位置，直到全部数据排序完成。
• 时间复杂度：O(n^2) O(n) O(n^2) （最坏 最好 平均）
• 空间复杂度：O(1)
• 稳定性： 稳定 每次都是在前面已排好序的序列中找到适当的位置，只有小的数字会往前插入，所以原来相同的两个数字在排序后相对位置不变。

<code>// 插入排序
public static void insertSort(int[] array) {
    for (int i = 2; i < array.length; i++ ) {
        int val = array[i];
        int j = i -1;
        while (j >= 0 && array[j] > val) {  // array[j] > val
            array[j+1] = array[j];
            j--;
        }
        array[j+1] = val; //  array[j+1] 不是array[j]
    }
}
/<code>

2.希尔排序

• 思想：希尔排序根据增量值对数据按下标进行分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整体采用直接插入排序得到有序数组，算法终止。
• 时间复杂度：O(n2) O(n) O(n1.5) （最坏，最好，平均）
• 空间复杂度：O(1)
• 稳定性：不稳定 因为是分组进行直接插入排序，原来相同的两个数字可能会被分到不同的组去，可能会使得后面的数字会排到前面，使得两个相同的数字排序前后位置发生变化。
• 不稳定举例: 4 3 3 2 按2为增量分组，则第二个3会跑到前面

<code>public static void shellSort(int[] array) {
    int len;
    len = array.length / 2; // 分成n/2组
    while (len >= 1) {
        for (int i = len; i < array.length; ++i) { //对每组进行直接插入排序
            int temp = array[i];
            int j = i - len;
            while (j >= 0 && array[j] > temp) {
                array[j + len] = array[j];
                j -= len;
            }
            array[j + len] = temp;
        }
        len /= 2;
    }
}/<code>

閱讀更多 醉人Ryu 的文章

關鍵字: 算法 排序 复杂度