时间复杂度
- 最好情况
- 最坏情况
空间复杂度: 需不需要开辟新的空间
排序方式：in-place还是不是in - place
排序稳定性: 也就是之前顺序的东西在排序之后是否还顺序

冒泡排序

前面一个数和后面一个比，如果前面的数比后面的大(或者小)，就交换他们两个
- 这样交换一次之后的最后一个数就是所有数字里面的最大数
- 也就相当于最大的数像冒泡一样冒出来了，第一轮过后，第二轮可以直接冒倒数第二个数，也就是说每一轮的内循环次数可以逐渐减少
需要重复n次（但是每次对越来越少的数字进行上述操作），以确保所有的交换都已经完毕了。

增加了一个flag的判断，如果在一轮里面没有任何交换产生，那就说明所有的元素都已经排序完毕了（因为如果还有数字往上冒必然会在前面有交换

这样如果是正序排列的话，可以直接跳出循环，不用进行比较，时间复杂度是n



def bubbleSort(num):
    n = len(num)
    for j in range(1, n):
        flag = True  # 如果在这轮没有任何交换，就可以说明排序已经完成了
        for i in range(n - j):
            if num[i] > num[i + 1]:
                temp = num[i]
                num[i] = num[i + 1]
                num[i + 1] = temp
                flag = False
        if flag is True:
            break
    return num

时间复杂度：
- 当正序排列的时候，因为可以直接跳出循环，所以只需要遍历一次所有的数保证他们排列正常，所以时间复杂度是n
- 当倒序排列的时候，需要把所有都移动一遍，所以时间复杂度是 n ^ 2
- 平均的复杂度是n方
空间复杂度：
- 因为交换只需要一个额外的temp来储存临时变量，空间复杂度是1
in-place：是的
稳定性：稳定，因为一次换过来的东西就不动了，在判断大小的时候也是判断的大于而不是大于等于，也就是说前面换到后面的大数永远会在后面的数的前面
- 比如[0, 8, 1, 8, 2]。首先会把第一个8换到第二个8的前面，因为判断条件没有等于，所以越不过去。

选择排序

从所有元素中找到最小（或者最大）元素，然后放到数组的第一个（也就是和数组的第一个交换位置），然后这个就算是固定住了
然后从第二个到最后一个中选择现在最小的，和数组的第二个交换位置，前两个就固定住了

以此类推



def SelectSort(nums):
    n = len(nums)
    for i in range(n):
        Min = float("inf")
        index = None
        for j in range(i, n):
            if nums[j] < Min:
                Min = nums[j]
                index = j
        if index != i:  # 这样可以减少一些根本不用交换的情况，下一个位置上本来就是最小的
            temp = nums[i]
            nums[i] = nums[index]
            nums[index] = temp
    return nums

时间复杂度：
- 最好情况和最坏情况都不能避免走两个循环，都是n ^ 2
空间复杂度: 1, 来储存temp的值和暂时的最大值的变量
in-place：是的，换位置就可以，不需要单拿出来
稳定：
- 不稳定，因为在交换位置的时候，并不知道现在的东西被交换到哪里去了
- 比如：[3, 3, 0, 9]，当0和3交换位置的时候，把第一个3交换到第二个3后面去了

插入排序

在第1轮，认为第1个已经排好序了，然后从第二个开始拿出来，把它放在排好序的里面的合适的位置上
从第二轮开始依次类推，所以还是两个循环
在第i轮里面，前i个元素已经是排好序的了
在插入的过程当中，需要考虑如果把所有的需要移动的数字的坐标都移动一位。这时候比较有效的考虑方法是从最右边开始往左边移动，只要右边的数比现在的temp要大，这一位（实际上这一位指的是j - 1，因为j是移动之后的坐标）就需要移动。移动之后再减1
在所有的都移动结束之后，如果j这个位置和i的位置不一样，就说明发生了插入，那么就是nums[j] = 被插入的数字temp



def InsertSort(nums):
    n = len(nums)
    for i in range(1, n):
        temp = nums[i]
        j = i
        while j > 0 and temp < nums[j - 1]:
            nums[j] = nums[j - 1]
            j -= 1
        if j != i:
            nums[j] = temp
    return nums

时间复杂度
- 最好的时候，不需要插入，最大值直接放在了前面排好序的最右边，也就是没有内循环，n
- 最差的时候，反序，需要全都循环一遍 n2
空间复杂度 1
in-place
稳定性：稳定，因为如果是[2, 0, 0, 1]，第一个0先插入变成了[0_1, 2, 0_2, 1]，然后插入第二个0的时候因为比较的时候没有比等于，所以会变成[0_1, 0_2, 2, 1]

希尔排序

选择一个序列来对这个数组进行排序，比如如果是10个数，可以是5 2 1这样的，最后一个一定是1（设定的公式是3xn + 1不知道为什么）
然后根据这个序列把数组分成这个序列个数的组，对每组的数字进行插入排序。比如用5分成两份，那就要进行5次，两个之间的排序
一共进行的排序次数是和序列的个数有关的

