减治法利用在插入排序算法
问题形容
采纳减治法进行插入排序
减治法是将问题宰割成子问题，子问题的解跟原问题存在某种关系,（划分为有序区和无序区）
- 初始时，将第0个地位设置为哨兵（避免越界）
- 划分有序区和无序区，第1个地位为有序区，其余为无序区
- 从第二个地位开始，在有序区中查找地位插入
- 如图,取无序区的第一个，遍历有序去，而后将值插入有序区即可，解决完一个，有序去多一个，无序区少一个，晓得处理完毕
算法实现
// # 1. 减治法排序之插入排序// # 2. 初始时，将第0个地位设置为哨兵（避免越界）// # 3. 划分有序区和无序区，第1个地位为有序区，其余为无序区// # 4. 从第二个地位开始，取无序区的第一个，遍历有序去，而后将值插入有序区即可#include<iostream>using namespace std; void sort(int arr[], int len) { for (int i = 2; i < len; i++) { arr[0] = arr[i]; // 以后解决的值 int j = i - 1; // 设置解决地位 cout<<"解决之"<<arr[i]<<"地位"<<j<<endl; for (; arr[j]>arr[0]; j--) { // 比拟，值大于待排序值arr[0]的间接后移一位，直到arr[0]>arr[j] arr[j + 1] = arr[j]; // 后移 } arr[j + 1] = arr[0]; // 插入值 }}void show(int arr[], int len) { for (int i = 0; i < len; i++) { cout<<arr[i]<<" "; } cout<<endl;}int main() { int arr[7] = {0, 12, 15, 9, 20, 10, 6}; sort(arr, 7); show(arr, 7); return 0;}