共计 825 个字符,预计需要花费 3 分钟才能阅读完成。
间接插入排序
思维:当插入第 i 个元素时,后面的 i - 1 个元素曾经排好序,这时,用第 i 个元素和后面的 i - 1 个元素进行比拟,找到第 i 个元素的地位将其插入,原来地位上的元素向后顺移。
例子:
初始序列:21 25 49 25* 16 8
1 21 25 49 25* 16 8
2 21 25 49 25* 16 8
3 21 25 25* 49 16 8
4 16 21 25 25* 49 8
5 8 16 21 25 25* 49
i= 4 时间接插入排序的过程:
初始:21 25 25* 49 16 8 temp
21 25 25* 49 16 8 16
21 25 25* 49 49 8 16
21 25 25* 25* 49 8 16
21 25 25 25* 49 8 16
21 21 25 25* 49 8 16
16 21 25 25* 49 8 16
在这趟排序中,咱们能够看到 V[0] 到 V[3] 曾经排好序了,在要插入 V[4]=16 这个数时,咱们须要比拟 V[4] 与 V[3],因为 V[4]<V[3],须要在 V[3] 到 V[0] 之间寻找插入地位,先将 V[4]=16 找一个工作元素 temp 中暂存,以避免后面的元素把他笼罩掉。而后从前面向前顺次比拟寻找插入地位,循环变量设为 j,如果 V[j]>temp, 那么就将 V[j] 后移,直到某一个 V[j]<=temp 时或者元素序列比拟完为止。最初把暂存的 temp 的值填到第 j 个地位的后一个地位,一趟排序就完结了。
稳定性:稳固
工夫复杂度:O(n^2)
代码:
c++:
void Insert_sort(int arr[],int n) {
int i;
int j;
int temp;
for (i = 1; i < n;i++) {
temp = arr[i];
for (j = i – 1; j >= 0;j–) {
if (temp<arr[j]) {
arr[j + 1] = arr[j];// 后移比 temp 大的值
}
else
{
break;// 不须要挪动
}
}
arr[j + 1] = temp;
}
}