排序——插入排序

• 数据分为已有序和待排序两部分，排序过程就是逐渐将待排序的数据插入到已有序序列中，直接插入的过程是在有序序列中从后向前寻找插入位置

//可使用哨兵优化，将arr[0]作为哨兵，但数组存储只能用1-n
void insertDirect(int* arr,int len) {
    int i,j,temp;
    for (i = 1; i < len; i++) {
        temp = arr[i];
        for (j = i; j > 0 && arr[j-1] > temp; j--) {	
            arr[j] = arr[j-1];
        }
        arr[j] = temp;		
    }
}

• 稳定的
• 只使用了常数个额外变量，空间复杂度为O(1)
• 当序列基本有序时，有最好时间复杂度O(n)
• 当序列基本逆序时，有最坏时间复杂度O(n²)
• 比较次数和移动次数都是O(n²)，平均时间复杂度为O(n²)

• 数据分为已有序和待排序两部分，排序过程就是逐渐将待排序的数据插入到已有序序列中，二分插入的过程是在有序序列中二分查找大于待插入数据的第一个元素的位置，然后移动元素

void binaryInsert(int* arr,int len) {
    int i,j,temp,left,right,mid;
    for (i = 1; i < len; i++) {
        temp = arr[i];
        left = 0; right = i-1;
        while (left <= right) {
            mid = left + (right - left)/2;
            if (arr[mid] <= temp) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        for (j = i; j > left; j--) {
            arr[j] = arr[j-1];
        }
        arr[left] = temp;
    }
}

• 稳定的
• 只使用了常数个额外变量，空间复杂度为O(1)
• 当序列基本有序时，有最好时间复杂度O(n)
• 当序列基本逆序时，有最坏时间复杂度O(n²)
• 比较次数是O(nlogn)，移动次数是O(n²)，平均时间复杂度为O(n²)

• 我们知道插入排序在数据基本有序的情况下，时间复杂度能达到O(n)，希尔排序就是将数据逐步有序直到最终有序的过程。希尔排序根据增量序列将数据分组，在组内进行插入排序，当增量为1时，就相当于直接插入排序

void shellSort(int* arr,int len) {
    int interval = len>>1;
    int i,j,temp;
    while (interval > 0) {
        for (i = interval; i < len; i++) {
            temp = arr[i];
            for (j = i; j > interval-1 && arr[j-interval] > temp; j -= interval) {
                arr[j] = arr[j-interval];
            }
            arr[j] = temp;
        }
        interval >>= 1;
    }
}

• 不稳定的
• 只使用了常数个额外变量，空间复杂度为O(1)
• 时间复杂度与选取的增量序列有关，介于 O(n^1.3) ~ O(n²)