LintCode Q464 Sort Integers II quick in Python

  • Jinhai ZHOU
  • 4 Minutes
  • 2016年11月11日
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:
# @param {int[]} A an integer array
# @return nothing
def sortIntegers2(self, A):
# Write your code here
# quick sort
# 1708 ms
# 100% test cases passed.
self.quickSort(A, 0, len(A) - 1)
def quickSort(self, A, start, end):
if start >= end:
return
# set A[end] as pivot
mid = A[end]
left, right = start, end - 1
while left < right:
while left < right and A[left] < mid:
left += 1
while left < right and A[right] >= mid:
right -= 1
A[left], A[right] = A[right], A[left]
# left == right
if A[left] >= A[end]:
# keep left sub array smaller than right sub array
A[left], A[end] = A[end], A[left]
else:
left += 1
self.quickSort(A, start, left - 1)
self.quickSort(A, left + 1, end)
知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。