乐趣区

直接插入排序

间接插入排序

思维:当插入第 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;

}

}

退出移动版