TVP

# 算法与数据结构大系列 - NO.1 - 插入排序

mySoul

4300

## 算法

``````Step 1 − If it is the first element, it is already sorted. return 1;
Step 2 − Pick next element
Step 3 − Compare with all elements in the sorted sub-list
Step 4 − Shift all the elements in the sorted sub-list that is greater than the
value to be sorted
Step 5 − Insert the value
Step 6 − Repeat until list is sorted``````

## 伪代码

``````procedure insertionSort( A : array of items )
int holePosition
int valueToInsert
for i = 1 to length(A) inclusive do:
/* select value to be inserted */
valueToInsert = A[i]
holePosition = i
/*locate hole position for the element to be inserted */
while holePosition > 0 and A[holePosition-1] > valueToInsert do:
A[holePosition] = A[holePosition-1]
holePosition = holePosition -1
end while
/* insert the number at hole position */
A[holePosition] = valueToInsert
end for
end procedure``````

## C代码

``````#include <stdio.h>
#include <stdbool.h>
#define MAX 7
int intArray[MAX] = {4,6,3,2,1,9,7};
void printline(int count) {
int i;
for(i = 0;i < count-1;i++) {
printf("=");
}
printf("=
");
}
void display() {
int i;
printf("[");
// navigate through all items
for(i = 0;i < MAX;i++) {
printf("%d ",intArray[i]);
}
printf("]
");
}
void insertionSort() {
int valueToInsert;
int holePosition;
int i;
// loop through all numbers
for(i = 1; i < MAX; i++) {
// select a value to be inserted.
valueToInsert = intArray[i];
// select the hole position where number is to be inserted
holePosition = i;
// check if previous no. is larger than value to be inserted
while (holePosition > 0 && intArray[holePosition-1] > valueToInsert) {
intArray[holePosition] = intArray[holePosition-1];
holePosition--;
printf(" item moved : %d
" , intArray[holePosition]);
}
if(holePosition != i) {
printf(" item inserted : %d, at position : %d
" , valueToInsert,holePosition);
// insert the number at hole position
intArray[holePosition] = valueToInsert;
}
printf("Iteration %d#:",i);
display();
}
}
void main() {
printf("Input Array: ");
display();
printline(50);
insertionSort();
printf("Output Array: ");
display();
printline(50);
}``````

## 输出

``````Input Array: [4 6 3 2 1 9 7 ]
==================================================
Iteration 1#:[4 6 3 2 1 9 7 ]
item moved : 6
item moved : 4
item inserted : 3, at position : 0
Iteration 2#:[3 4 6 2 1 9 7 ]
item moved : 6
item moved : 4
item moved : 3
item inserted : 2, at position : 0
Iteration 3#:[2 3 4 6 1 9 7 ]
item moved : 6
item moved : 4
item moved : 3
item moved : 2
item inserted : 1, at position : 0
Iteration 4#:[1 2 3 4 6 9 7 ]
Iteration 5#:[1 2 3 4 6 9 7 ]
item moved : 9
item inserted : 7, at position : 5
Iteration 6#:[1 2 3 4 6 7 9 ]
Output Array: [1 2 3 4 6 7 9 ]
==================================================``````

## 总结

``````// 插入排序
public class insertSort {
public static void sort(int[] numbers){
// 其中insert为要插入的数据
int i, j , insert;
// 从数组的第二个元素开始循环数组中的元素插入
for(i = 1; i < numbers.length; i++){
// 用于保存被替换的值
insert = a[i];
// 用于保存已经排序好的列表
j = i - 1;
// 寻找剩余列表的数组，用于进行插入
while(j >= 0 && insert < a[j]){
// 把待插入的位置挪开
a[j + 1] = a[j];
j--;
}
// 进行插入
a[j + 1] = insert;
}
}
}``````

0 条评论

LV.

• 概述
• 插入排序如何工作？
• 算法
• 伪代码
• C代码
• 输出
• 总结