整数排序 II - quick_sort and merge_sort
https://www.lintcode.com/problem/464/?utm_source=sc-cheatsheet-cyc
描述
给一组整数,请将其在原地按照升序排序。使用归并排序,快速排序,堆排序或者任何其他 O(n log n) 的排序算法。
样例
例1:
输入:[3,2,1,4,5],输出:[1,2,3,4,5]。
例2:
输入:[2,3,1],输出:[1,2,3]。
为了对输入的数组进行排序,我们可以使用一个常见的排序算法——快速排序(Quick Sort)。以下是实现此算法的步骤:
确定一个基准点(pivot),可以选择数组的第一个元素。
将数组分成两个子数组,一个包含所有小于基准点的元素,另一个包含所有大于基准点的元素。
对这两个子数组递归地应用上述步骤。
最终将所有子数组合并起来得到排序后的数组。
```python
from typing import (
List,
)
class Solution:
"""
@param a: an integer array
@return: nothing
"""
def sort_integers2(self, a: List[int]):
# write your code here
self.quick_partition(a, 0, len(a)-1) #err: len(a)
def quick_partition(self, a: List[int], start:int, end:int):
if start >= end: # start > end也可以
return
pivot = a[(start + end) // 2]
left, right = start, end
while left <= right:
while left <= right and a[left] < pivot: #err: a[left] <= pivot 有大小才有必要换,等于没必要
left += 1
while left <= right and a[right] > pivot: #error: a[right] >= pivot
right -= 1
if left <= right:
a[left], a[right] = a[right], a[left]
left += 1 #err: missing 不要忘了这个
right -= 1 #err: missing
self.quick_partition(a, start, right)
self.quick_partition(a, left, end)
```
```python
from typing import (
List,
)
class Solution:
"""
@param a: an integer array
@return: nothing
"""
def sort_integers2(self, a: List[int]):
# write your code here
if not a:
return
temp = [0] * len(a) #Missing 因为需要合并,一定要有这个Helper array
self.merge_sort(a, 0, len(a) - 1, temp)
def merge_sort(self, a:List[int], start: int, end: int, temp: List[int]):
if start >= end: #递归一定要有程序出口,必须是>= 不能是> ,至少2个数才需要合并
return
mid = (start + end) // 2
self.merge_sort(a, start, mid, temp)
self.merge_sort(a, mid + 1, end, temp)
self.merge(a, start, end, temp)
def merge(self, a:List[int], start: int, end: int, temp: List[int]):
mid = (start + end) // 2
left, right = start, mid + 1
cur = start #ERROR!不能从0开始!!!!!!
while left <= mid or right <= end:
if left == mid + 1 and right <= end:
temp[cur] = a[right]
right += 1
elif right == end + 1 and left <= mid:
temp[cur] = a[left]
left += 1
elif a[left] > a[right]:
temp[cur] = a[right]
right += 1
else:
temp[cur] = a[left]
left += 1
cur += 1
for i in range(start, end+1):
a[i] = temp[i]
```
Last updated