快速排序
快速排序是一种相比冒泡排序更加高效的排序算法。
参考网址:http://www.cnblogs.com/foreverking/articles/2234225.html
参考网址:http://developer.51cto.com/art/201403/430986.htm
最坏时间复杂度：
平均时间复杂度：
常见场景
- 海量数据 一年的全国高考考生人数为500万，分数使用标准分，最低100分，最高900分，没有小数，要求对这500万元素进行排序。
分析：对500W数据排序，如果按一般的复杂度比较低的排序，平均比较次数5000000*log5000000=1.112亿。但我们发现这些数据有特殊性，100<=score<=900 所以可以考虑痛排序这种“投机取巧”的方法，让其在较短的比较次数下完成排序。
方法：创建801个桶，将每个考生的分数丢进去，这个过程从头遍历至尾只需要500W次。然后根据桶号大小依次将桶中的数值输出，即可得到一个有序序列。同时我们还可以得到100分有几人，101分有几人这样的信息。
注意，桶排序对数据有特殊要求，比如上面的分数如果不是100-900，而是0-2亿，那么分配2亿个桶显然是不可能的。所以桶排序有其局限性，适合元素集合不大的情况。
代码
/**
* 快速排序
*
* @param num
* @param left
* @param right
*/
public static void quickSort(int[] num,int left,int right){
if(left >=right){
return ;
}
int i = left;
int j = right;
int temp = num[left];//拿到基准值
while(i!=j){
while(i<j && num[j]>=temp){
//比基准值大
j--;
}
if(j>i){
num[i] = num[j];
}
while(i<j && num[i]<=temp){
i++;
}
if(i<j){
num[j] = num[i];
}
}
num[i] = temp;
//递归左边
quickSort(num,left,i-1);
//递归右边
quickSort(num,i+1,right);
}
冒泡排序
冒泡排序是一种理解容易，但复杂度比较高的排序算法。
冒泡排序的基本思想是：每次比较两个相邻的元素，如果他们的顺序错误就把他们交换过来。
参考网址：http://blog.51cto.com/ahalei/1364401
时间复杂度：
代码
/**
* 冒泡排序
* @param nums
*/
public static void bubbleSort(int[] nums){
for(int i=0;i<nums.length;i++){
for(int j=i+1;j<nums.length;j++){
if(nums[i]>nums[j]){
nums[i] ^= nums[j];
nums[j] ^= nums[i];
nums[i] ^= nums[j];
}
}
}
}
直接插入排序
直接插入排序是一种简单的排序算法，其过程是依次将每个元素插入到一个已经有序的序列中去。
void insertSort(int R[] int n){
int i,j;
int temp;
for(i=1;i<n;i++){
temp = R[i];//从第2个元素开始
j=i-1;
while(j>=0 && temp<R[j]){
R[j+1] = R[j];
j--;
}
R[j+1] = temp;
}
}
直接插入排序是稳定的，最坏时间复杂度是
