高端的平面设计网站/日本进口yamawa

题目描述：

给一组整数，按照升序排序。使用归并排序，快速排序，堆排序或者任何其他 O(n log n) 的排序算法。

您在真实的面试中是否遇到过这个题？

Yes

样例

给出 [3, 2, 1, 4, 5], 排序后的结果为 [1, 2, 3, 4, 5]。

题目分析：

给一组整数，按照升序排序。使用归并排序，快速排序，堆排序或者任何其他 O(n log n) 的排序算法。

快速排序，递归将大于key值和小于key值的分为两部分，直到每个子数组长度为1，不可再分。

源码：

class Solution:

# @param {int[]} A an integer array

# @return nothing

def sortIntegers2(self, A):

# Write your code here

if A is None: return A

n = len(A)

if n == 1 or n == 0: return A

return self.quickSort(A,0,n-1)

def quickSort(self,List,left,right):

if left >= right:

return List

key = List[left]

low = left

high = right

while left < right:

while left < right and List[right] >= key:

right -= 1

List[left],List[right] = List[right],List[left]

while left < right and List[left] <= key:

left += 1

List[right],List[left] = List[left],List[right]

self.quickSort(List,low,left-1)

self.quickSort(List,left+1,high)

return List