代码实现

1
2void setup() {
3int array[] = new int[6];
4for (int i = 0; i < array.length; i++)
5array[i] = int(random(-128, 128));
6
7// 115 80 -36 107 -57 107
8quickSort(array);
9// -57 -36 80 107 107 115
10}
11
12// 
13// sort the array
14// 
15// @parama array to be sorted
16// @paramstart left boundary
17// @paramend right boundary
18//
19static void quickSort(int[] arr, int begin, int end) {
20if (begin >= end) 
21return;
22
23int partitionIndex = partition(arr, begin, end);
24quickSort(arr, begin, partitionIndex - 1);
25quickSort(arr, partitionIndex + 1, end);
26}
27
28static void quickSort(int[] arr) {
29quickSort(arr, 0, arr.length - 1);
30}
31
32//
33// find where to partition
34//
35// @parama array to be sorted
36// @paramstart left boundary
37// @paramend right boundary
38// @return partition index
39// 
40static int partition(int[] arr, int begin, int end) {
41// start || middle || end
42int pivot = arr[end];
43int i = begin;
44
45for (int j = begin; j < end; j++) {
46// swap if arr[j] <= pivot
47if (arr[j] <= pivot) {
48int swapTemp = arr[i];
49arr[i] = arr[j];
50arr[j] = swapTemp;
51i++;
52}
53}
54
55// swap pivot with i
56int swapTemp = arr[i];
57arr[i] = arr[end];
58arr[end] = swapTemp;
59
60return i;
61}
62