![[C++]数据结构-排序:插入排序之直接插入排序 [C++]数据结构-排序:插入排序之直接插入排序](https://image.shishitao.com:8440/aHR0cHM6Ly9ia3FzaW1nLmlrYWZhbi5jb20vdXBsb2FkL2NoYXRncHQtcy5wbmc%2FIQ%3D%3D.png?!?w=700&webp=1)
得赶紧休息了,木有时间写原理了。直接上代码。
/* <插入排序-直接插入排序> */
#include<iostream>
using namespace std; void print(int *nodes, int length){
for(int i=0;i<length;i++){ //notice: No equal sign in middle condition, otherwise the last node will be error
printf("%d\t", nodes[i]);
}
printf("\n");
} void InsertSort(int *nodes,int length){
for(int i=2;i<length;i++){
if(nodes[i] < nodes[i-1]){//default:ascending order
nodes[0] = nodes[i]; //set nodes[0] as a sentry or flag
int j;
for(j=i-1;nodes[0] < nodes[j];j--){
nodes[j+1] = nodes[j];
}
nodes[j+1] = nodes[0];
}
}
} /* 直接插入排序(Insertion Sorting)
[1] init thought:
foreach:nodes[2...n] as nodes(i)
set 哨兵nodes(0) = nodes(i);
foreach:nodes[i-1...n] as nodes(j)
if nodes(j).key <= nodes(0).key
nodes(j+1) = nodes(j);
else
break;
nodes[j+1] = nodes[0];
*/
int main(){
int nodes[11] = {0,1,3,64,5,57,33,32,53,7509,6578}; print(nodes,11);
InsertSort(nodes,11);
print(nodes,11); return 0;
}
output