插入排序(Insertion sort)
1. 概要说明
插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. The array is split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.
- insertion /ɪnˈsɜːʃn/ 插入
- sort /sɔːt/ 排序
- algorithm /ˈælɡərɪðəm/ 算法
- split /splɪt/ 分割（不规则动词）
2. 图示过程
3. 动图演示
4. 练习1
问题：以下程序执行后，数组中的元素是什么顺序？
#include <iostream>
using namespace std;
//sorted_right_index：目前已经排好序的数组的最大的下标。
//value: 待插入的元素。
void insert(int arr[], int sorted_right_index, int value)
{
int pos = sorted_right_index;
while (pos >= 0 && arr[pos] > value)
{
arr[pos + 1] = arr[pos];
pos--;
}
arr[pos + 1] = value;
}
int main()
{
int arr[8] = {3, 5, 7, 11, 13, 2, 9, 6};
//前5(4+1)个元素已经排好，待插入元素2
insert(arr, 4, 2);
return 0;
}
2、
【NOIP 2018 普及组初赛 q08】以下排序算法中，不需要进行关键字比较操作的算法是（ ）。
A. 基数排序 B. 冒泡排序
C. 堆排序 D. 直接插入排序
5. C++实现插入排序
#include <iostream>
using namespace std;
void insertion_sort(int arr[], int len)
{
for (int i = 1; i < len; i++)
{
int key = arr[i];
int j = i - 1;
while ((j >= 0) && (key < arr[j]))
{
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
int main()
{
int arr[8] = {3, 5, 7, 11, 13, 2, 9, 6};
insertion_sort(arr, 8);
for (int i = 0; i < 8; i++)
{
cout << arr[i] << " ";
}
return 0;
}