C语言中数组的排序算法详解

选择法排序是指：如果要把一个数组从小到大排列，那么就从该数组中依次选择最小的数字来排序。从第一个数字开始，将第一个数字与数组中剩下数字中最小的那一个交换位置，然后将第二个数字与剩下数字中最小的那个交换位置，以此类推，直到最后一个数字。 例如输入数组{7,5,4,8,6,2,3} 第一次排序通过查找最小的数字，交换7与2的位置；第二次查找5后面最小的数字，找到了3，交换5与3的位置；第三次查找4之后最小的数字，发现并没有数字比4小，交换4与4的位置（相当于没有改变）；第四次查找8后面最小的数字5，交换8与5的位置。

因为剩下的数字中，可能有不止一个数字比当前数字小，所以需要一个临时值来储存当前最小的数字，还需要一个标志位来记录当前最小数字对应的位号。实现代码如下：

插入法排序比较复杂，基本原理就是抽出一个数据，寻找相应的位置插入，再抽出一个数据，寻找相应的位置插入，直到完成排序。简单来说就是，对于一个数组来说，先取数组中的第二个数字，和第一个数字对比，如果比第一个数字小，则放到第一个数字前面；如果比第一个数字大，则放到第一个数字后面。然后取数组中第三个数字，与第二个数字和第一个数字对比，以此类推。

假设现在有这样一段数列{1,2,3,6,9} 而下一个待插入的数是 a[5] = 4 也就是待插入值temp = 4，i = 5，iPos=4 那么函数是这样运行的：

先对比待插入的值temp 与 a[4] = 6 的大小，此时temp = 4，满足while循环，那么就把原来a[4]的值放在a[5]上

此时iPos自减，仍然满足while循环条件，继续执行while循环代码。再来对比temp与a[3]的大小，此时temp仍然为4，在while循环里并没有更改temp的值。发现a[3]还是小于temp，于是继续把a[3]也往后放一个，放到a[4]的位置。

此时iPos自减，但是因为a[2] = 3，那么a[2]的值比temp小，所以while循环结束，跳出循环。只需要将待插入的值temp的值填在此时空出来的a[iPos+1] 的位置即可。

折半法排序又称为快速排序，是选取一个中间值，然后把比中间值小的数字放在左边，比中间值大的数字放在右边。然后两边分别递归使用这个过程。折半法排序对于较大的n时有较快的运算速度，但是折半法排序是不稳定的，对应有相同关键字的记录，排序后结果可能会颠倒次序。但是可以通过对这种排序方法的学习，来熟悉了解一些递归的思想，以及二分法的实现。