排序

---

快速排序

平均情况下快速排序的时间复杂度是Θ(nlgn)，最坏情况是n2，但通过随机算法可以避免最坏情况。由于递归调用，快排的空间复杂度是Θ(lgn)。

简单来说，快速排序就是用两个指针来遍历数组，将数组通过基准数来进行切分，（假设是排序为递增序列）目标就是通过快排使得基准数左边的数都小于基准数，基准数右边的数都大于基准数。实现手法，先从尾部向头部找寻，找到第一个比基准数小的数字进行标记，之后从头部开始向尾部进行寻找，找到第一个比基准数大的数字进行标记，然后进行交换。
举例：
--- [3,5,2,1,4] ---

1. 基准数 3
2. 先找寻数字，从后往前找到了 1 比 3 小，标记 数组第四位
3. 从前往后找，找到了 5 比 3 大 ，标记 数组第二位
4. 交换 2,4 的位置，数组变成 [3,1,2,5,4]
5. 然后指针继续走，发现在 2 的位置，头指针与尾指针相遇，即 2 这个位置为基准点
6. 然后将，基准值移动到基准点，即数组变为 [2,1,3,5,4]

#!/usr/bin/python

# -*- coding: utf-8 -*-

numlist = [2,3,1,7,4,6,5]

def quicksort(start,end):

    if start > end:

        return

    k = numlist[start]

    left = start

    right = end

    while start < end:

        while k < numlist[end] and end > start:

            end -=1

        while numlist[start] <= k and start < end:

            start += 1

        numlist[start] , numlist[end] = numlist[end],numlist[start]

    numlist[left],numlist[start] = numlist[start],numlist[left]

    quicksort(left,start-1)

    quicksort(start+1,right)

quicksort(0,len(numlist)-1)

print(numlist)

归并排序

时间复杂度 O(nlogn)

归并排序简单来讲是一种“分治法”的体现，它将数组二二拆分，然后拆到最少之后，在相邻两两互相比较合并。
---举例---
以数组 array = [6, 5, 3, 1, 8, 7, 2, 4] 为例，首先将数组分为长度为 2 的子数组，并使每个子数组有序：
变化前 ： [6, 5] [3, 1] [8, 7] [2, 4]
变化后 ： [5, 6] [1, 3] [7, 8] [2, 4]
然后再两两合并：
变化前 ： [6, 5, 3, 1] [8, 7, 2, 4]
变化后 ： [1, 3, 5, 6] [2, 4, 7, 8]
最后将两个子数组合并：
变化前 ： [6, 5, 3, 1, 8, 7, 2, 4]
变化后 ： [1, 2, 3, 4, 5, 6, 7, 8]

array = [6, 5, 3, 1, 8, 7, 2, 4]
def mergesort(numlist):
    if len(numlist) <= 1:
        return numlist
    mid = int(len(numlist) / 2)
    leftlist = mergesort(numlist[:mid])
    rightlist = mergesort(numlist[mid:])
    return merge(leftlist,rightlist)

def merge(leftlist,rightlist):
    res = []
    i = 0
    j = 0
    while i < len(leftlist) and j < len(rightlist):
        if leftlist[i] <= rightlist[j]:
            res.append(leftlist[i])
            i += 1
        else:
            res.append(rightlist[j])
            j += 1
    res += leftlist[i:]
    res += rightlist[j:]
    return res
numlist = mergesort(array)
print(numlist)

插入排序

时间复杂度 O(n^2)

插入排序，有点类似冒泡排序，它是使指针从后往前遍历，在遍历过程中，被遍历过的数以此往后顺移一位。【其实这种方式看起来，就像是逐次向前比较，来使两个数换位】

#!/usr/bin/python
# -*- coding: utf-8 -*-
array = [6, 5, 3, 1, 8, 7, 2, 4]
def insert_sort(lst):
    n=len(lst)
    if n==1: return lst
    for i in range(1,n):
        for j in range(i,0,-1):
            if lst[j]<lst[j-1]: lst[j],lst[j-1]=lst[j-1],lst[j]
            else:break
    return lst
numlist = insert_sort(array)
print(numlist)

动态规划

---

最长回文子序列、回文子序列个数

最长回文子序列：

主要的思路条件是：dp[i][j] ，i 和 j 代表字符的index，比如说一个字符串“abba”，然后 dp[1][3] 就表示这个字符串的子串 "bba" 来进行判断，dp[0][2] 就表示这个子串 “abb” 来进行判断。
然后这个dp的状态转移方程思路：

• dp[x][x] = 1 表示每个字符串代表它本身，那么一定是一个回文字符串。
• dp[i][j] = dp[i][j]=dp[i+1][j-1] + 2 if（str[i]==str[j]） 【当这个字符串是三个的时候，就容易理解这个状态转移方程组】
• dp[i][j] = max(dp[i+1][j],dp[i][j-1]) if （str[i]!=str[j]）【就是去头与去尾子序列中最佳的答案】

回文子序列个数：

dp的状态转移方程思路：

• dp[i][i]=1 （i=0：n-1）
• dp[i][j]=dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1] if（str[i]！=str[j]） 【去头的序列 + 去尾的序列 - 去头和尾的序列长度】
• dp[i][j]=dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]+dp[i+1][j-1]+1=dp[i+1][j] + dp[i][j-1]+1 if （str[i]==str[j]）【去头的序列 + 去尾的序列 + 1】

参考链接：https://www.cnblogs.com/AndyJee/p/4465696.html