冒泡排序 选择排序 插入排序三种基础排序的比较
排序在计算机中是很基础并且是十分重要的问题，但由于排序有可能非常耗时，所以它已经成为了计算机科学中广泛研究的课题。对此仅仅讨论一些简单的排序算法，冒泡排序，选择排序，插入排序。对此只是自己学习的一个记录。
例如：有一群升高不尽相同的人站成一排，我们想要通过某种方法，将他们排成一列升高有序的队伍（例如：从低到高）。在排序这件事上我们人与计算机相比有以下优势，我们可以看到周围所有的队员并且立刻找出最高的一个，而不用费力地测量和比较每个人的身高。而且，队员们不一定要固守特定的 空间，他们可以相互推推操操就腾出了位置，还能互相前后站立。经过一些具体的调整，就可以毫 不费力地给队员们排好队。计算机程序却不能像人这样通览所有的数据。它只能根据计算机的“比较”操作原理，在同一 时间内对两个队员进行比较。算法的这种“管视"将是一个反复出现的问题。在人类看来很简单的 事情，计算机的算法却不能看到全景，因此它只能一步一步地解决具体问题和遵循一些简单的规则。
计算机实现方法一：每次和从第一个人开始，依次与相邻的人比较，如果比旁边的一个人矮则交换位置，否则不变。假设有10个人，第一次比较是第一个人与第二个人比较，如果第二个人高于第一个人则不改变位置，否则交换，依次这样。
//冒泡排序
#include "stdio.h"
#define N 1000
int main (){
int a[N];
int i,n;//n表示输入个数
scanf("%d",&n);
for(i = 0;i<n;i++){
scanf("%d",&a[i]);
}
int j,k;
for(j = 0;j<n;j++){
for(k = j+1;k=a[k]){
int temp = a[k];
a[k] = a[j];
a[j] = temp;
}
}
}
for(i=0;i<n;i++){
printf("%d ",a[i]);
}
printf("\n");
}
我们可以发现，排序主要的过程就是比较，然后交换位置。程序需要进行比较的次数为外层循环n次，内层循环随着外层循环的改变而改变，计算得到的次数为n*(n-1)/2次。如果是最差的情况则每次都要交换，因此交换所需要的次数也为n*(n-1)/2次。
//选择排序
#include "stdio.h"
#define N 10000
int main(){
int a[N];
int i,j,k,n;
scanf("%d",&n);
for(i = 0;i<n;i++){
scanf("%d",&a[i]);
}
for(j=0;j<n-1;j++){
int min = j;//最小的数的下标
for(k = j+1;k a[k]){
min = k;//直到选出最小
}
}
//交换
int temp = a[j];
a[j] = a[min];
a[min] = temp;
}
for(i = 0;i<n;i++)
{
printf("%d ",a[i]);
}
printf("\n");
}
选择排序改进了冒泡排序，将必要的交换次数从O(N2)减少到0(N)=不幸的是比较次数仍保持 为O(N2)o然而，选择排序仍然为大记录量的排序提出了一个非常重要的改进，因为这些大量的记 录需要在内存中移动，这就使交换的时间和比较的时间相比起来，交换的时间更为重要。
//插入排序
#include "stdio.h"
#define N 1000
int main(){
int a[N];
int n;
int i,in,out;
scanf("%d",&n);
for(i = 0;i<n;i++){
scanf("%d",&a[i]);//存入n个数，将这n个数排序输出
}
for(out = 1;out=temp&&in>0){
a[in] = a[in-1];
in--;
}
a[in] = temp;
}
//输出
for(i = 0;i<n;i++){
printf("%d ",a[i]);
}
printf("\n");
}
虽然插入排序的时间复杂度为O(N2)，但是在一般情况下，它要比冒泡排序快一倍，比选择排序还要快一点。总的来说插入和选择都是降低了数据交换的次数。
作者：@那个帅哥
