排序算法是大多数人入门算法的基础，这篇博文便介绍一下著名的lowb三人组及其代码实现（基于c语言）。

什么是lowb三人组

lowb三人组指的是排序算法中的冒泡排序（bubble sort）插入排序（insert sort）查找排序（insert sort）这三种算法理解和实现起来简单，时间复杂度均为O（n^2），相比于一些牛B的算法就 比较lowb，因此得名。

冒泡排序（bubble sort）

冒泡排序可以想象是在烧开水，开水沸腾的时候气泡便会从底冒到顶。

以数组{3，2，4，1，6，5}为例：
要想把它按升序排列，可采取以下方案：
3>2,交换3和2得到2，3，4，1，6，5
3<4,pass看下一组
4>1,交换4和1得到2，3，1，4，6，5
4<6,pass看下一组
6>5，交换6和5得到2，3，1，4，5，6

上述过程称为冒泡排序的一趟，也就是一次冒泡，一次冒泡过程中，最大的“泡泡”会冒到顶端，也就是数组的最后一个元素。我们将其定为有序区，前面的称为。一次冒泡会导致有序区元素+1，无序区则-1。对无序区继续进行一次冒泡。
2，1，3，4， （无序区）|（有序区）5 ，6
循环下去直至无序区为空（冒泡n（数组长度）趟）则排序完成。（无序区元素为1的时候，它一定是无序区最大的，直接放入有序区其实就可以完成排序了（即冒泡n-1趟便可））。

下面请观看一段魔性舞蹈，帮助理解冒泡吧~

[bilibili]冒泡排序魔性舞蹈点此观看

上述过程代码实现如下：

void bubble_sort(int nums[],int size)
{
	//进行第i趟,i从0开始计数，每一趟最大的“泡泡”会冒到数组末尾
	for (int i = 0; i < size-1; i++)
	{
		for (int j = 0; j<size-i-1; j++)//对无序区进行一趟冒泡的过程
		{
			//比后面的数大，交换
			if (nums[j]>nums[j + 1])
			{
				int tmp = nums[j];
				nums[j] = nums[j + 1];
				nums[j + 1] = tmp;
			}
		}
	}
}

其实对于上述代码还可以进一步优化：
比如数组{3，2，4，1，6，5}冒泡3次后便排好了。
之后的循环啥都没做。
故当出现有一趟完成后数组没有改变，就可以认为已经排好。

void bubble_sort(int nums[],int size)
{
	//进行第i趟,i从0开始计数，每一趟最大的“泡泡”会冒到数组末尾
	for (int i = 0; i < size-1; i++)
	{
		int isSorted = 1;
		for (int j = 0; j<size-i-1; j++)//对无序区进行一趟冒泡的过程
		{
			//比后面的数大，交换
			if (nums[j]>nums[j + 1])
			{
				int tmp = nums[j];
				nums[j] = nums[j + 1];
				nums[j + 1] = tmp;
				//数组有改变将isSort赋值0
				isSorted = 0;
			}
		}
		if (isSorted == 1)
		{
			//数组没有改变，已经排好了
			return;
		}
	}
}

插入排序（insert sort）

这个是我认为最好理解的算法，相信大家一定斗过地主，大家一定会这样理牌
摸到第一张牌，拿在手上，将它作为有序区。
摸第二张牌，与第一张比较，大就放在右边，小就放左边。然后它也加入了有序区。
摸第三张牌，它比有序区第二张小就放在第二张前面，成了第二张牌，第二张变成第三张，再与第一张比较一下，比第一张小再放前面.
…
摸到最后一张牌也放入有序区。就排好序啦~

[bilibili]插入排序魔性舞蹈

直接上代码：

void insert_sort(int nums[], int size)
{
	//从第1张开始，摸size-1张牌，每一张牌插入有序区
	for (int i = 1; i < size;i++ )
	{
		int tmp_inx = i;
		while (tmp_inx>0&&nums[tmp_inx] < nums[tmp_inx - 1])//只要这张牌不是第一张并且比前一张小就往前面放
		{
			//将第i张牌放到第i-1张牌前面
			int tmp = nums[tmp_inx];
			nums[tmp_inx] = nums[tmp_inx - 1];
			nums[tmp_inx - 1] = tmp;
			tmp_inx--;
		}
	}
}

选择排序（select sort）

选择排序的原理也很简单。
我们将数组遍历一遍，能找到最小的数。
（先把第一个元素当成最小，循环过程中遇到比它小的再把它当成最小。循环结束后便能找到最小的了。）
然后再剩下的元素中继续遍历可以找到第二小的数。
…
容易想到再拿一个数组来依次存放第几小的数，但是再使用一个数组又要开辟内存空间。一般不提倡。
想要原地排序，我们可以就最小的数与下标为0的数交换，然后作为有序区，对无序区再找出第二小的与下标为1的数交换…同样等到无序区只剩最后一个数的时候便可结束。

[bilibili]选择排序魔性舞蹈

void select_sort(int nums[], int size)
{
	//寻找i次，最后只剩一个一定是最大的数
	for (int i = 0; i < size - 1; i++)
	{
		//在无序区中找出最小的数
		int tmp = nums[i];
		int inx = i;
		for (int j = i; j < size-1; j++)
		{
			if (nums[j + 1] < tmp)
			{
				tmp = nums[j + 1];
				inx = j+1;
			}
		}
		nums[inx] = nums[i];
		nums[i] = tmp;
	}
}

说明

博主初学编程，很多东西了解不够，若文中有错误，敬请指出。
另外附上我的GitHub里面有一些自己写的小程序