插入排序（Insertion Sort）
C++自学精简教程 目录(必读)
插入排序
每次选择未排序子数组中的第一个元素，从后往前，插入放到已排序子数组中，保持子数组有序。
打扑克牌，起牌。
输入数据
42 20 17 13 28 14 23 15
执行过程
完整代码
#include <iostream>
#include <cassert>
#include <vector>
using namespace std;void print_array(const char* msg, int* arr, int n)
{cout << msg << " ";for (int i = 0; i < n; i++){cout << arr[i] << " ";}cout << endl;
}
//swap two number
void Swap(int& a, int& b)
{int tmp = a; a = b; b = tmp;
}//将newValue插入到子数组arr中，arr的长度为length
void Insert(int* arr, int newValueindex, int newValue)
{// newValueindex=1 {arr[0]} <== arr[1] // newValueindex=2 {arr[0], arr[1]} <== arr[2]// ......// newValueindex=n-1 {arr[0], arr[1],... arr[n-2]} <== arr[n-1]// [a, b, c, d] e// 0 j length int j = newValueindex - 1;for (; j >= 0; j--){if (arr[j] > newValue){//move arr[j] to the next position,for newVaulearr[j + 1] = arr[j];}else{break;//break 发生时， j 的值可能是 0}}//发生了移动，j会停止在最后一个需要被移动的位置的前面一个位置if (j != newValueindex - 1){arr[j+1] = newValue;}
}void InsertSort(int* arr, int n)
{if (n <= 1){return;}//将下标为1的元素插入到{arr[0]}中//将下标为2的元素插入到{arr[0], arr[1]}中//......//将下标为n-1的元素插入到{arr[0], arr[1], arr[n-2]}中for (int i = 1; i < n; i++) {//将未排序序列中的第一个元素插入到已排序的序列中Insert(arr, i, arr[i]);//insert first element in unsorted list to the sorted listprint_array("one trip", arr, n);}
}void test(vector<int> arr)
{//输出原始序列print_array("original array:", arr.data(), arr.size());//执行排序,并输出排序过程InsertSort(arr.data(), arr.size());//输出排序后的列表print_array("after sorted:",arr.data(), arr.size());cout << endl;
}int main()
{test({ 1 });test({ 1 , 2 });test({ 2 , 1 });test( { 2 , 2 });test({ 42, 20, 17, 13, 28, 14, 23, 15 });test({ 1, 8, 3, 6, 5, 4, 7, 2 , 9 });test( { 8, 8, 6, 6, 7, 5, 5, 7, 9 , 9});return 0;
}
执行结果
original array: 1
after sorted: 1original array: 1 2
one trip 1 2
after sorted: 1 2original array: 2 1
one trip 1 2
after sorted: 1 2original array: 2 2
one trip 2 2
after sorted: 2 2original array: 42 20 17 13 28 14 23 15
one trip 20 42 17 13 28 14 23 15
one trip 17 20 42 13 28 14 23 15
one trip 13 17 20 42 28 14 23 15
one trip 13 17 20 28 42 14 23 15
one trip 13 14 17 20 28 42 23 15
one trip 13 14 17 20 23 28 42 15
one trip 13 14 15 17 20 23 28 42
after sorted: 13 14 15 17 20 23 28 42original array: 1 8 3 6 5 4 7 2 9
one trip 1 8 3 6 5 4 7 2 9
one trip 1 3 8 6 5 4 7 2 9
one trip 1 3 6 8 5 4 7 2 9
one trip 1 3 5 6 8 4 7 2 9
one trip 1 3 4 5 6 8 7 2 9
one trip 1 3 4 5 6 7 8 2 9
one trip 1 2 3 4 5 6 7 8 9
one trip 1 2 3 4 5 6 7 8 9
after sorted: 1 2 3 4 5 6 7 8 9original array: 8 8 6 6 7 5 5 7 9 9
one trip 8 8 6 6 7 5 5 7 9 9
one trip 6 8 8 6 7 5 5 7 9 9
one trip 6 6 8 8 7 5 5 7 9 9
one trip 6 6 7 8 8 5 5 7 9 9
one trip 5 6 6 7 8 8 5 7 9 9
one trip 5 5 6 6 7 8 8 7 9 9
one trip 5 5 6 6 7 7 8 8 9 9
one trip 5 5 6 6 7 7 8 8 9 9
one trip 5 5 6 6 7 7 8 8 9 9
after sorted: 5 5 6 6 7 7 8 8 9 9