1.插入排序

<1>.首先我们举个例子

我们要把6进行前面的插入，那我们要进行比较，首先确定一个end的指针，然后他指向的数字就是我们需要比较的，如果end指向的数比我们end+1 的大的话，那我们就往前挪一个，让end指向的数位置换到刚才end+1 的位置，也就是6的位置。然后end--，如果end指向的数比6小大，我们循环停止。如果按照我们的例子来看，那么就应该是这样的

那么我们前面的的数怎么办，他们还没有成为有序的数组，那如果我们前面一开始就是有序的，那么是不是从后面开始比较，然后停止的时候，是不是就全都是有序的。那我们如果从一开始，一点一点让他们成为有序的，一直到end指向数组最后一个数的前一个数，然后进行刚才的比较，那么全都是有序的。也就是说应该是这样的

第一次单个3就算是有序的数组，然后和五进行比较

第二次，3 5 和8进行比较然后3 5 8就是有序的

第三次，3 5 8和4 开始比较，那么按照顺序就是 3 4 5 8.。。。。依次类推，然后 我们就得到了排序

那么end就是在有序数组的最后一个，然后把end+1的位置存进tmp，如果比较成立，end的数字向后移动，覆盖end+1位置的数，当如果是逆序排列，end就会到达-1的位置，那么遍历也就结束了，这也成为了我们while的判断条件

void InsertSort(int* arr, int n)
{
	for(int i=0;i<n-1;i++)
	{ 
	 int end=i;
	 int tmp = arr[end + 1];
	 while (end >= 0)
	 {
		if (arr[end] > tmp)
		{
			arr[end + 1] = arr[end];
			end--;
		}
		else
		{
			break;
		}
		
	 }
	arr[end + 1] = tmp;
	}
}

代码就是这样写的

提醒大家的是while循环结束后，把end+1的位置放tmp，就是我们每次较完之后end，如果要进行挪动，那么end最后的位置就是空的，那么我们就要把刚才存的end+1的位置的数字tmp存进去。

2冒泡排序

冒泡排序我们在c语言里面实现过我们就不多说了

第一层循环时为了把第一个数依次向后比较，第二层控制第一层进行比较的次数，第一次，最后一个数就排好了，那么第一层循环就少了一层。

void BubbleSort(int* arr, int n)
{
	for (int i = 0; i < n-1; i++)
	{
		int exchang = 0;
		for (int j = 1; j < n - i; j++)
		{
			if (arr[j - 1] > arr[j])
			{
				Swap(&arr[j - 1], &arr[j]);
				exchang = 1;
			}
			
		}if (exchang == 0)
			{
				break;
			}
	}
}
void Swap(int* x, int* y)
{
	int t = *x;
	*x = *y;
	*y = t;
}

3.希尔排序

希尔排序时我们以插入排序为基础，比之前有点难度。、

按照之前的希尔排序在我们设立的每次依次分的有序数组，他进行规范行的分组，画图

假设我们每次规定的一个数组是间隙三个的，然后我们第一次调整蓝色的有序数组，那么第一次就是3为有序数组，然后和4 比较，接着3 4和7 比较

接着红色这组，再然后绿色的。这样遍历就可以。我们红色算一组，可以按照刚才的插入的排序写一个循环，我们怎么知道我们要循环几次，其实间隙是几，我们就循环几次。先实现一下。

int gap = 3;这个写法是进行固定一个小组进行轮换，然后在进行下一个小组
	for (int j = 0; j < gap; j++)//间隙有几个就进行几次循环
	{
		
		for (int i = 0; i < n - gap; i+=gap)i<gap这样的话最后的end不会越界
		{

			int end = i;
			int tmp = arr[end + gap];
			while (end >= 0)
			{
				if (arr[end] > tmp)
				{
					arr[end + gap] = arr[end];
				}
				else
				{
					break;
				}
			}
			arr[end+gap]=tmp;
		}
	}

n是数组个数，我们为什么要让i小于n-gap（间隙），刚才插入排序是不是小于n-1，其实道理差不多，如果我们end按照间隙加，那最后一次如果超过n不就越界访问了，所以让end<n-gap,使得找end+gap的情况不越界。

那么我们的间隙该怎么定呢。间隙越大，换的越快，越不接近有序数组。间隙越小，换的越慢，越接近有序数组。那我们如果让间隙是变化的，那这样不久越来越好了。应该从大往小变，为什么，第一次间隙为1，直接写成插入排序了。哈哈哈哈。但是这这只是预排序，那么之后该怎么排序才能完全成为有序的呢。那么我们最后一次进行插入排序是不是就可以了。那么正好是不是和刚才的间隙对应上了，如果我们让间隙从大变小，直到变为1，那就完成了希尔排序。第一次的间隙我们取数组的一半，为什么？你想想如果比一半大，那还能找到end+gap的数嘛，直接越界了。哈哈哈哈哈哈哈哈哈哈哈哈。

void ShellSort(int* arr, int n)
{
	int gap = n;
	while (gap)
	{
		gap /= 2;
		for (int i = 0; i < n - gap; i++)//从每个的头开始依次遍历，进行循环调整
		{

			int end = i;
			int tmp = arr[end + gap];
			while (end <n)
			{
				if (arr[end] > tmp)
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tmp;
		}
	}
}

有没有发现和刚才不一样，for循环从两个变成一个了，我们进行了改进，反正我们从蓝色完了就是红色，再然后就是绿色。那我们直接从第一个开始依次加间隙，直到end加间隙越界，不就行了。也就是蓝色组第一个，接着红色组第一个，绿色组第一个，然后蓝色第二个。。。。

感谢观看，欢迎指出错误。