奔跑的肥豬

 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 }