关于后端:减治法应用在插入排序算法

减治法利用在插入排序算法

问题形容

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

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