leetcode-java/src/sort/QuickSort.java at master · fluency03/leetcode-java · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
/**
 * QuickSort: every time, it picks one element as a pivot and partitions the
 * array to two parts, where the elements of the first part before pivot are
 * always less or equal to the pivot, and the elements of the second part after.
 *
 * Worst Case Time Complexity: O(n^2).
 * Best and Average Case Time Complexity: O(nlogn).
 * Space Complexity: O(n).
 *
 * Different ways of picking the pivot:
 *
 * - Always pick first element as pivot.
 * - Always pick last element as pivot (implemented below)
 * - Pick a random element as pivot.
 * - Pick median as pivot.
 *
 */

importjava.util.Arrays;

publicclassQuickSort {
publicstaticvoidsortRecursively(int[] nums) {
quickSortRecursively(nums, 0, nums.length - 1);
 }

publicstaticvoidsortIteratively(int[] nums) {
if (nums.length == 0 || nums.length == 1) return;
quickSortIteratively(nums, 0, nums.length - 1);
 }

privatestaticvoidquickSortRecursively(int[] nums, intleft, intright) {
if (left >= right) return;

intp = partition(nums, left, right);
quickSortRecursively(nums, left, p - 1);
quickSortRecursively(nums, p + 1, right);
 }

privatestaticvoidquickSortIteratively(intarr[], intl, inth) {
intstack[] = newint[h-l+1];

inttop = -1;
stack[++top] = l;
stack[++top] = h;

while (top >= 0) {
h = stack[top--];
l = stack[top--];

intp = partition(arr, l, h);

if (p-1 > l) {
stack[++top] = l;
stack[++top] = p - 1;
 }

if (p+1 < h) {
stack[++top] = p + 1;
stack[++top] = h;
 }
 }
 }

privatestaticintpartition(int[] nums, intleft, intright) {
intpivot = nums[right];
inti = (left - 1);
for (intj = left; j < right; j++) {
if (nums[j] <= pivot) {
i++;
swap(nums, i, j);
 }
 }
swap(nums, i+1, right);
return (i + 1);
 }


privatestaticintpartition2(int[] nums, intleft, intright) {
intpivot = nums[right];
inti = left;
for (intj=left; j<right; j++) {
if (nums[j] <= pivot) {
swap(nums, i, j);
i++;
 }
 }
swap(nums, i, right);
returni;
 }

privatestaticintpartition3(int[] nums, intleft, intright) {
intpivot = nums[left];
inti = left+1;
intj = right;
while (true) {
while (i <= j && nums[i] <= pivot) i++;
while (i <= j && nums[j] > pivot) j--;
if (i >= j) break;
swap(nums, i, j);
 }
swap(nums, left, j);
returnj;
 }


privatestaticvoidswap(int[] nums, inti, intj) {
inttemp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
 }

publicstaticvoidmain(String[] args) {
int[] arr1 = {10, 3, 7, 5, 20, 15, 1};
QuickSort.sortIteratively(arr1);
System.out.println(Arrays.toString(arr1));

int[] arr2 = {};
QuickSort.sortIteratively(arr2);
System.out.println(Arrays.toString(arr2));

int[] arr3 = {10};
QuickSort.sortIteratively(arr3);
System.out.println(Arrays.toString(arr3));
 }
}