直接插入排序，折半插入排序和2路插入排序的算法C++语言的实现

排序的方法有很多中，其中就包括一个比较重要的插入排序，他的思路就是像摸扑克牌一样，每次新的数据插入到相对应的位置之后，在整体把数据向后移，插入数据。自己总结和测试的代码如下：(作为自己复习用)

//包含头文件
#include
using namespace std;
#include
//总结排序算法
//展示整体的数据
void ShowArray(int* a, int n)
{
    for (int i = 0; i < n; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
}

//1直接插入排序从小到大  
void InsertSort(int* a, int n)
{
    int i = 1;
    for (i = 1; i < n; i++)
    {
        int temp = a[i];//记录要插入的数据
        int j = i - 1;//j最开始指向前一个数据
        while (j>=0&&temp < a[j])//控制条件把数据整体往后移动
        {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = temp;//插入到特定位置
    }
}

//2折半插入排序算法
void BinsertSort(int* a, int n)
{
    int i = 1;
    for (i = 1; i < n; i++)
    {
        int temp = a[i];
        int low = 0, high = i-1;//定义下标最左和最右
        while (low <= high)
        {
            int mid = (low + high)/2;//中间下标
            if (a[mid] <= temp)
            {
                low = mid + 1;
            }
            else
            {
                high = mid - 1;
            }
        }
        for (int j = i; j>low; j--)//在每一次找到插入位置后进行数据整体后移动，然后插入
        {
            a[j] = a[j-1];
        }
        a[low] = temp;
    }

}

//3二路插入排序算法
void Path2InsertSort(int* a, int n)
{
    int* newarray = new int[n];//创建新数组指针
    newarray[0] = a[0];//直接赋值第一个
    int first = 0,last = 0;
    for (int i = 1; i < n; i++)//对原本数组进行一个个插入
    {
        if (a[i]>=newarray[last])//大于等于数据直接加入
        {
            last++;//因为last可以直接往后加，不会超出
            newarray[last] = a[i];
        }
        else if (a[i] < newarray[first])//小数据在后面，更小的话直接插入
        {
            first = (first - 1 + n) % n;
            newarray[first] = a[i];    
        }
        else//插入的数据在l和f之间，则要移动然后插入
        {
            int j = last;//定位最大的数的下标
            while (a[i] < newarray[j])
            {   
                //小的情况，则整体移动
                newarray[(j + 1)% n] = newarray[j];//用循环队列解决冲突，取余找出下标
                j = (j - 1 + n) % n;
            }
            newarray[(j + 1)%n] = a[i];//插入到此时需要插入的位置
            last++;
        }
    }
    for (int i = 0; i < n; i++)//first指向最小的一次赋给a[]数组
    {
        a[i] = newarray[(first+i)% n];
    }
    delete []newarray;//删除辅助循环队列（本质上是数组）
}

//4希尔排序
void ShellSort(int* a, int n)
{
	//初始化步长原本为一半的数,每次减半
	for (int step = n / 2; step > 0; step/= 2)
	{
		for (int i = 0; i < step; i++)
		{
			for (int j = i + step; j < n; j += step)
			{
				int temp = a[j];//暂存最后数据，防止被覆盖
				int k = j - step;
				while (k >= 0 && a[k] > temp)
				{
					a[k + step] = a[k];
					k -= step;
				}
				a[k + step] = temp;
			}
		}
	}
}

//5希尔排序的递归算法,重载要多加一个参数，＜n的数据作为权值
void ShellSort(int* a, int n, int step)
{
	while(step>0)
	{
		for (int i = 0; i < step; i++)
		{
			for (int j = i + step; j < n; j += step)
			{
				int temp = a[j];//暂存最后数据，防止被覆盖
				int k = j - step;
				while (k >= 0 && a[k] > temp)
				{
					a[k + step] = a[k];
					k -= step;
				}
				a[k + step] = temp;
			}	
		}
		step /= 2;
		ShellSort2(a, 10, step);
	}
}

//主函数
int main()
{
    int arr[10] = { 5,7,9,1,2,8,0,4,7,6 };
    ShowArray(arr, 10);
    //InsertSort(arr, 10);//插入排序
    //BinsertSort(arr, 10);//折半插入排序
    Path2InsertSort(arr, 10);//二路插入排序
    cout<<"排序后的数据为："<