乐趣区

Onlogn分治思想归并排序和快速排序

分治思想,分而治之,将大问题拆分成小问题来解决
将问题 (p..r)q 拆成 (p..q)(q+1..r)
递归(编程技巧)

merge_sort(A, n){merge_sort_c(A, 0, n-1)
        }
        // 递归调用函数
        merge_sort_c(A, p, r){
            // 递归终止条件
            if p >= r then return
                
            // 取 p 到 r 中点 q
            q = (p + r)/2
            // 分治递归
            merge_sort_c(A, p, q)
            merge_sort_c(A, q+1, r)
            // 将 A(p..q) 和 A(p+1..r) 合并为 A(p..r)
            merge(A(p..r), A(p..q), A(q+1..r))
        }
退出移动版