插入排序之折半插入排序（c++实现）

插入排序有直接插入排序，折半插入排序（又叫二分插入排序），链表插入排序，希尔排序等。在排序中属于稳定排序类型。

折半插入排序的算法思想： （1）计算 0 ~ i-1 的中间点，用 i 索引处的元素与中间值进行比较，如果 i 索引处的元素大，说明要插入的这个元素应该在中间值和刚加入i索引之间，反之，就是在刚开始的位置 到中间值的位置，这样很简单的完成了折半； （2）在相应的半个范围里面找插入的位置时，不断的用（1）步骤缩小范围，不停的折半，范围依次缩小为 1/2 1/4 1/8 …快速的确定出第 i 个元素要插在什么地方； （3）确定位置之后，将整个序列后移，并将元素插入到相应位置。 / 话不多说，直接品代码。

#include <iostream> int * myArray2; int pointer; void insert(int num) { myArray2[pointer] = num; int tempPointer = pointer; tempPointer /= 2; auto bigPointer = pointer; while(tempPointer>=1) { if(myArray2[bigPointer]<myArray2[tempPointer]) { int temp = myArray2[bigPointer]; myArray2[bigPointer] = myArray2[tempPointer]; myArray2[tempPointer] = temp; } bigPointer = tempPointer; tempPointer /= 2; } pointer++; } int main() { pointer = 1; int n; std::cin >> n; myArray2 = (int *)malloc(4*(n+1)); int temp; for(auto i=1;i<n+1;i++) { std::cin >> temp; insert(temp); } //输出 for(auto i=1;i<n+1;i++) { std::cout << myArray2[i]<<" "; } //释放空间 delete[] myArray2; return 0; }

使用了内存动态分配指针数组，结束自动释放空间。 /

做一位为IT无私奉献的耕耘者。 smile