def ShellSort(nums):
    n = len(nums)
    gap = 1
    while gap < n / 3:
        gap = gap * 3 + 1  # 一个神奇的选择方法，也不知道为什么但是确实很好用
    while gap > 0:
        for i in range(gap, n):
            # 这里执行的是插入排序，和上面的插入排序一样，只不过每次跳gap个了
            temp = nums[i]
            j = i
            while j > 0 and temp < nums[j - gap]:
                nums[j] = nums[j - gap]
                j -= gap
            if j != i:
                nums[j] = temp
        # 直接int就可以向下取整，因为加1并不影响取整效果
        gap = int(gap / 3)
    return nums

关于增量，不同的增量对时间复杂度有不同的影响
- 目前应用最多的是 Knuth增量:1,4,13,40,…,(3^k - 1)/2，也就是代码里面的这个增量
- 这时候的复杂度是 N^（3/2）
时间复杂度：
- 根据不同的步长不同而有所差别，还有的步长还没计算出来复杂度
- 如果是原版的，也就是原长度一直除2的话
  - 最好效果：n，也就是不需要内循环
  - 最烂效果：n^2
空间复杂度 1
in-place
不稳定，因为很有可能因为分组的不同把两个数的顺序颠倒，比如两组的后面都是3，但是第一组的前一个是2，第二组的前一个是4，这样就把第二个3换到前面去了

归并排序

归并排序是分治法的一个典型的应用，可以把有序的子列合并，然后得到新的有序的子列
比较方法
- 首先比较两个子列的初始值a[i]和b[j]，把比较小的那个（比如i）放进新的list[k]里面，并且让i和k分别加一，然后继续比较i和j，然后结果放进k里。
- 如果有一个子列已经取完了，那么可以直接把另一个里面的剩余元素复制到新的list的最后
- 因为现在使用的子列已经是排好序的了，所以可以使用这种比较方法。初始状态认为每一个数字都是一个单独的子列，所以往上合并的时候都是有序的了
实现：
- 申请一个新的空间，大小是两个子列的大小之和
- 两个指针分别从初始位置开始
- 根据上面的方法移动指针
- 在实现的过程中需要用到拆分和合并两个步骤

def MergeSort(nums):
    n = len(nums)
    if n < 2:
        return nums
    middle = int(n / 2)
    L, R = nums[:middle], nums[middle:]
    return merge(MergeSort(L), MergeSort(R))


def merge(L, R):
    M = []
    i, j = 0, 0
    while L and R:
        if L[0] <= R[0]:
            M.append(L.pop(0))
        else:
            M.append(R.pop(0))
    while L:
        M.append(L.pop(0))
    while R:
        M.append(R.pop(0))
    return M

在python实现中，其实并不需要用坐标表示，可以直接用pop把每次需要取的东西取出来
时间复杂度
- 无论最好或者最坏的情况都需要把所有东西都比较一回，一共是logn层，每层的实际内容都是n个，所以最终的复杂度是nlog(n)。这样看出来归并排序对于最好和最坏的情况比较稳定
空间复杂度：
- 临时数组的时间n + recursive的时候的空间logn = O(n)
out of place
稳定性：稳定，因为在左边的一定是在左边

快速排序

选取数组的第一个作为标准，然后把比这个标准小的都放在左边，比标准大的都放在右边
然后再分别对左右进行快速排序
注意，在不是python的情况下，需要通过角标互换的方法得到结果
实现
- 选择一个基准piv
- 数列最左边的标记为左标记，最右边的标记是右标记
- 将左标记向右标记移动
- 如果左标记的值超过了piv的值，停止
- 移动右标记
- 当右标记小于piv的时候，停止移动
- 当左右标记都停止的时候，交换两个数字
- 然后继续移动，直到两个标记碰到一起，这时候把这个值和piv交换

def QuickSort(nums, s, e):
    if s < e:
        i, j = s, e
        piv = nums[i]
        index = i
        while i < j:
            while (i < j) and nums[j] >= piv:
                j -= 1
            while (i < j) and nums[i] <= piv:
                i += 1
            nums[i], nums[j] = nums[j], nums[i]
        nums[i], nums[index] = piv, nums[i]

        QuickSort(nums, s, i - 1)
        QuickSort(nums, j + 1, e)
    return nums

def QuickSort_1(nums):
    n = len(nums)
    if n < 2:
        return nums
    temp = nums[0]
    less, more, equal = [], [], [temp]
    for i in nums[1:]:
        if i < temp:
            less.append(i)
        elif i > temp:
            more.append(i)
        elif i == temp:
            equal.append(i)

    # less = [x for x in nums[1:] if x < temp]
    # more = [x for x in nums[1:] if x > temp]
    # equal = [x for x in nums if x == temp]
    return QuickSort(less) + equal + QuickSort(more)

