算法与数据结构基础（三）插入排序、选择排序和冒泡排序的区别

 插入排序的原理：

始终定义第一个元素为有序的，将元素逐个插入到有序排列之中，其特点是要不断的移动数据，空出一个适当的位置，把待插入的元素放到里面去。插入排序的函数如下：

insertion_sort(int *arr,int len)
{
　　　　int i,j,tmp;
　　　　 for(i=1;i<len;i++)
　　　　 {
　　　　　　　　 j=i-1;
　　　　　　　　tmp=arr[i];
　　　　　　　　 while(j>=0&&arr[j]>tmp)
  　　　　　　　　{
　　　　　　　　　　　　arr[j+1]=arr[j];
　　　　　　　　　　　　 j--;
　　　　　　　　}
　　　　　　　　arr[j+1]=tmp;
　　　　}
}
    其中，arr为要排序的数组，len为数组的长度，j为数组下标，tmp为定义的要插入的数。可以看到，在while循环中，不断的去比较待插入的值与有序队列的值，不断的去移动数据，最后找到合适的位置，插入数据。

选择排序的原理：

每次在无序队列中“选择”出最小值，放到有序队列的最后，并从无序队列中去除该值（具体实现略有区别）。代码如下：

selection_sort(int *arr, int n)
{
　　　　int i,j,min,temp;
　　　　for(i=0;i<n-1;i++)
　　　　{
　　　　　　　　min=i;
　　　　　　　　for(j=i+1;j<n;j++)
　　　　{
　　　　　　　　if(arr[j]<arr[min])
　　　　　　　　{
　　　　　　　　　　　　min=j;
　　　　　　　　}
　　　　 }
}
    可以看出，选择排序的特点就是每次选出最小的放到有序队列最后。当然，也可以选出最大值放到有序队列的最前。

冒泡排序的原理：

每次在无序队列里将相邻两个数依次进行比较，将小数调换到前面，逐次比较，直至将最大的数移到最后。最将剩下的N-1个数继续比较，将次大数移至倒数第二位。依此规律，直至比较结束。冒泡代码如下：

sort(int *arr,int n)
{
　　　　int i,j,t;
　　　　for(i=0;i<n-1;i++)
　　　　{
　　　　　　　　for(j=0;j<n-1-i;j++)
　　　　　　　　{
　　　　　　　　　　　　if(arr[j]>arr[j+1])
　　　　　　　　　　　　{
　　　　　　　　　　　　　　　　t=arr[j];
　　　　　　　　　　　　　　　　arr[j]=arr[j+1];
　　　　　　　　　　　　　　　　arr[j+1]=t;
　　　　　　　　　　　　}
　　　　　　　　}
　　　　}
}
可以看到当把最大的数移至最后位置时，第二个for循环循环次数减一，即只比较最后位前的N-1位即可。