Array
Divide and Conquer
Bucket Sort
Counting Sort
Radix Sort
Sorting
Heap (Priority Queue)
Merge Sort
Description
Given an array of integers nums
, sort the array in ascending order and return it.
You must solve the problem without using any built-in functions in O(nlog(n))
time complexity and with the smallest space complexity possible.
Example 1:
Input: nums = [5,2,3,1]
Output: [1,2,3,5]
Explanation: After sorting the array, the positions of some numbers are not changed (for example, 2 and 3), while the positions of other numbers are changed (for example, 1 and 5).
Example 2:
Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]
Explanation: Note that the values of nums are not necessairly unique.
Constraints:
1 <= nums.length <= 5 * 104
-5 * 104 <= nums[i] <= 5 * 104
Solutions
Solution 1
Python3 Java C++ Go TypeScript JavaScript None Kotlin
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 class Solution :
def sortArray ( self , nums : List [ int ]) -> List [ int ]:
def quick_sort ( l , r ):
if l >= r :
return
x = nums [ randint ( l , r )]
i , j , k = l - 1 , r + 1 , l
while k < j :
if nums [ k ] < x :
nums [ i + 1 ], nums [ k ] = nums [ k ], nums [ i + 1 ]
i , k = i + 1 , k + 1
elif nums [ k ] > x :
j -= 1
nums [ j ], nums [ k ] = nums [ k ], nums [ j ]
else :
k = k + 1
quick_sort ( l , i )
quick_sort ( j , r )
quick_sort ( 0 , len ( nums ) - 1 )
return nums
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 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 );
}
}
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 class Solution {
public :
vector < int > sortArray ( vector < int >& nums ) {
function < void ( int , int ) > quick_sort = [ & ]( int l , int r ) {
if ( l >= r ) {
return ;
}
int i = l - 1 , j = r + 1 ;
int x = nums [( l + r ) >> 1 ];
while ( i < j ) {
while ( nums [ ++ i ] < x ) {
}
while ( nums [ -- j ] > x ) {
}
if ( i < j ) {
swap ( nums [ i ], nums [ j ]);
}
}
quick_sort ( l , j );
quick_sort ( j + 1 , r );
};
quick_sort ( 0 , nums . size () - 1 );
return nums ;
}
};
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 func sortArray ( nums [] int ) [] int {
quickSort ( nums , 0 , len ( nums ) - 1 )
return nums
}
func quickSort ( nums [] int , l , r int ) {
if l >= r {
return
}
i , j := l - 1 , r + 1
x := nums [( l + r ) >> 1 ]
for i < j {
for {
i ++
if nums [ i ] >= x {
break
}
}
for {
j --
if nums [ j ] <= x {
break
}
}
if i < j {
nums [ i ], nums [ j ] = nums [ j ], nums [ i ]
}
}
quickSort ( nums , l , j )
quickSort ( nums , j + 1 , r )
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 function sortArray ( nums : number []) : number [] {
function quickSort ( l : number , r : number ) {
if ( l >= r ) {
return ;
}
let i = l - 1 ;
let j = r + 1 ;
const x = nums [( l + r ) >> 1 ];
while ( i < j ) {
while ( nums [ ++ i ] < x );
while ( nums [ -- j ] > x );
if ( i < j ) {
[ nums [ i ], nums [ j ]] = [ nums [ j ], nums [ i ]];
}
}
quickSort ( l , j );
quickSort ( j + 1 , r );
}
const n = nums . length ;
quickSort ( 0 , n - 1 );
return nums ;
}
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 /**
* @param {number[]} nums
* @return {number[]}
*/
var sortArray = function ( nums ) {
function quickSort ( l , r ) {
if ( l >= r ) {
return ;
}
let i = l - 1 ;
let j = r + 1 ;
const x = nums [( l + r ) >> 1 ];
while ( i < j ) {
while ( nums [ ++ i ] < x );
while ( nums [ -- j ] > x );
if ( i < j ) {
[ nums [ i ], nums [ j ]] = [ nums [ j ], nums [ i ]];
}
}
quickSort ( l , j );
quickSort ( j + 1 , r );
}
const n = nums . length ;
quickSort ( 0 , n - 1 );
return nums ;
};
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 impl Solution {
pub fn sort_array ( mut nums : Vec < i32 > ) -> Vec < i32 > {
let n = nums . len ();
Self :: quick_sort ( & mut nums , 0 , n - 1 );
return nums ;
}
fn quick_sort ( nums : & mut Vec < i32 > , left : usize , right : usize ) {
if left >= right {
return ;
}
let mut i = left as i32 - 1 ;
let mut j = right as i32 + 1 ;
let pivot = nums [ left ];
while i < j {
loop {
i += 1 ;
if nums [ i as usize ] >= pivot {
break ;
}
}
loop {
j -= 1 ;
if nums [ j as usize ] <= pivot {
break ;
}
}
if i < j {
nums . swap ( i as usize , j as usize );
}
}
Self :: quick_sort ( nums , left , j as usize );
Self :: quick_sort ( nums , j as usize + 1 , right );
}
}
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 class Solution {
fun sortArray ( nums : IntArray ): IntArray {
fun quickSort ( left : Int , right : Int ) {
if ( left >= right ) {
return
}
var i = left - 1
var j = right + 1
val pivot = nums [ left ]
while ( i < j ) {
while ( nums [++ i ] < pivot ) ;
while ( nums [-- j ] > pivot ) ;
if ( i < j ) {
val temp = nums [ i ]
nums [ i ] = nums [ j ]
nums [ j ] = temp
}
}
quickSort ( left , j )
quickSort ( j + 1 , right )
}
quickSort ( 0 , nums . size - 1 )
return nums
}
}
Solution 2
Python3 Java C++ Go TypeScript JavaScript
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 class Solution :
def sortArray ( self , nums : List [ int ]) -> List [ int ]:
def merge_sort ( l , r ):
if l >= r :
return
mid = ( l + r ) >> 1
merge_sort ( l , mid )
merge_sort ( mid + 1 , r )
i , j = l , mid + 1
tmp = []
while i <= mid and j <= r :
if nums [ i ] <= nums [ j ]:
tmp . append ( nums [ i ])
i += 1
else :
tmp . append ( nums [ j ])
j += 1
if i <= mid :
tmp . extend ( nums [ i : mid + 1 ])
if j <= r :
tmp . extend ( nums [ j : r + 1 ])
for i in range ( l , r + 1 ):
nums [ i ] = tmp [ i - l ]
merge_sort ( 0 , len ( nums ) - 1 )
return nums
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 class Solution {
private int [] nums ;
public int [] sortArray ( int [] nums ) {
this . nums = nums ;
quickSort ( 0 , nums . length - 1 );
return nums ;
}
private void quickSort ( int l , int r ) {
if ( l >= r ) {
return ;
}
int i = l - 1 , j = r + 1 , k = l ;
int x = nums [ ( l + r ) >> 1 ] ;
while ( k < j ) {
if ( nums [ k ] < x ) {
swap ( ++ i , k ++ );
} else if ( nums [ k ] > x ) {
swap ( -- j , k );
} else {
++ k ;
}
}
quickSort ( l , i );
quickSort ( j , r );
}
private void swap ( int i , int j ) {
int t = nums [ i ] ;
nums [ i ] = nums [ j ] ;
nums [ j ] = t ;
}
}
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 class Solution {
public :
vector < int > sortArray ( vector < int >& nums ) {
function < void ( int , int ) > merge_sort = [ & ]( int l , int r ) {
if ( l >= r ) {
return ;
}
int mid = ( l + r ) >> 1 ;
merge_sort ( l , mid );
merge_sort ( mid + 1 , r );
int i = l , j = mid + 1 , k = 0 ;
int tmp [ r - l + 1 ];
while ( i <= mid && j <= r ) {
if ( nums [ i ] <= nums [ j ]) {
tmp [ k ++ ] = nums [ i ++ ];
} else {
tmp [ k ++ ] = nums [ j ++ ];
}
}
while ( i <= mid ) {
tmp [ k ++ ] = nums [ i ++ ];
}
while ( j <= r ) {
tmp [ k ++ ] = nums [ j ++ ];
}
for ( i = l ; i <= r ; ++ i ) {
nums [ i ] = tmp [ i - l ];
}
};
merge_sort ( 0 , nums . size () - 1 );
return nums ;
}
};
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 func sortArray ( nums [] int ) [] int {
mergeSort ( nums , 0 , len ( nums ) - 1 )
return nums
}
func mergeSort ( nums [] int , l , r int ) {
if l >= r {
return
}
mid := ( l + r ) >> 1
mergeSort ( nums , l , mid )
mergeSort ( nums , mid + 1 , r )
i , j , k := l , mid + 1 , 0
tmp := make ([] int , r - l + 1 )
for i <= mid && j <= r {
if nums [ i ] <= nums [ j ] {
tmp [ k ] = nums [ i ]
i ++
} else {
tmp [ k ] = nums [ j ]
j ++
}
k ++
}
for ; i <= mid ; i ++ {
tmp [ k ] = nums [ i ]
k ++
}
for ; j <= r ; j ++ {
tmp [ k ] = nums [ j ]
k ++
}
for i = l ; i <= r ; i ++ {
nums [ i ] = tmp [ i - l ]
}
}
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 function sortArray ( nums : number []) : number [] {
function mergetSort ( l : number , r : number ) {
if ( l >= r ) {
return ;
}
const mid = ( l + r ) >> 1 ;
mergetSort ( l , mid );
mergetSort ( mid + 1 , r );
let [ i , j , k ] = [ l , mid + 1 , 0 ];
while ( i <= mid && j <= r ) {
if ( nums [ i ] <= nums [ j ]) {
tmp [ k ++ ] = nums [ i ++ ];
} else {
tmp [ k ++ ] = nums [ j ++ ];
}
}
while ( i <= mid ) {
tmp [ k ++ ] = nums [ i ++ ];
}
while ( j <= r ) {
tmp [ k ++ ] = nums [ j ++ ];
}
for ( i = l , j = 0 ; i <= r ; ++ i , ++ j ) {
nums [ i ] = tmp [ j ];
}
}
const n = nums . length ;
let tmp = new Array ( n ). fill ( 0 );
mergetSort ( 0 , n - 1 );
return nums ;
}
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 /**
* @param {number[]} nums
* @return {number[]}
*/
var sortArray = function ( nums ) {
function mergetSort ( l , r ) {
if ( l >= r ) {
return ;
}
const mid = ( l + r ) >> 1 ;
mergetSort ( l , mid );
mergetSort ( mid + 1 , r );
let [ i , j , k ] = [ l , mid + 1 , 0 ];
while ( i <= mid && j <= r ) {
if ( nums [ i ] <= nums [ j ]) {
tmp [ k ++ ] = nums [ i ++ ];
} else {
tmp [ k ++ ] = nums [ j ++ ];
}
}
while ( i <= mid ) {
tmp [ k ++ ] = nums [ i ++ ];
}
while ( j <= r ) {
tmp [ k ++ ] = nums [ j ++ ];
}
for ( i = l , j = 0 ; i <= r ; ++ i , ++ j ) {
nums [ i ] = tmp [ j ];
}
}
const n = nums . length ;
let tmp = new Array ( n ). fill ( 0 );
mergetSort ( 0 , n - 1 );
return nums ;
};
Solution 3
GitHub