在生活中常常需要处理一些关于排序的问题，对一串数据进行升序、降序操作时，我们往往可以使用一些排序的方法去处理这类的问题。
C语言常见的三种排序方法可以分为：冒泡法、选择法和插入法三种。
一、3种算法的分析：
题目排序要求：对随机输入的10个整数按升序进行排序
1、 冒泡法
算法特点：对相邻元素进行比较，每轮（比较完一次所有的数）将比较的数中的最大/小值沉底。确定元素位置的顺序是从后往前，其余元素可能作相对位置的调整。可以进行升序或降序排序。
算法分析：定义n-1次循环，每个数字比较n-j次，比较前一个数和后一个数的大小。然后交换顺序。
算法分析：冒泡法就是每次冒出最大或最小的之一数的过程，在这个过程中，每次比较两两相邻的数的大小，进行交换位置。如果有n个数，则要进行n-1轮比较（两两相邻正好有n-1个空隙）。在第1轮的比较中要进行n-1次相邻元素的两两比较，在第2轮的比较中要进行n-2次相邻元素的两两比较，依次类推，则在第i轮比较中要进行n-i次两两比较。比较的顺序从前往后，每经过一轮比较后，将比较数中的最大值或最小值沉底（换到最后一个元素位置），最大值沉底为升序，最小值沉底为降序。
算法的示例代码：
#include <stdio.h> int main() { int a[10],i,j; printf("请随机输入10个数进行比较大小：\n"); //数组接收数据必须逐个元素进行赋值 for(i=0;i<10;i++) scanf("%d",&a[i]); /*冒泡排序过程*/ for(i=0;i<9;i++) //此循环用于循环的轮数 { for(j=0;j<9-i;j++) //此循环用计算每轮循环，循环的次数第i轮是比较n-i次 { if(a[j]>a[j+1]) //比较相连的两个数的大小，判断是否需要交换 { int temp; temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } }
}
/*输出排序后的结果*/ printf("由小到大排序的结果为: "); for(i=0;i<10;i++)printf("%d ",a[i]); printf("\n"); } |
2、 选择法
算法特点：每轮是选出一个最值确定其在结果序列中的位置，确定元素的位置的方式是从前往后进行选择的，而每轮最多只会进行一次交换，其余元素的相对位置不变。可进行降序排序或升序排序。
算法分析：定义外层n-1次循环，假设第一个为最值，放在参数中，在从下一个数以后找最值若后面有比前面假设的最值更大的就放在k中，然后在对k进行分析。若k部位最初的i值。也就是假设的i不是最值，那么就交换最值和当前序列的第一个数。
算法的示例代码：
#include <stdio.h> int main() { int a[10],i,j,temp; printf("请随机输入10个数进行比较大小：\n"); for(i=0;i<10;i++)scanf("%d",&a[i]); for(i=1;i<10;i++) //外循环控制轮数，n个数从第2个数开始到最后共进行n-1次插入 { temp=a[i]; //将待插入数暂存于变量t中 for( j=i-1 ; j>=0 && temp<a[j] ; j-- ) //在有序序列（下标0 ~ i-1）中寻找插入位置 a[j+1]=a[j]; //若未找到插入位置，则当前元素后移一个位置 a[j+1]=temp; //找到插入位置，完成插入 } printf("小到大排序的结果为: "); for(i=0;i<10;i++) printf("%d ",a[i]); printf("\n"); } |
3、插入排序
算法特点：每轮从无序序列中取出第一个数插入到有序序列的合适位置，元素的最终位置在最后一轮插入后才能确定位置。也可是先用循环查找插入位置（可从前往后或从后往前），再将插入位置之后的元素（有序列中）逐个后移一个位置，最后完成插入。该算法的特点是在寻找插入位置的同时完成元素的移动。因为元素的移动必须从后往前，则可将两个操作结合在一起完成，提高算法效率。仍可进行升序或降序排序。
算法分析：将序列分为有序序列和无序列，依次从无序序列中取出元素值插入到有序序列的合适位置。初始是有序序列中只有第一个数，其余n-1个数组成无序序列，则n个数需进n-1次插入。寻找在有序序列中插入位置可以从有序序列的最后一个数往前找，在未找到插入点之前可以同时向后移动元素，为插入元素准备空间。
#include <stdio.h> int main() { int a[10],i,j,t; printf("请随机输入10个数进行比较大小：\n"); for(i=0;i<10;i++)scanf("%d",&a[i]); for(i=1;i<10;i++) //外循环控制趟数，n个数从第2个数开始到最后共进行n-1次插入 { t=a[i]; //将待插入数暂存于变量t中 for( j=i-1 ; j>=0 && t<a[j] ; j-- ) //在有序序列（下标0 ~ i-1）中寻找插入位置 a[j+1]=a[j]; //若未找到插入位置，则当前元素后移一个位置 a[j+1]=t; //找到插入位置，完成插入 } printf("小到大排序的结果为: "); for(i=0;i<10;i++)printf("%d ",a[i]); printf("\n"); } |
二、算法的优缺点分析
1、冒泡排序
优点：稳定，比较次数可知；
缺点：慢，每次只能移动相邻两个数据，移动数据的次数多。
2、选择排序
优点：稳定，比较次数与冒泡排序一样，数据移动次数比冒泡排序少；
缺点：相对之下还是慢。
3、插入排序
优点：稳定，快；
缺点：比较次数不一定，比较次数越少，插入点后的数据移动越多，特别是当数据总量庞大的时候，但用链表可以解决这个问题