插入型排序
插入型排序包括：直接插入排序 折半插入排序 希尔排序 直接插入排序 时间复杂度：O(n^2) 空间复杂度：O(1) 稳定性：稳定 比较次数和移动次数与待排序序列的初始状态有关 最好情况：序列有序 比较次数：n-1次 移动次数：0 最差情况：序列逆序 比较次数：1+2+3+…+n-1次 移动次数 直接插入特性：当数组基本有序时，时间复杂度达到O(n)
void insertSort(int *a, int n) {
for (int i=1; i<n; ++i) {
int x = a[i];
int j;
for (j=i; j>0 && a[j-1]>x; --j) a[j] = a[j-1];
a[j] = x;
}
return;
}折半插入排序 时间复杂度：O(n^2) 空间复杂度：O(1) 稳定性：稳定 比较次数与初态无关，约为nlg2n次 移动次数与初态有关 折半插入排序相对于直接插入排序，减少了比较次数
void binaryInsertSort(int *a, int n) {
for (int i=1; i<n; ++i) {
int l=0, r=i-1;
while (l <= r) {
int m = (r+l)/2;
if (a[i] <= a[m]) r = m-1;
else l = m+1;
}
int x = a[i];
for (int j=i; j>l; --j) a[j] = a[j-1];
a[l] = x;
}
return;
}希尔排序 递减增量排序 时间复杂度：O(n^2) 最好约为O(n^1.3) 空间复杂度：O(1) 稳定性：不稳定
void shellSort(int *a, int n) {
int d = 1;
while (d < n/3) d = d*3 + 1;
while (d >= 1) {
for (int i=d; i<n; ++i) {
int x = a[i];
int j;
for (j=i; j>=d && a[j-d]>x; j-=d) a[j] = a[j-d];
a[j-d] = x;
}
d /= 3;
}
return;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
