作为一个程序员，我们经常能听到大家在讨论各种排序算法，说的云里雾里，貌似很难的样子，感觉可牛逼了。可是当我们仔细去学习后发现，其实并是想象中那么难，下面就来分析下几种常用的排序。
选择排序
原理：选择排序是每一次从待排序的数据元素中选出最小的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。主要分如下步骤：
（1）将第一个位值上的数跟之后所有位置上的数依次进行比较，如果第一个位置上的数比第二个位置上的数大，则进行互换，然后继续将第一个位置上的数与第三个位置上的数进行比较，经过一轮的比较后，第一个位值上的数就是所有数中最小的一个。
（2）将第二个位置上的数与之后所有位置上的数进行比较，同样的规则，第二轮比较结束后，第二位放的就是所有数中第二小的数。
（3）以此类推，重复上面的步骤（2）依次往下比，直到最后一个位置结束。
选择排序有简单选择排序和堆排序，这里我们只是以简单排序来讲解，其他可自己了解。
具体代码实现如下：
public int[] sort(int []arr){
int len = arr.length; //计算数组长度
for(int i=0;i<len;i++){ //控制循环次数
for(int j=i+1;j<len;j++){//控制比较次数
if(arr[i]>arr[j]){//当前一个数大于后一个数，交换位置
int tmp = arr[i];
arr[i]=arr[j];
arr[j]=tmp;
}
}
}
return arr;
}
假设参与比较的数组元素个数为 n，则第一轮排序有 n-1 次比较，第二轮有 n-2 次，如此类推，这种序列的求和公式为：
（n-1）+（n-2）+...+1 = n*（n-1）/2。当 n 的值很大时，算法比较次数约为 n2/2次比较，用大O表示是O(n2) 时间级别。
插入排序
原理：每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。
插入排序还分为直接插入排序、二分插入排序、链表插入排序、希尔排序等等，这里我们只是以直接插入排序讲解，其他的可以自己去了解。
具体代码实现如下：
pbulic int[] insertSort(int []arr){
int j;//用来记录插入的位置
int i;//从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
for(i = 1 ; i < arr.length; i++){
int tmp = arr[i];//记录要插入的数据
j = i;
while(j > 0 && tmp < arr[j-1]){//从已经排序的序列最右边的开始比较，找到比其小的数
arr[j] = arr[j-1];//向后挪动
j--;
}
arr[j] = tmp;//存在比其小的数，插入
}
return arr;
}
在最好情况下，需要比较n-1次，无需交换元素，时间复杂度为O(n);在最坏情况下，时间复杂度依然为O(n2)。
冒泡排序
原理：冒泡排序跟选择排序一样的简单，好理解，整个过程就想气泡一样往上升。假设从小到大排序，对于给定的n个记录，从第一个记录开始依次对相邻的两个记录进行比较，当前面的记录大于后面的记录时，交换位置，进行一轮比较后，第n位上就是整个记录中最大的数，然后在对前n-1个记录进行第二轮比较，重复该过程直到进行比较的记录只剩下一个为止。
具体代码实现如下：
public int[] bubbleSort(int[] arr){
int j = array.length - 1; //控制冒泡次数
while( j >= 1){
for(int i = 0; i < j; i++){
if(array[i] > array[i+1]){//控制比较次数
int tmp = array[i];
array[i] = array[i+1];
array[i+1] = tmp;
}
}
j--;
}
return arr;
}
冒泡排序和选择排序执行了相同次数的比较：n*（n-1）/2，时间复杂度同为O(n2)。
其实无论何时，只要看见一个循环嵌套在另一个循环中，我们都可以怀疑这个算法的运行时间为 O(n2)级，外层循环执行 N 次，内层循环对每一次外层循环都执行N次（或者几分之n次）。这就意味着大约需要执行N2次某个基本操作。
总结
上面讲的三种排序，冒泡、选择、插入用大 O 表示法都需要 O(n2) 时间级别。一般不会选择冒泡排序，虽然冒泡排序书写是最简单的，但是平均性能是没有选择排序和插入排序好的。
选择排序把交换次数降低到最低，但是比较次数还是挺大的。当数据量小，并且交换数据相对于比较数据更加耗时的情况下，可以应用选择排序。
在大多数情况下，假设数据量比较小或基本有序时，插入排序是三种算法中最好的选择。
注：以上图片来源网络。