Quick Sort
Sort an integer array in nondecreasing order by implementing Quick Sort. Do not use a built-in sort.
Work through the cases
3 examplesInput notation
One nonempty line of space-separated integers; at most 1000 values.Expected result
The sorted values, space-separated.Case 1
Input
8 3 5 3 -1
Expected output
-1 3 3 5 8
Case 2
Input
2 1
Expected output
1 2
Case 3
Input
0 -2 0 -1
Expected output
-2 -1 0 0
These notes use simplified input/output notation. The linked platform defines the method signature and judge format.
FROM IDEA TO IMPLEMENTATION
Understand the approach.
Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.
n ≤ 5 × 10^4 needs an O(nlog n) sort; a naive quadratic pass is too slow. Three-way quicksort partitions around a random pivot into <, =, and > segments so duplicate keys do not degenerate, then recurses on the two sides.
class Solution {
private int[] nums;
public int[] sortArray(int[] nums) {
this.nums = nums;
quikcSort(0, nums.length - 1);
return nums;
}
private void quikcSort(int l, int r) {
if (l >= r) {
return;
}
int x = nums[(l + r) >> 1];
int i = l - 1, j = r + 1;
while (i < j) {
while (nums[++i] < x) {
}
while (nums[--j] > x) {
}
if (i < j) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
}
quikcSort(l, j);
quikcSort(j + 1, r);
}
}Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.
Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.