1 package Sort; 2  3 import org.junit.Test; 4  5 // 随机快排算法 6 public class RandQuickSort { 7  8     // 交换数组中的两个元素 9     public void exchange(int[] array, int index1, int index2) {10         int tmp = array[index1];11         array[index1] = array[index2];12         array[index2] = tmp;13     }14 15     // 分区函数,返回分区的元素下标16     public int partition(int[] array, int start, int end) {17         if (start >= end)18             return -1;19         int length = end - start + 1;20         // 产生一个[start.. end]范围内的伪随机下标21         int pivotIndex = start + (int) Math.floor(Math.random() * length);22         System.out.println("选取的主元下标为: " + pivotIndex);23         // 选取array[pivotIndex]作为主元24         exchange(array, pivotIndex, end);25         int i = start;26         int j = end - 1;27         while (i < j) {28             // 从数组头部开始,依次找到数组中大于主元的元素29             while (i <= end && array[i] < array[end])30                 ++i;31             // 从数组尾部开始,依次找到数组中小于主元的元素32             while (j >= start && array[j] >= array[end])33                 --j;34             if (i < j) {35                 exchange(array, i, j);36                 ++i;37                 --j;38             }39         }40 41         if (i > j) {42             exchange(array, i, end);43             return i;44         }45         // i == j的两种情况46         else if (array[i] > array[end]) {47             exchange(array, i, end);48             return i;49         } else {50             exchange(array, i + 1, end);51             return i + 1;52         }53     }54 55     // 真正的随机快速排序算法要开始了56     public void quickSort(int[] array, int start, int end) {57         if (start < end) {58             int middle = partition(array, start, end);59             quickSort(array, start, middle - 1);60             quickSort(array, middle + 1, end);61         }62     }63 64     @Test65     public void test() {66         int[] array = { 8, 2, -1, 4, 9, -5, 3, 6, 25, 5, 10, -3, 30, 21, 13 };67         quickSort(array, 0, array.length - 1);68         Array.print(array);69     }70 }