原理:
就是从未排序数组中依次取出元素来和已排好序数组依次进行大小比较(从后往前比较)。如果新取出来的数比已排好序数组的最后一个元素大,则插入后面即可,如果比它小,再把这个新取出来的数和前一个数进行比较,直到找到合适的位置,插入即可(注意:在从后往前依次进行比较的时候,把比它大的数依次往后移动)。 ![动态图显示]https://www.runoob.com/wp-content/uploads/2019/03/insertionSort.gif)
程序实现(Python):
def
insertionSort(arr
):
for i
in range(1, len(arr
)):
key
= arr
[i
]
j
= i
- 1
while j
>= 0 and key
< arr
[j
]:
arr
[j
+ 1] = arr
[j
]
j
-= 1
arr
[j
+ 1] = key
a
= [12, 11, 13, 5, 6]
insertionSort(a
)
print("排序后的数组为:")
for i
in range(len(a
)):
print("{0}".format(a
[i
]), end
=' ')
程序实现(C++):
#include
<iostream
>
#include
<iomanip
>
const int
N = 10;
using namespace std
;
void input(int
* p1
, int n
)
{
int
* ptr
= p1
+ n
;
for (; p1
< ptr
; p1
++)
cin
>> *p1
;
}
void output(int
* p2
, int n
)
{
int
* ptr
= p2
+ n
;
for (; p2
< ptr
; p2
++)
cout
<< setw(6) << *p2
;
cout
<< endl
;
}
void insertSort(int
* p3
, int n
)
{
int
* p
, * q
, * ptr
, temp
;
ptr
= p3
+ n
;
for(p
=p3
+1;p
<ptr
;p
++)
if (*p
< *(p
- 1))
{
temp
= *p
;
*p
= *(p
- 1);
for (q
= p
- 2; q
>= p3
&& temp
< *q
; q
--)
*(q
+ 1) = *q
;
*(q
+ 1) = temp
;
}
}
int
main()
{
int a
[N];
cout
<< "输入" << N << "个整数:" << endl
;
input(a
, N);
cout
<< "排序前数组元素的值:" << endl
;
output(a
, N);
insertSort(a
, N);
cout
<< "排序后数组元素的值:" << endl
;
output(a
, N);
return 0;
}
转载请注明原文地址:https://ipadbbs.8miu.com/read-11270.html