forked from kamyu104/LeetCode-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 0
/
sort-an-array.py
72 lines (64 loc) · 2.35 KB
/
sort-an-array.py
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
# Time: O(nlogn)
# Space: O(n)
# merge sort solution
class Solution(object):
def sortArray(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
def mergeSort(start, end, nums):
if end - start <= 1:
return
mid = start + (end - start) // 2
mergeSort(start, mid, nums)
mergeSort(mid, end, nums)
right = mid
tmp = []
for left in xrange(start, mid):
while right < end and nums[right] < nums[left]:
tmp.append(nums[right])
right += 1
tmp.append(nums[left])
nums[start:start+len(tmp)] = tmp
mergeSort(0, len(nums), nums)
return nums
# Time: O(nlogn), on average
# Space: O(logn)
import random
# quick sort solution
class Solution2(object):
def sortArray(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
def kthElement(nums, left, k, right, compare):
def PartitionAroundPivot(left, right, pivot_idx, nums, compare):
new_pivot_idx = left
nums[pivot_idx], nums[right] = nums[right], nums[pivot_idx]
for i in xrange(left, right):
if compare(nums[i], nums[right]):
nums[i], nums[new_pivot_idx] = nums[new_pivot_idx], nums[i]
new_pivot_idx += 1
nums[right], nums[new_pivot_idx] = nums[new_pivot_idx], nums[right]
return new_pivot_idx
right -= 1
while left <= right:
pivot_idx = random.randint(left, right)
new_pivot_idx = PartitionAroundPivot(left, right, pivot_idx, nums, compare)
if new_pivot_idx == k:
return
elif new_pivot_idx > k:
right = new_pivot_idx - 1
else: # new_pivot_idx < k.
left = new_pivot_idx + 1
def quickSort(start, end, nums):
if end - start <= 1:
return
mid = start + (end - start) / 2
kthElement(nums, start, mid, end, lambda a, b: a < b)
quickSort(start, mid, nums)
quickSort(mid, end, nums)
quickSort(0, len(nums), nums)
return nums