面试的时候经常会遇到面试官让你直接手写排序算法，下面是冒泡排序和快速排序的实现。


冒泡排序

基本流程就是，自下而上比较相邻的两个元素进行比较，让大的元素往下面沉，较小的往上冒。按照排序规则进行比较，如果是跟排序的规则相反就需要调整互换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
package  cn.test1;
 
import  org.apache.commons.lang.ArrayUtils;
 
public  class  BubbleSort {
 
     public  static  void  main(String[] args) {
         int [] array = {  1 ,  12 ,  34 ,  3 ,  56 ,  6 ,  9 ,  10 ,  12  };
         bubbleSort(array);
 
         for  ( int  i : array) {
             System.out.println(i);
         }
     }
 
     public  static  void  bubbleSort( int [] array) {
         if  (ArrayUtils.isEmpty(array)) {
             return ;
         }
 
         int  length = array.length;
         for  ( int  i =  0 ; i < length -  1 ; i++) {
             for  ( int  j =  1 ; j < length -  1 ; j++) {
                 if  (array[j] > array[j +  1 ]) {
                     int  temp = array[j];
                     array[j] = array[j +  1 ];
                     array[j +  1 ] = temp;
                 }
             }
         }
 
     }
 
}


快速排序：

基本思想：先找准基数，随意选择数组一个元素，作为基数，不过一般选择数组头或者尾作为基数，如果选择了其他的元素，也要首先交换到末尾或者头。

分区过程：比基数大的放在右边，比基数小的放在左边。重复下去就可以排序了。

看下代码，自己试试，debug一下，会更清楚些。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
package  cn.test1;
 
public  class  QuickSort {
 
     public  static  void  main(String[] args) {
         QuickSort qs =  new  QuickSort();
         int [] array = {  78 ,  34 ,  12 ,  64 ,  5 ,  4 ,  62 ,  99 ,  98 ,  5 ,  18 ,  23 ,  34 ,  15 ,  51  };
         qs.sort(array);
     }
 
     public  void  sort( int [] array) {
         quickSort(array,  0 , array.length -  1 );
     }
 
     /**
      * 通过划分，基于分治思想，递归执行子任务排序最后合并
      * 
      * @param low
      *            数组首位索引
      * @param high
      *            数组末尾索引
      */
     public  void  quickSort( int [] array,  int  low,  int  high) {
         int  middleIndex;
         if  (low < high) {
             middleIndex = getMiddleIndex(array, low, high);
             quickSort(array, low, middleIndex -  1 );
             quickSort(array, middleIndex +  1 , high);
         }
     }
 
     /**
      * 简单划分方法
      */
     public  int  getMiddleIndex( int [] array,  int  i,  int  j) {
         int  pivot = array[i];  // array[i] 就是 第一个坑
 
         while  (i < j) {
             while  (i < j && array[j] >= pivot) {
                 j--;  // 从右向左找出小于基准数pivot的数来填充array[i]
             }
 
             if  (i < j) {
                 array[i] = array[j];  // 将array[j]填充到array[i]中，array[j]就形成了一个新的坑
                 i++;
             }
 
             while  (i < j && array[i] <= pivot) {
                 i++;  // 从左向右找出大于基准数pivot的数来填充array[j]
             }
 
             if  (i < j) {
                 array[j] = array[i];  // 将array[i]填充到array[j]中，array[i]就形成了一个新的坑
                 j--;
             }
         }
         array[i] = pivot;  // 退出时，i等于j。将pivot填到这个坑中。
         return  i;
     }
}