《数据结构》排序 —— 插入+冒泡+选择

| |

前言：《数据结构》作为计算机专业的一门重点学科，无论是将来考研、就业，对其的考察都是重中之重，之前的文章已经对此进行过论述。作为考察程序员“编程能力”的一种方式，考验的是我们如何将数据结构的思想用编程语言精确的编码出来。所有的《数据结构》课本都详细的讲解了每一种数据结构和算法的思想，然后给出具体的编程语言代码或者伪代码。算法思想只要认真看书，还是比较容易掌握的 ，真正考验我们的，是从算法思想到具体编码的这个思考过程，就是思考如何编码实现，这个过程是逃不掉的，除非参考别人的现有代码，但一段时间过后一定会忘记（百分之百的，我就忘记了无数次了）。所以，尽量在编程实现前，自己有个清晰的思路，尝试着自己去实现，然后调试。

代码

本文全部代码放在github，需要的可以下载或者直接复制代码运行，只有一个cpp文件。已经通过测试，完全没有问题。这里重点是实现算法思想，所以没有考虑代码的健壮性，没有异常处理。

一点说明
之所以将这三个排序放在一起，是因为这三种排序方法相对来说还是非常简单的，首先就是算法思想很简单，大部分人应该都能够想到这三种算法，没有什么复杂的逻辑，其次编程实现起来也没什么坑，所以就将其归为一类了。

插入排序

关于插入排序的算法思想就不再赘述，但是有一点在编程实现时需要一点点思考：就是我们在描述插入时是说——”将待排数据插入到已排序列当中“，这句话把思想描述的非常清晰，我们都理解这句话的意思，但是对计算机来说就相当模糊了。编程的重点，就是将这类模糊的自然语言描述，用编程语言转化成具体的计算机命令，当然这个算是非常简单的了，不过我还是想啰嗦两句。
这里的插入，对计算机来说分为三步：比较——移动——插入。

比较：比较有两种方法：从前往后&从后往前。这里我们采用的是从后往前，因为从前往后进行比较的话，一会儿移动起来会比较麻烦，原因大家可以自己思考，很简单。

移动：移动又分为两种：比较一个移动一个&先比较后移动。这里我们采用的前者，因为后者也是会比较麻烦，也是我们为什么在进行比较时，会采用从后往前比较的原因。

插入：这个就没什么可说的了，移动完了在空出的位置插入即可。

由此可见，一句简单的”插入“，对于计算机来说，可并不简单。所以我们在进行编程时，大脑一定要清晰，逻辑不要混乱,想清楚每一步该怎么走。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void inser(int data[])		//插入排序
{
	/*定义需要用到的变量*/
	int contemp;	//临时存放待插入的元素
	int i;	//存放待插入元素的位置
	int j;	//用来指向已被排序好的部分的元素的位置
	for(i=1;i<ArraySize;i++)
	{
		j=i-1;	
		contemp = data[i];
		while(j>=0&&data[j]>contemp)
		{
			data[j+1]=data[j];
			j--;
		}
		data[j+1]=contemp;
	}
}

冒泡排序

这个应该是排序里的经典了吧，两个for循环就搞定。不过我更倾向于认为它是”沉底排序“，而不是”冒泡“。因为以一般人的习惯，都是对待排数组从前往后遍历，然后把最大的放到最后，这不就是”沉底“嘛………

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void maopao(int data[])		//冒泡排序
{
	int contemp;	//临时存放
	for(int i=ArraySize-1;i>0;i--)	//一共需要“ArraySize-1”次循环才能完成
		for(int j=0;j<i;j++)	//每一次循环需要比较的次数是递减的
		{
			if(data[j]>data[j+1])
			{
				contemp=data[j];
				data[j]=data[j+1];
				data[j+1]=contemp;
			}
		}
}

选择排序

选择排序就是每一次都选择最大（最小）的放到最后（最前），和冒泡的思路差不多，也需要两次for循环，但是要注意它们两个for循环的逻辑是不一样的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void select(int data[])		//选择排序
{
	int contemp;	//临时存放
	for(int i=0;i<ArraySize-1;i++)		//需要“ArraySize-1”次循环
		for(int j=i+1;j<ArraySize;j++)
		{
			if(data[i]>data[j])
			{
				contemp=data[j];
				data[j]=data[i];
				data[i]=contemp;
			}
		}
}