面试的时候经常会遇到面试官让你直接手写排序算法，下面是冒泡排序和快速排序的实现。
冒泡排序
基本流程就是，自下而上比较相邻的两个元素进行比较，让大的元素往下面沉，较小的往上冒。按照排序规则进行比较，如果是跟排序的规则相反就需要调整互换。
|
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;
}
} |
版权声明：原创作品，如需转载，请注明出处。否则将追究法律责任
本文转自 豆芽菜橙 51CTO博客，原文链接:http://blog.51cto.com/shangdc/1921323