程序员必知的8大排序(一)——-直接插入排序，希尔排序（java实现）
程序员必知的8大排序(二)——-简单选择排序，堆排序（java实现）
程序员必知的8大排序(三)——-冒泡排序，快速排序（java实现）
程序员必知的8大排序(四)——-归并排序，基数排序（java实现）
程序员必知的8大排序(五)——-总结
5.冒泡排序
（1）基本思想：在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。
（2）实例：
冒泡法执行的次数是确定的，不存在最多和最少次数，如果有n个数要进行冒泡法排序，那么就要执行(n-1)+(n-2)+(n-3)……+3+2+1次循环！n个数,第一轮,比较n-1次,得到最大（或最小）数余下的n-1个数,比较n-2次,得到排第二位的数以此此类推,最后比较1次,确定最后两个数的大小故共比次数：1+2+...+n-1=(1+n-1)(n-1)/2=n(n-1)/2等差数列：前n项和公式为：Sn=n*a1+n(n-1)d/2或Sn=n(a1+an)/2则比较次数永远都是N (N - 1) / 2（和选择排序一样）
（3）用java实现
public class Sort { public static void main(String[] args) {
bubbleSort();
} public static void bubbleSort(){
int a[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,34,15,35,25,53,51};
int temp=0;
for(int i=0;i<a.length-1;i++){
for(int j=0;j<a.length-1-i;j++){
if(a[j]>a[j+1]){
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
for(int i=0;i<a.length;i++)
System.out.println(a[i]);
}}
6.快速排序
（1）基本思想：选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。
（2快速排序一听名字就觉得很高端，在实际应用当中快速排序确实也是表现最好的排序算法。快速排序虽然高端，但其实其思想是来自冒泡排序，冒泡排序是通过相邻元素的比较和交换把最小的冒泡到最顶端，而快速排序是比较和交换小数和大数，这样一来不仅把小数冒泡到上面同时也把大数沉到下面。
（3）总结快速排序的思想：冒泡+二分+递归分治，慢慢体会。。。
（4）实例：
（3）用java实现
public class SortTest { public static void main(String []args){
System.out.println("Hello World");
int[] a = {2,1,4,3};
int start = 0;
int end = a.length-1;
sort(a,start,end);
for(int i = 0; i<a.length; i++){
System.out.println(a[i]);
} } public static void sort(int[] a,int s_start,int s_end){
int start = s_start;
int end = s_end;
int key = a[s_start]; while(end>start){
//从后往前比较
while(end>start&&a[end]>=key) //如果没有比关键值小的，比较下一个，直到有比关键值小的交换位置，然后又从前往后比较
end--;
if(a[end]<=key){
int temp = a[end];
a[end] = a[start];
a[start] = temp;
}
//从前往后比较
while(end>start&&a[start]<=key)//如果没有比关键值大的，比较下一个，直到有比关键值大的交换位置
start++;
if(a[start]>=key){
int temp = a[start];
a[start] = a[end];
a[end] = temp;
}
//此时第一次循环比较结束，关键值的位置已经确定了。左边的值都比关键值小，
//右边的值都比关键值大，但是两边的顺序还有可能是不一样的，进行下面的递归调用
}
//递归
if(start>s_start) sort(a,s_start,start-1);//左边序列。第一个索引位置到关键值索引-1
if(end<s_end) sort(a,end+1,s_end);//右边序列。从关键值索引+1到最后一个
}}
