随机快排算法
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;
11 array = array;
12 array = 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 // 产生一个范围内的伪随机下标
21 int pivotIndex = start + (int) Math.floor(Math.random() * length);
22 System.out.println("选取的主元下标为: " + pivotIndex);
23 // 选取array作为主元
24 exchange(array, pivotIndex, end);
25 int i = start;
26 int j = end - 1;
27 while (i < j) {
28 // 从数组头部开始,依次找到数组中大于主元的元素
29 while (i <= end && array < array)
30 ++i;
31 // 从数组尾部开始,依次找到数组中小于主元的元素
32 while (j >= start && array >= array)
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 > array) {
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 @Test
65 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 }
页:
[1]