package Sort;import java.util.Arrays;public class QuickSort {

 public static <T extends Comparable<? super T>> void sort(T arr[],
 int first, int last) {
 T temp;
 int pivot;

 if (first - last <= 1) 
 return;

  else if (first - last == 2) {
 if (arr[last - 1].compareTo(arr[first]) < 0) {
 temp = arr[first];
 arr[first] = arr[last - 1];
 arr[last - 1] = temp;

 }
 return;
 }

 else {
 pivot = quickSort(arr, first, last);
 sort(arr,first,pivot);
 sort(arr,pivot+1,last);
 }
 } public static <T extends Comparable<? super T>> int quickSort(T arr[],
int first, int last) { int mid, scanUp, scanDown;
T pivot, temp; if (first == last)
return last; if (first == last - 1)
return first; else {
mid = (first + last) / 2;
pivot = arr[mid];

arr[mid] = arr[first];
arr[first] = pivot;

scanUp = first + 1;
scanDown = last - 1;
for (;;) {
while (scanUp <= scanDown && arr[scanUp].compareTo(pivot) < 0) 
scanUp++;

while (pivot.compareTo(arr[scanDown]) < 0) 
scanDown--;

if (scanUp >= scanDown)
break;
temp = arr[scanUp];
arr[scanUp] = arr[scanDown];
arr[scanDown] = temp;
scanUp++;
scanDown--;
}
arr[first] = arr[scanDown];
arr[scanDown] = pivot;
return scanDown;
}
}
public static void main(String[] args) {
String[] strArr = { "dog", "tiger", "cat", "ant", "snake", "pig",
"cow", "zhangxin" };
Integer [] arr={9,8,7,6,5,4,3,2,1};
QuickSort.quickSort(arr, 0, strArr.length);

for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+"  ");
}
}
}