1public class StringQuickSort {
2
3 String names[];
4 int length;
5
6 public static void main(String[] args) {
7 StringQuickSort sorter = new StringQuickSort();
8 String words[] = {"zz", "aa", "cc", "hh", "bb", "ee", "ll"}; // the strings need to be sorted are put inside this array
9 sorter.sort(words);
10
11 for (String i : words) {
12 System.out.print(i);
13 System.out.print(" ");
14 }
15 }
16
17 void sort(String array[]) {
18 if (array == null || array.length == 0) {
19 return;
20 }
21 this.names = array;
22 this.length = array.length;
23 quickSort(0, length - 1);
24 }
25
26 void quickSort(int lowerIndex, int higherIndex) {
27 int i = lowerIndex;
28 int j = higherIndex;
29 String pivot = this.names[lowerIndex + (higherIndex - lowerIndex) / 2];
30
31 while (i <= j) {
32 while (this.names[i].compareToIgnoreCase(pivot) < 0) {
33 i++;
34 }
35
36 while (this.names[j].compareToIgnoreCase(pivot) > 0) {
37 j--;
38 }
39
40 if (i <= j) {
41 exchangeNames(i, j);
42 i++;
43 j--;
44 }
45 }
46 //call quickSort recursively
47 if (lowerIndex < j) {
48 quickSort(lowerIndex, j);
49 }
50 if (i < higherIndex) {
51 quickSort(i, higherIndex);
52 }
53 }
54
55 void exchangeNames(int i, int j) {
56 String temp = this.names[i];
57 this.names[i] = this.names[j];
58 this.names[j] = temp;
59 }
60}
1private static void quickSort(String[] a, int start, int end)
2{
3 // index for the "left-to-right scan"
4 int i = start;
5 // index for the "right-to-left scan"
6 int j = end;
7
8 // only examine arrays of 2 or more elements.
9 if (j - i >= 1)
10 {
11 // The pivot point of the sort method is arbitrarily set to the first element int the array.
12 String pivot = a[i];
13 // only scan between the two indexes, until they meet.
14 while (j > i)
15 {
16 // from the left, if the current element is lexicographically less than the (original)
17 // first element in the String array, move on. Stop advancing the counter when we reach
18 // the right or an element that is lexicographically greater than the pivot String.
19 while (a[i].compareTo(pivot) < 0 && i <= end && j > i){
20 i++;
21 }
22 // from the right, if the current element is lexicographically greater than the (original)
23 // first element in the String array, move on. Stop advancing the counter when we reach
24 // the left or an element that is lexicographically less than the pivot String.
25 while (a[j].compareTo(pivot) > 0 && j >= start && j >= i){
26 j--;
27 }
28 // check the two elements in the center, the last comparison before the scans cross.
29 if (j > i)
30 swap(a, i, j);
31 }
32 // At this point, the two scans have crossed each other in the center of the array and stop.
33 // The left partition and right partition contain the right groups of numbers but are not
34 // sorted themselves. The following recursive code sorts the left and right partitions.
35
36 // Swap the pivot point with the last element of the left partition.
37 swap(a, start, j);
38 // sort left partition
39 quickSort(a, start, j - 1);
40 // sort right partition
41 quickSort(a, j + 1, end);
42 }
43 }
44 /**
45 * This method facilitates the quickSort method's need to swap two elements, Towers of Hanoi style.
46 */
47 private static void swap(String[] a, int i, int j)
48 {
49 String temp = a[i];
50 a[i] = a[j];
51 a[j] = temp;
52 }