# 912. Sort an Array

## 03 May 912. Sort an Array

Given an array of integers `nums`, sort the array in ascending order.

Example 1:

```Input: nums = [5,2,3,1]
Output: [1,2,3,5]
```

Example 2:

```Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]
```

Constraints:

• `1 <= nums.length <= 5 * 104`
• `-5 * 104 <= nums[i] <= 5 * 104`

https://www.jianshu.com/p/bbbab7fa77a2

## 冒泡排序（Bubble Sort）

python

class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
for i in range(len(nums)):
for j in range(len(nums)-i-1):
if nums[j]> nums[j+1]:
nums[j], nums[j+1] = nums[j+1], nums[j]

return nums;

## 归并排序（Merge Sort）

class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
return self.merge(nums)

def merge(self, nums):
if(len(nums)<=1):
return nums

middle = int(len(nums)/2)
left = self.merge(nums[:middle])
right = self.merge(nums[middle:])
return self.mergeSort(left, right)

def mergeSort(self, left, right):
result = []
left_index =0
right_index=0

while left_index<len(left) and right_index <len(right):
if left[left_index]<=right[right_index]:
result.append(left[left_index])
left_index +=1

else:
result.append(right[right_index])
right_index+=1

result = result + left[left_index:]+right[right_index:]

return result

## 快速排序（Quick Sort）

class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
self.quickSort(nums, 0, len(nums)-1)
return nums

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

if(left<right):
pivot = self.partition(nums, left, right)
self.quickSort(nums, left, pivot-1)
self.quickSort(nums, pivot+1, right)
def partition(self, nums, left, right):
# print(left)
# print(right)
i = left-1
pivot = nums[right]

for j in range(left, right):
if nums[j]<=pivot:
i=i+1
nums[i], nums[j] = nums[j], nums[i]

nums[i+1], nums[right] = nums[right], nums[i+1]

return i+1