排序算法——交换排序（冒泡排序、快速排序）（java）

一、冒泡排序

　　时间复杂度：O(n^2)

　　公认最慢的排序，每次把最大/最小的放一边，原理：

　　　　[57,68,59,52]

　　　　[57,59,68,52]

　　　　[57,59,52,68]

　　　　每次比较把相对大的数往后移，最后放到最后一位的就是整个数组中最大的数了，然后对n-1个数继续排序。

 1 public class BubbleSort {
 2     public static <T extends Comparable> void sort(T[] src){
 3         T tmp;
 4         int len = src.length;
 5         for(int i=0;i<len-1;i++){  // 注意是小于len-1，即遍历到倒数第二个元素
 6             for(int j=0;j<len-1-i;j++){
 7                 if(src[j].compareTo(src[j+1])>0){
 8                     tmp = src[j];
 9                     src[j] = src[j+1];
10                     src[j+1] = tmp;
11                 }
12             }
13         }
14     }
15 }

二、快速排序

　　时间复杂度：O(nlogn) 最坏情况：O(n^2)

　　空间复杂度：O(nlogn)

　　不稳定。

　　原理：选定基准值，把比它大的放右边，比它小的放左边，这样就分成了两块，对这两块重复以上步骤。

　　实际操作：

　　　　[15,11,18,13,19,17,12,16,14] 移动high指针，low=0,high=8,pivot=15[位置0]，第一次对比，14比基准值15小，src[low=0] = src[high8]

　　　　[14,11,18,13,19,17,12,16,14] 移动low指针，low依次=0,1,2，high=8，14和11都比15大，18比15大，src[high=8] = src[low=2]

　　　　[14,11,18,13,19,17,12,16,18] 移动high指针，low=2,high依次=8,7,6，到12比15小，src[low=2] = src[high=6]

　　　　[14,11,12,13,19,17,12,16,18] 移动low指针，low依次=2,3,4，high=6，19比15大，src[high=6] = src[low=4]

　　　　[14,11,12,13,19,17,19,16,18] 移动high指针，low=4，high依次=6,5,4，19和17都不小于15，到high=4，!low<high，此时的low/high就是基准值位置

　　　　[14,11,12,13,19,17,19,16,18] 现在low=4，high=4，low/high[4] = pivot，19位置值等于基准值

　　　　[14,11,12,13],15,[17,19,16,18] 分成两块了，再对这两块重复以上步骤，直到分出的值不多于一个。

 1 public class QuickSort {
 2     public static void sort(int[] src){
 3         quickSort(src,0,src.length-1);
 4     }
 5     
 6     private static void quickSort(int[] src,int low,int high){
 7         if(low<high){
 8             int mid = partition(src,low,high);  // 获得中间值的位置
 9             quickSort(src,low,mid-1);  // 对左部分快排
10             quickSort(src,mid+1,high);  // 对右部分快排
11         }
12     }
13     
14     private static int partition(int[] src,int low,int high){
15         int tmp = src[low];  // 记录基准值
16         while(low<high){  // 相等时，说明剩一个值，这就是基准值的最终位置
17             while(low<high&&src[high]>=tmp){
18                 high--;  // 从high开始，至有一个比基准值小的值时，high指针不动，下面的while从low开始找
19             }
20             src[low] = src[high];  // 交换值
21             while(low<high&&src[low]<=tmp){
22                 low++;
23             }
24             src[high] = src[low];
25         }
26         src[low] = tmp; 
27         return low;
28     }
29 }

-2014年04月28日--------------------更新了BubbleSort的代码