选择排序

对每一个nums[i], 寻找 $range(i,n)$ 范围内比nums[i]大的数，并与之交换
以此类推，位置 i 处就是第i 小的数

两次for循环，时间复杂度为 $O(n^2)$

def selection_sort(nums):
    n = len(nums)
    for i in range(n):
        for j in range(i, n):
            if nums[i] > nums[j]:
                nums[i], nums[j] = nums[j], nums[i]
    return nums

==冒泡排序==

最坏的情况是: 原始的nums是倒序，从倒序转顺序
对每一个nums[i], 需要比较n-i次相邻元素

两次for循环，时间复杂度为 $O(n^2)$

class Solution(object):
    def sortArray(self, nums):
        n=len(nums)
        for i in range(n):
            for j in range(1,n-i):
                if nums[j]<nums[j-1]:
                    nums[j],nums[j-1]=nums[j-1],nums[j]
        return nums

==插入排序==

对每一个nums[i], 将其插入到符合大小顺序的位置处
随着i的增加，需要比较的次数也增加。比较时，从最近的相邻元素开始，倒序比

时间复杂度为 $O(n^2)$

class Solution(object):
    def sortArray(self, nums):
        n=len(nums)
        for i in range(1,n):
            while i>0 and nums[i]<nums[i-1]:
                nums[i-1],nums[i]=nums[i],nums[i-1]
                i-=1
        return nums

或者

class Solution(object):
    def sortArray(self, nums):
        n=len(nums)
        for i in range(1,n):
            for j in range(i-1,-1,-1):
                if nums[j]>nums[i]:
                    nums[j],nums[i]=nums[i],nums[j]
                    i-=1
        return nums

希尔排序（了解）

希尔排序是插入排序的优化，通过gap减少排序过程中交换的次数

时间复杂度为 $O(n^2)$

class Solution(object):
    def sortArray(self, nums):
        n=len(nums)
        gap=n//2
        while gap:
            for i in range(gap,n):
                while i-gap>=0 and nums[i]<nums[i-gap]:            
                    nums[i-gap],nums[i]=nums[i],nums[i-gap]
                    i-=gap
            gap=gap//2
        return nums

==归并排序==

归并排序是理解递归方法的一个很好的例子

不要跳进递归里面去（~~跳进去没任何用处，反而会更混乱~~ ）。归并排序就是先把数组分左右两个子数组并对子数组排序，然后合并
递归是逐步缩小子问题，主要是理解函数的作用及返回的内容
- sortArray() 函数的作用是排序，返回排好序的列表
  - 如 [7,5,3] -> 返回[3,5,7]
- merge() 函数的作用是对两个有序数组按照由小到大的顺序合并
  - 如 left=[2,4,6],right=[3,5,7]-> 合并后返回[2,3,4,5,6,7]

时间复杂度为 $O(n^2)$，空间复杂度为 $O(n)$。参考漫谈经典排序算法

class Solution(object):
    # 函数的作用是排序，不要跳进递归中
    def sortArray(self, nums):
        if len(nums)<=1: return nums
        mid=len(nums)//2
        # 分成有序的左右两个子列
        left=self.sortArray(nums[:mid])
        right=self.sortArray(nums[mid:])
        # 合并
        return self.merge(left,right)

    # 按照大小顺序，合并两个子数组
    def merge(self,left,right):
        res=[]
        while len(left)>0 and len(right)>0:
            if left[0]<right[0]:
                res.append(left.pop(0))
            else:
                res.append(right.pop(0))
        # 从while条件中跳出后，左右子数组中可能仍有未pop出的元素
        # 所以将其连接到res后面即可
        res+=left
        res+=right
        return res

==快速排序==

将列表的第一个（或最后一个）元素设为pivot，然后在range(1,len(nums))中，小于等于pivot的元素放l，大于pivot的元素放r
对l和r列表分别递归调用排序函数，并通过left+[pivot]+right 将其连起开，返回最终结果
注意递归终止的条件及特判if len(nums)<=0:return nums

时间复杂度为 $O(n^2)$

class Solution:
    def sortArray(self, nums):
        # 递归终止的条件及特判
        if len(nums)<=0:return nums
        # 将列表的第一个元素设为pivot，后面的元素中，小于pivot的在左，大于pivot的在右
        l=[]
        r=[]
        pivot=nums[0]
        for i in range(1,len(nums)):
            if nums[i]<=pivot:
                l.append(nums[i])
            else:
                r.append(nums[i])
        left=self.sortArray(l)
        right=self.sortArray(r)
        return left+[pivot]+right