八大排序（插入排序 | 选择排序 | 冒泡排序）

在我们内存中我们一般会有一些没有顺序的数据，我们成为内排序，而今天分享八大排序的是时间复杂度为O（N^2）的插入排序，选择排序和教学意义比较强的冒泡排序。

插入排序?

?这是插入排序的动图，通过动图我们也是可以看到我们的插入排序的思想

从当前的位置往前找小，如果当前位置的值是比前面的位置下的，前面位置往后挪动覆盖，因为会覆盖当前的位置，所以我们需要一个key来保存我们的当前的位置，如果往前找位置的时候，这个位置的值是比我们当前位置的值小的时候，循环就开始停下来，这个时候我们退出循环，在进行插入就是插入排序，我们先来看看我们的代码，然后画图来给大家看看。

void InsertSort(int* a, int n)
{

	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int key = a[end + 1];
		while (end >= 0)
		{
			if (a[end] > key)
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = key;
	}

}

代码是很简短的，我们给个数组是{9， 8， 7， 6， 5， 4， 3， 2， 1}。

end需要往前移动找小，如果比他大，那这个位置的数就得往后移动。?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?选择排序

?

?

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void SelectSort(int* a, int n)
{
	
	for (int j = 0; j < n; j++)
	{
		int mini = j;
		for (int i = j; i < n; i++)
		{
			if (a[i] < a[mini])
			{
				mini = i;
				
			}
			i++;

		}
		Swap(&a[mini], &a[j]);
	}
	
}

这个就是选择排序的基础玩法，但是这个选择排序我们一次只找出最小的值，我们这里还是遍历一遍数组了，遍历一遍数组只找出一个值还是有点亏，所以我们可以优化一下，一次性找出两个值，分别是最大值和最小的值，但是！优化后还是有些缺点，就是存在覆盖问题，我们来先看看代码吧。

void SelectSort(int* a, int n)
{
	
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		int mini = begin;
		int maxi = begin;
		for (int i = begin; i <= end; i++)
		{
			if (a[i] < a[mini])
			{
				mini = i;
			}
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
			
		}
		Swap(&a[begin], &a[mini]);
		if (begin == maxi)
		{
			maxi = mini;
		}
		Swap(&a[end], &a[maxi]);
		begin++;
		end--;
	}
}

优化之后判断哪个地方需要我们注意一下，因为begin的位置可能开始就是最大值，这里还需要注意的就是我们的maxi和mini一定要放到循环里面，因为你不放进去他每次都是从一开始的begin，就是下标0开始，这样会打乱我们刚开始的排序。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?冒泡排序

冒泡排序还不简单，我们直接手搓，要是这个小编还能写错，我直接eat? big shit

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		int j = 0;
		for (j = 0; j < n -1 - i; j++)
		{
			if (a[j] > a[j + 1])
			{
				Swap(&a[j], &a[j + 1]);
					
			}
			
			
		}
	}
}

那我们的三个时间复杂度是O（N^2）的排序也是终于完成了。我们下次来讲讲在插入排序的基础上实现希尔排序。