排序算法之插入类排序

插入类排序

插入类排序的思想就是通过向一个已经有序的序列中，插入一个元素，待插入元素通过某种规则找到它的合适位置。常用的三种插入排序有直接插入排序、折半插入排序和希尔排序。

直接插入排序（Straight Insertion Sort）

直接插入排序是最简单的排序算法，在已经有序的序列中，直接插入排序通过找到待插入元素合适的位置，然后直接插入到位置上就可以了。

网上的gif动图：

排序算法之插入类排序

代码：

void straightSort(int a[], int n){
    int i, j;
    int temp;
    for(i = 1; i < n; i++){
        temp = a[i];
        j = i - 1;
        while(j >= 0 && a[j] > temp){     //if temp bigger than the data in its left
           a[j + 1] = a[j];
           j--;
        }
        a[j + 1] = temp;
    }
}

int main() {
    int a[] = {1,2,3,2,5,6};
    int i = 0;
    straightSort(a, 6);
    for(i = 0; i<6; i++) {
        printf("%d ",a[i]);
    }
    return 0;
}

分析：

从代码中可以看出，内层循环遍历就是找到待插入数据的位置。所以当内层判断条件始终成立，也就是

当序列是逆序的时候，总的执行次数就是n(n-1)/2，此时的时间复杂度为排序算法之插入类排序。

当序列是正序的时候，内层判断始终不成立，此时的时间复杂度是排序算法之插入类排序。

所以综上平均时间复杂度是排序算法之插入类排序。

空间复杂度：每次只需要一个辅助空间即可，所以空间复杂度是排序算法之插入类排序。

另外，直接插入排序不能保证每趟排序后，每个关键字都能达到它的最终位置。如｛1，2，3，4，5，0｝,不到最后一次就不能保证每个元素的最终位置不变。

折半插入排序（Binary Insertion Sort）

折半插入排序也称二分插入排序。折半插入排序是对直接插入排序的改进，在直接插入排序过程中，每次将待插入数据插入前面已经有序的序列时，需要从后向前进行遍历来查找插入位置，而折半插入排序则是采用折半查找的思想来找插入位置。

网上的gif动图：

待填坑

代码：

void binarySort(int a[], int n){
    int i, j;
    int temp;
    int pos = 0;
    for(i = 1; i < n; i++){
        temp = a[i];
        j = i-1;
        pos = binarySearch(a, 0, i, temp);        //find the position to be inserted
        while(j >= pos){
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = temp;
    }

}

int binarySearch(int a[], int low, int high, int data){
    int i, j, center, pos;
    i = low;
    j = high;
    if(low <= high){
        pos = (i + j) / 2;          // get the integer part
        center = a[pos];
        if(data > center){
            binarySearch(a, pos+1, j, data);
        }else{
            binarySearch(a, i, pos-1, data);
        }
    }else{
        return i;
    }
}
int main() {
    int a[] = {1,2,3,2,5,6};
    int i;
    binarySort(a, 6);
    for(i = 0; i<6;i++){
        printf("%d ", a[i]);
    }
}

分析：

从代码中可以看出，折半插入只是在直接插入排序中加入了一个二分查找来查找待插入的位置。相比于直接插入排序，折半排序在查找上花费的时间大大减少，但是在移动元素进行插入的过程中，移动次数和直接插入排序是一样的。折半插入排序的比较次数和初始序列无关，都是以low>high时结束，但是移动次数需要考虑初始序列的状态。

时间复杂度：最好情况是排序算法之插入类排序，也就是初始状态是正序的时候，