[数据结构与算法]减治法应用在插入排序算法

问题描述

采用减治法进行插入排序
减治法是将问题分割成子问题，子问题的解跟原问题存在某种关系,（划分为有序区和无序区）

1. 初始时，将第0个位置设置为哨兵（防止越界）
2. 划分有序区和无序区，第1个位置为有序区，其余为无序区
3. 从第二个位置开始，在有序区中查找位置插入
4. 如图
   

算法实现

// # 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;
}