(1)写出快速排序法的算法伪码，并分析其算法复杂度

快速排序法的算法伪码如下：

1. 定义函数quick_sort(array, left, right)
2. 若left >= right，返回
3. 取数组array中left和right之间的任意一个数作为pivot
4. 定义变量i = left，j = right
5. 当i < j时，执行以下步骤：
1. 若array[i] >= pivot且array[j] <= pivot，则交换array[i]和array[j]
2. 若array[i] < pivot，则i++
3. 若array[j] > pivot，则j--
6. 递归调用quick_sort(array, left, i-1)和quick_sort(array, i+1, right)

快速排序法的最坏时间复杂度为O(n^2)，即当待排序序列已经有序或基本有序时，每次划分只删去一个元素，需要划分n次才能结束递归。最好情况下的时间复杂度为O(nlogn)，即当待排序序列被均匀地分成两部分时，每次递归的规模就会减半。平均情况下的时间复杂度为O(nlogn)。快速排序法是一种原地排序算法，空间复杂度为O(1)。

相关问题

最长公共子序列。给定两个序列, , 使用动态规划算法求X和Y的最长公共子序列。 要求： （1） 写出递归公式 （2） 分析采用哪种数据结构存储中间结果 （3） 分析求解顺序 （4） 写出算法伪码 （5） 分析算法复杂度 （6） 使用熟悉的编程语言实现算法 （7） 生成测试数据，测试算法的正确性和性能

1. 递归公式：设X和Y分别为两个序列，LCS(i,j)为X[1...i]和Y[1...j]的最长公共子序列长度，则有：

LCS(i,j) = 0 i=0或j=0
LCS(i,j) = LCS(i-1,j-1) + 1 X[i] = Y[j]
LCS(i,j) = max(LCS(i-1,j),LCS(i,j-1)) X[i] != Y[j]

2. 数据结构：可以使用二维数组存储中间结果

3. 求解顺序：从LCS(0,0)开始，按照行优先或列优先的顺序依次计算LCS(i,j)，直到LCS(m,n)

4. 算法伪码：

function LCSLength(X,Y)
m = length(X)
n = length(Y)
let c[0..m, 0..n] be a new array
for i = 0 to m
c[i,0] = 0
for j = 0 to n
c[0,j] = 0
for i = 1 to m
for j = 1 to n
if X[i] = Y[j]
c[i,j] = c[i-1,j-1] + 1
else
c[i,j] = max(c[i,j-1],c[i-1,j])
return c[m,n]

5. 复杂度：最坏情况下时间复杂度为O(mn)

6. 编程语言实现：

def LCSLength(X,Y):
    m = len(X)
    n = len(Y)
    c = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1,m+1):
        for j in range(1,n+1):
            if X[i-1] == Y[j-1]:
                c[i][j] = c[i-1][j-1] + 1
            else:
                c[i][j] = max(c[i-1][j],c[i][j-1])
    return c[m][n]

7. 测试数据：

X = "ABCBDAB"
Y = "BDCABA"
LCSLength(X,Y)  # 输出4

贪心法设计一个以金额 n 和硬币面额𝑑1 > 𝑑2 > ⋯ > 𝑑𝑚作为输入，得到最少找零硬币数。为 以上找零问题设计一个贪婪算法，给出算法伪码，并分析其时间复杂度。

这个问题可以使用贪心法来求解。我们可以先将硬币面额按照从大到小的顺序排序，然后从大到小依次考虑每一种面额的硬币。

具体做法是，对于当前考虑的硬币面额𝑑𝑖，尽可能多地使用该面额的硬币，直到该面额的硬币不能再用了，然后转到下一个面额。

下面是该算法的伪代码：

def minCoins(n, coins):
    coins = sorted(coins, reverse=True)  # 按从大到小排序
    count = 0
    for coin in coins:
        while n >= coin:
            n -= coin
            count += 1
    return count

时间复杂度分析：假设硬币面额数量为m，那么排序的时间复杂度为O(mlogm)，每种面额的硬币最多使用n/di个，所以总共需要进行O(m)次循环，因此算法的时间复杂度为O(mlogm+n)。