最近去一家公司面试,手贱在人家CTO面前自告奋勇写了一把冒泡法,结果在交换数据的时候出了洋相,回家反思,写下如下代码,对自己算是一个鞭策,得到的教训是不要眼高手低,低调前行。
1 package com.defymedia.interview.sort;
2
3 import java.util.ArrayList;
4 import java.util.List;
5 import java.util.Random;
6
7 public class SimpleSort {
8
9 public static final int NO_MATCH = -1;
10
11 public <T extends Comparable> List<T> sort(List<T> list) {
12 int size = list != null ? list.size() : 0;
13 if (size == 0) return null;
14
15 for (int i = 0; i < size; i++) {
16 for (int j = i + 1; j < size; j++) {
17 if (list.get(i).compareTo(list.get(j)) > 0) {
18 T temp = list.get(i);
19 list.set(i, list.get(j));
20 list.set(j, temp);
21 }
22 }
23 }
24
25 return list;
26 }
27
28 public <T extends Comparable> T[] sort(T[] ts) {
29 int size = ts != null ? ts.length : 0;
30 if (size == 0) return null;
31
32 for (int i = 0; i < size; i++) {
33 for (int j = i + 1; j < size; j++) {
34 if (ts[i].compareTo(ts[j]) > 0) {
35 T temp = ts[i];
36 ts[i] = ts[j];
37 ts[j] = temp;
38 }
39 }
40 }
41
42 return ts;
43 }
44
45 public <T extends Comparable> int binarySearch(T[] ts, T t) {
46 int length = ts != null ? ts.length : NO_MATCH;
47 if (length <= 0 || t == null) return NO_MATCH;
48
49 int middle;
50 int index = NO_MATCH;
51 int low = 0;
52 int high = length;
53 while (low < high) {
54 middle = (low + high) >> 1;
55 T temp = ts[middle];
56 if (temp.compareTo(t) > 0) {
57 high = middle;
58 } else if (temp.compareTo(t) < 0) {
59 low = middle;
60 } else {
61 index = middle;
62 break;
63 }
64 }
65
66 System.out.println("index is " + index);
67 return index;
68 }
69
70 public static void main(String[] param) {
71 SimpleSort simpleSort = new SimpleSort();
72 int size = 10;
73 Random random = new Random();
74 List<Integer> list = new ArrayList<>(size);
75 for (int i = 0; i < size; i++) {
76 list.add(random.nextInt(20));
77 }
78 list = simpleSort.sort(list);
79 for (Comparable comparable : list) {
80 System.out.println(comparable.toString());
81 }
82 Integer[] data = new Integer[size];
83 for (int i = 0; i < size; i++) {
84 data[i] = random.nextInt(50);
85 }
86 data = simpleSort.sort(data);
87 for (Comparable comparable : data) {
88 System.out.println(comparable.toString());
89 }
90 int number = NO_MATCH;
91 simpleSort.binarySearch(data, number);
92 }
93 }