快速排序：排序不穩定。每當兩次分割的區域都均勻大小時，為最好情況。空間復雜度O(logn)~O(n)之間。時間復雜度一般和最好情況為O(nlogn)，最壞為O(n*n)。
package datasort;
//快排排序O(nlogn)
public class QuickSort {
public static void QuickSort(int[] array){
if(array != null){
quickSort(array, 0, array.length-1);
}
}
private static void quickSort(int[] array,int beg,int end){
if(beg >= end || array == null)
return;
int p = partition(array, beg, end);
quickSort(array, beg, p-1);
quickSort(array, p+1, end);
}
private static int partition(int[] array, int beg, int end) {
int first = array[beg];
int i = beg, j = end;
while (i < j) {
while (array[i] <= first && i < end) {
i++;
}
while (array[j] > first && j >= beg) {
j--;
}
if (i < j) {
System.out.print("array["+i+"],array["+j+"]("+array[i]+","+array[j]+")--->");
array[i] = array[i] ^ array[j];
array[j] = array[i] ^ array[j];
array[i] = array[i] ^ array[j];
System.out.println("array["+i+"],array["+j+"]("+array[i]+","+array[j]+")");
}
}
if (j != beg) {
array[j] = array[beg] ^ array[j];
array[beg] = array[beg] ^ array[j];
array[j] = array[beg] ^ array[j];
}
return j;
}
public static void main(String[] args) {
int[] a={28,4,36,2,65,14,55,17};
QuickSort(a);
System.out.println();
for(int i=0;i<a.length;i++){
System.out.print(a[i]+" ");
}
}
}