【C语言】三种最基础的排序方法
写在前面的话：我本人是学生，难免会出错，如果发现有错误的可以私信留言或提议。
排序方法是C语言最基础的算法之一，在平时的编程中也发挥着很大的作用，因此有必要进行仔细、深入的学习。冒泡法、简单排序法、直接插入法各地可能叫法不同，但是程序逻辑大致都是一样的。平时我用的最多的就是冒泡法，所以就重点聊一下冒泡法。（就是偏心）
（1）冒泡法
这种算法的思想顾名思义就是把比较小的数像冒泡一样排到前面（或后面），这样就实现了对数据的排列。
实现这个过程需要两个for循环，外层循环用来存储已经排好序的个数，内层循环用来指向两个相邻的数，进行比较。代码整上：
int main (){int a[10], temp, n;scanf ("%d", &n);for (int i = 0; i < n; i ++)scanf ("%d", &a[i]);for (int i = 0; i < n; i ++) {for (int j = 0; j < n - i - 1; j ++) {if (a[j] < a[j + 1]) {temp = a[j];a[j] = a[j + 1];a[j + 1] = temp;}}}for (int i =0 ; i < n; i ++)printf ("%d ", a[i]);return 0;}
这里要小心第9行的 -1 是避免数组越界。
比如说有一个长度是5的数组：i == 0, j == 0
开始时，i,j均被初始化为0，此时对a[j]和a[j+1]进行比较（从大到小排序，下同），此时a[0] < a[1]，满足if条件，执行交换过程，那么再一次来到内层循环判断的时候数组就变成了这样：i == 0, j == 1
之后再重复上面的过程，a[1] < a[2] ? 很明显是不满足的，所以不进行交换，内层循环继续：i == 0, j == 2 ,这时满足if条件，进行交换，再一次来到for循环进行判断时，已经是：i == 0, j == 3:
之后重复上面的过程：i == 0, j == 4:
此时跳出内层循环，i 自增1，再来到内层循环时：i ==1, j == 0
接着往下就是重复上面的过程......
如果在上述程序的某几行之间插入一个打印用来显示数组a目前的状态（代替调试过程）就可以得到下面的结果（最后一行是最终输出，其他都是加上来了解过程的，下同）：
（不要问我为啥字是绿的）
这样，我们就可以很直观的了解冒泡法究竟是怎么冒的了。此方法先在后面形成有序的数列。
（2）简单排序法
这种方法简单粗暴，就是先直接将整个数组里面的元素过滤一遍，选出最大的，然后把他和还没有进行排序的最前面数字交换位置。在这句话中，“还没有进行排序的最前面数字” 的定语有点不好理解，先整上代码再说：
int main () {int a[10], k, temp, n;scanf ("%d", &n);for (int i = 0; i < n; i ++)scanf ("%d", &a[i]);for (int i = 0; i < n; i ++) {k = i;for (int j = i; j < n; j ++)if (a[j] > a[k])k = j;if (i != k) {temp = a[i];a[i] = a[k];a[k] = temp;}}for (int i = 0; i < n; i ++)printf ("%d", a[i]);return 0;}
可以看出，程序的目的是将大数向前安排，然后通过 i 保存已经排好序的个数。其中，k发挥了中流砥柱的作用，它是表示当前没有排序中数列的最大数的序号。
外层循环开始时，先将还没有排好序的第一个数的序号赋值给k，然后利用循环进行逐个比较，选出最大数的序号k，再和未排序的第一个数进行换位，如下：
第一次查询开始，排好序的个数是0，k向后找最大的数，运行到内层循环结束时，得到：
然后换位，回到外层for循环时：
然后重复上面的过程：
从图上直观上讲，“还没有进行排序的最前面数字” 就是紧挨着黄色区域的那个数字，这样不断进行查找、换位就可以得到最终的顺序。
（3）直接插入法
这种方法和名字一样，很直接，就是向后查找比未排好序的第一个数大的一个数，如果找到了，就把前面的数字都向前移动一位，然后把这个数插进去。代码：
int main () {int a[10], n, j, k;scanf ("%d", &n);for (int i = 0; i < n; i ++)scanf ("%d", &a[i]);for (int i = 0; i < n; i ++) {int b = a[i];for (j = 0; (a[j] > a[i]) && (j < i); j ++);for (int k = i; k > j; k --)a[k] = a[k - 1];a[j] = b;}for (i = 0; i < n; i ++)printf (" %d ", a[i]);return 0;}
和简单排序法一样，外层循环的 i 是用来保存已经排好序的个数的，第一个第二层循环（line 9）是用来确定插入位置的，它从数列最开头开始查找直到遇见合适的位置，注意它后面是分号，表示省略循环体，之后再进行移位。找到插入位置之后，如图：
然后进行移位：
这里不标黄是因为直接插入可能插入的不是最终的位置，而是相对位置。过程如下：
这三种方法各有各的特色，当然，还有一些已经被封装好的库函数（如sort(), qsort()等），它们的执行效率更高。但是，这三种方法是理解复杂程序运行过程的基本，深入理解这三个方法的运行过程对于理解其他的程序运行过程也是有很大帮助的。