排序算法之 ___ 插入排序

写于: 2016年06月07日 晚

插入排序

原理

依次选择一个待排序的数据, 插入到前边已经排好序的序列中.

性能

时间复杂度为O(N^2)==(ps:即N的平方)==, 空间复杂度为O(1). 算法是稳定的, 比较次数和交换次数都与初始序列有关.

==先废话一下==: 对大小为N的无序数组R[N]进行排序, 进行N-1轮选择过程. 首先将第1个元素作为已经排序好的子数组, 然后 将剩余的N-1个元素, 逐个插入到已经排序好的子数组. 因此, 在第1轮排序时, 前i个元素总是有序的, 将第i+1个元素插入到正确的位置.

==代码来喽==

#include <stdio.h>
void insert_sort(int arr[], int len) {
     int i, j, temp;
     for(i = 1; i < len; i++) {
        if(arr[i] < arr[i-1]) {
          temp = arr[i];
          j = i;
          do {
             arr[j] = arr[j-1];
             j--;
          } 
         while(j>0 && arr[j-1] > temp);
         arr[j] = temp;
        }
     }
}
int main() {
    int arr[] = {6, 3, 8, 3, 0, 9, -3, 15, 4};
    insert_sort(arr, 10);
    for(int k = 0; k < 10; k++) {
        printf("%d ",arr[k]);
    }
}

运行结果:

优化

直接插入排序每次往前插入时, 是按顺序依次往前找, 可在这里进行优化, 往前找合适的插入位置时采用二分查找的方法, 即折半插入.

折半插入排序算法的使用是有前提的, 就是必须是有序数组. 它是指在一个有序序列中插入一个元素形成一个新的有序序列. 在有序序列中进行查找, 折半思想也是最有效的方法. 折半查找设置三个下标low、high和mid, 设置low的值为1, high为n-1, mid的值为(low+high)/2, 然后将要插入的元素与mid下标元素进行比较. 若小于mid下标元素, 那么high=mid-1, low值不变; 若大于mid下标元素,则low=mid+1, high值不变; 若等于mid那么查找成功插入之.

折半插入排序相对于直接插入排序而言: 平均性能更快, 时间复杂度降至O(NlogN), 排序是稳定的, 但排序的比较次数与初始序列无关, 总是需要foor(log(i))+1(floor函数,也请自行谷歌)次排序比较.

==优化代码 ...==

#include <stdio.h>
void halfinsert_sort(int arr[], int len) {
     int low, mid, high;
     int i, j;
     for (i = 2; i <= len; i++) {
        arr[0] = arr[i];
        low = 1;
        high = i-1;
        while(low <= high) {
              mid = (low + high)/2;
              if(arr[0] < arr[mid]) {
                high = mid-1;
             }else low = mid+1;
        }
        for(j = i-1; j >= high; j--) {
           arr[j+1] = arr[j];
        }
        arr[high+1] = arr[0];
     }
}
int main() {
    int arr[] = {0, 1, 2, 3, 4, 6, 7, 8, 9, 10 5};
    int k;
    halfinsert_sort(arr, 10);
    for(k = 1; k <= 10; k++) {
       printf("%d  ", arr[k]);
    }
    return 0;
}

运行结果:

使用场景

当数据基本有序时, 采用插入排序可以明显减少数据交换和数据移动次数, 进而提升排序效率.

                  end