尽管现在很多语言里都有现成的排序函数，但排序的思想还是需要搞懂。而且排序是数据结构里逃不掉的内容。如果你是做底层开发，只能自己写排序函数，而怎么写排序函数又关系到机器的效率问题，那究竟有哪些排序函数呢？
冒泡排序法
冒泡排序，很形象，最大的泡泡最先咕噜到水面，最小的泡泡最后咕噜到水面（体积越大，浮力越大），那我们数组里进行排序也是同样道理。假设数组里有5个元素，遍历第一遍找到5个元素中的最大值，遍历第二遍找到剩余的四个元素中的最大值，依此类推最后可以得到由大到小的有序数组。
通俗易懂吧，当然代价就是它的平均的时间复杂度为：O( n^2 )；平均的空间复杂度为：O(1)。
第一次讲解，说一下时间复杂度的定义：算法中内外循环中比较及交换元素的时间开销；空间复杂度的定义：交换元素时临时变量所占的内存空间。
#include<stdio.h>
int main(){
int n;//数组元素的个数
int buf[100];//用buf[100]来存储要排序的数组元素
while(scanf("%d",&n)!=EOF)//输入n，即输入的个数
{
for(int i=0 ;i<n;i++){
scanf("%d",&buf[i]);//读取每一个待排序数字
}
/* 冒泡排序主体 */
for(int i=0;i<n;i++){
for(int j=0;j<n-i-1;j++){
if(buf[j]>buf[j+1]){
int temp=buf[j];
buf[j]=buf[j+1];
buf[j+1]=temp;
}
}
}
/* 冒泡排序主体 */
printf("The result is:");
for(int i=0;i<n;i++){
printf("%d ",buf[i]);//打印输出结果，题目要求，在每一个数字后面都输出一个 空格
}
printf("\n");//输出换行
}
}
效果图：
image.png
直接插入排序法
插入排序，也很容易理解。想象有两个数组，第一个是待排序数组a，另一个是空数组b（用来存储有序元素）。
- 我们拿出a中的第一个元素放在b里，因为b中没有元素可以比较，所以它放在第一位
- 然后拿出a中的第二个元素放在b里，因为b中有了一个元素，所以需要与其进行比较放在正确的位置
- 再拿出a中的第三个元素放在b里，因为b中有了两个有序的元素，所以需要与这两个元素依次进行比较放在正确的位置里
- 以此类推，最后数组b中就是一个排好的元素了
为了发扬耐劳苦尚简朴的伟大精神，在实际编程中我们不采用两个数组，因为多一个数组就浪费一个数组的空间啊！我们可以用一个数组的空间进行排序：假设待排序元数有n个，则初始数组a的长度为n，初始数组b的长度为0，a的数组少一个元素b的数组就多一个元素，所以我们就可以用长度为n的数组空间就能表示了。
假设对无序表{3,1,7,5,2,4,9,6}进行升序排序
-
插入3
image.png -
插入1
image.png -
插入7
image.png -
插入5
image.png -
插入2
image.png
image.png
以上图片来源于http://c.biancheng.net/view/3439.html,是一个学C语言的好网站
#include<stdio.h>
int main(){
int n;//数组元素的个数
int buf[100];//用buf[100]来存储要排序的数组元素
while(scanf("%d",&n)!=EOF)//输入n，即输入的个数
{
for(int i=0 ;i<n;i++){
scanf("%d",&buf[i]);//读取每一个待排序数字
}
/* 插入排序主体 */
for(int i= 1; i<n; i++){
if(buf[i] < buf[i-1]){//若第 i 个元素大于 i-1 元素则直接插入；
//反之，需要找到适当的插入位置后在插入。
int j= i-1;
int x = buf[i];//使用一个变量等于数值，如果用buf[i]与buf[j]进行比较的话
//因为buf[i]地址不变但是值会变，所以要用x作为中间变量
while(j>-1 && x < buf[j]){
buf[j+1] = buf[j];
j--;
}
buf[j+1] = x;
}
}
/* 冒泡排序主体 */
printf("The result is:");
for(int i=0;i<n;i++){
printf("%d ",buf[i]);//打印输出结果，题目要求，在每一个数字后面都输出一个 空格
}
printf("\n");//输出换行
}
}
效果图：
image.png
