1+ import java .util .Arrays ;
2+
3+ public class QuickSort {
4+
5+ private static void quickSort (int [] nums ) {
6+ quickSort (nums , 0 , nums .length - 1 );
7+ }
8+
9+ private static void quickSort (int [] nums , int low , int high ) {
10+ if (low >= high ) {
11+ return ;
12+ }
13+ int [] p = partition (nums , low , high );
14+ quickSort (nums , low , p [0 ] - 1 );
15+ quickSort (nums , p [0 ] + 1 , high );
16+ }
17+
18+ private static int [] partition (int [] nums , int low , int high ) {
19+ int less = low - 1 , more = high ;
20+
21+ while (low < more ) {
22+ if (nums [low ] < nums [high ]) {
23+ swap (nums , ++less , low ++);
24+ } else if (nums [low ] > nums [high ]) {
25+ swap (nums , --more , low );
26+ } else {
27+ ++low ;
28+ }
29+ }
30+ swap (nums , more , high );
31+ return new int [] {less + 1 , more };
32+ }
33+
34+ private static void swap (int [] nums , int i , int j ) {
35+ int t = nums [i ];
36+ nums [i ] = nums [j ];
37+ nums [j ] = t ;
38+ }
39+
40+ public static void main (String [] args ) {
41+ int [] nums = {1 , 2 , 7 , 4 , 5 , 3 };
42+ quickSort (nums );
43+ System .out .println (Arrays .toString (nums ));
44+ }
45+ }
0 commit comments