直接插入排序（3种方法）

直接插入排序是一种最简单的排序方法，其基本 *** 作是将一条记录插入到已排好的有序表中，从而

得到一个新的、记录数量增1的有序表。

直接插入排序是一种稳定的排序方法。

//直接插入排序
void InsertSort(int* ar, int left, int right)
{
	for (int i = left + 1; i < right; i++)
	{
		ar[0] = ar[i];          //设置哨兵位
		int j = i;
		while (ar[0] < ar[j - 1])
		{
			ar[j] = ar[j - 1];
			j--;
		}
		ar[j] = ar[0];
	}
}

void InsertSort_1(int* ar, int left, int right) //从前往后比较
{
	for (int i = left + 1; i < right; i++)
	{
		int k = left;
		while (ar[i] > ar[k])   
			k++;
		int tmp = ar[i];
		for (int j = i; j > k; j--)
			ar[j] = ar[j - 1];
		ar[k] = tmp;
	}
}

void InsertSort_2(int* ar, int left, int right) //从后往前比较
{
	for (int i = left + 1; i < right; i++)
	{
		int j = i;
		if (j > left && ar[j] < ar[j - 1])
		{
			int tmp = ar[j];
			ar[j] = ar[j - 1];
			ar[j - 1] = tmp;
			j--;
		}
	}
}