写于: 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