|
1
28
29 package com.caucho.util;
30
31 import java.util.ArrayList  ;
32
33 abstract public class Sort {
34 abstract public boolean lessThan(Object a, Object b);
35
36 private void quicksort(ArrayList list, int head, int tail)
37 {
38 if (tail - head < 2)
39 return;
40 else if (tail - head == 2) {
41 Object va = list.get(head);
42 Object vb = list.get(head + 1);
43
44 if (lessThan(vb, va)) {
45 list.set(head, vb);
46 list.set(head + 1, va);
47 }
48
49 return;
50 }
51
52 int center = head + 1;
53 Object pivot = list.get(head);
54 for (int i = head + 1; i < tail; i++) {
55 Object value = list.get(i);
56
57 if (lessThan(value, pivot)) {
58 Object centerValue = list.get(center);
59 list.set(center, value);
60 list.set(i, centerValue);
61 center++;
62 }
63 }
64
65 if (center == tail) {
66 Object tailValue = list.get(tail - 1);
67 list.set(head, tailValue);
68 list.set(tail - 1, pivot);
69
70 quicksort(list, head, tail - 1);
71 } else {
72 quicksort(list, head, center);
73 quicksort(list, center, tail);
74 }
75 }
76
77 public void sort(ArrayList list)
78 {
79 quicksort(list, 0, list.size());
80 }
81 }
82
83
84 |
Popular Tags |
Java API By Example, From Geeks To Geeks.