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

冒泡排序

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

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;
    
}
}