def QuickSort_3(nums):
    if len(nums) < 2:
        return nums
    i, j = 0, len(nums) - 1
    piv = nums[i]
    index = i
    while i < j:
        while (i < j) and nums[j] >= piv:
            j -= 1
        while (i < j) and nums[i] <= piv:
            i += 1
        nums[i], nums[j] = nums[j], nums[i]
    nums[i], nums[index] = piv, nums[i]
    return QuickSort_3(nums[:i]) + [piv] + QuickSort_3(nums[i + 1:])

第一种方法input的时候需要确定最开始和结束时候的index。看起来只有第一种方法是in-place的实现？
时间复杂度：
- 最差的时候和冒泡排序是一样的（也就是排好的），这时候的复杂度是n^2
- 最好的时候是完全平分，这时候是 nlogn
空间复杂度：如果用第一种方法，只耗费recursive时候的空间，也就是logn
in-place
不稳定，因为不知道在换的时候就把什么奇奇怪怪的东西换到前面去了

堆排序

一种类似二叉树的设计，子节点的数值总是大于或者小于父节点的数值。首先要让数据形成这样的结构
每次操作的时候，都把root的值和最后一个节点交换，交换后的最后一个节点移动出堆，然后再重新移动堆让他保持上面说的性质
一般通过一维数组来访问
- 父节点i的左节点：2i+1
- 父节点i的有节点：2i+2
- 子节点的父节点： floor（（i-1）/2）

def HeapSort(nums):
    # start是从最后一个父节点开始的,构建出heap
    for start in range((len(nums)-2)//2,-1,-1):
        MinHeap(nums,start,len(nums)-1)

    for i in range(len(nums)-1,-1,-1):
        nums[i],nums[0] = nums[0],nums[i]
        # 因为这里换到最后去的数字就已经确定是最大值了，所以再考虑的时候不用考虑他了
        MinHeap(nums,0,i-1)
    return nums

def MinHeap(nums, start, end):
    dad = start
    child = dad * 2 + 1
    # 如果子节点还在这个堆里面的话
    while child <= end:
        if child + 1 <= end and nums[child] > nums[child + 1]:
            # 比较两个子节点，选出来更小的那个
            child += 1
        if nums[dad] < nums[child]:
            break
        else:
            nums[dad], nums[child] = nums[child], nums[dad]
            dad = child
            child = dad * 2 + 1

注意：如果是maxheap（即root上的数字是最大的数字的话），实际排出来的是由小到大，因为max的数字在每一次都被换到了最后面
时间复杂度：nlogn
空间复杂度：1
上面的代码可以原地完成的 in place
稳定性：不稳定，这种瞎换的很难搞清楚到底换到哪里去了

计数排序

扫描一遍整个数组，找到最大值max和最小值min，花费时间n
创建一个新的数组，大小是max-min + 1
然后用新数组里面的index来统计每个数字出现的次数，最后整理出来

def CountingSort(nums):
    Max,Min = max(nums),min(nums)
    counting = [0 for i in range(Max-Min+1)]
    result = []
    for n in nums:
        counting[n-Min] += 1
    for n,i in enumerate(counting):
        result += i * [n + Min]
    return result

def CountingSort_2(nums): #并不创建新的数组
    Max= max(nums)
    bucketLen = Max + 1
    bucket = [0]*bucketLen
    sortedIndex = 0
    n = len(nums)
    for i in range(n):
        # 如果现在的这个位置是空的
        if not bucket[nums[i]]:
            bucket[nums[i]] = 0
        bucket[nums[i]] += 1
    for j in range(bucketLen):
        while bucket[j] > 0:
            nums[sortedIndex] = j
            sortedIndex += 1
            bucket[j] -= 1

不是比较排序，时间上来说比任何比较排序都快
没法用在排序的东西不是数字的情况下，数字差异非常大的情况会很占内存。排序的必须是整数
时间复杂度
- n+k，只需要在整个数组里找出最大值和最小值，然后在k时间里面数数每个数字出现了多少次。其中k是这些整数的范围
空间复杂度
- k用来储存计数的数组
稳定：为了保证数组的稳定性，需要反向填充数组（现在的方法不能保证稳定性）

桶排序

思想基于上面的计数排序，但是没有分那么多种
主要想法就是先把现在的内容分到k个不同的桶里面，再在每个桶里面分别排序
步骤
- 把数据分到k个桶里
  - 每个桶的范围是 floor（（max-min+1）/ k）
  - 放入桶的编号为 floor((数字-最小值)/每个桶的范围)
- 对每个不为空的桶排序
- 连接每个不为空的桶
时间复杂度：
- 最好n+k -> 平均分
- 最差是n^2 都分到一个桶里了
空间复杂度 n+k
稳定，注意先放进桶里的要先拿出来，才能保证稳定

基数排序 radix sort

非比较的整数排序的算法。也可以用在字母上，也就是LSD和MSD
把整数按位切割成不同的数字，然后每个位的数字分别比较。需要把比较的位放进0-9的九个桶里
步骤
- 所有数统一到一个长度，短的话前面补0
- 从最低位开始，依据最低位进行排序
- 一直排到最高位，排序之后就是有序的了