leetcode和oj-gc-algorithm-course:gc算法课程2014

leetcode 和 oj GC Algorithm Course 2014 11月6日 八种排序算法 文件：sort.cpp 其实是数据结构课程设计交的作业 冒泡排序 O(n^2) 选择排序 O(n^2) 插入排序 O(n^2) — 对于基本有序的数列效率最高 希尔排序 O(nlogn) — 插入排序的优化 归并排序 O(nlogn) — 需要额外的空间存储 快速排序 O(nlogn ~ n^2) — 最常用，但对有序数列严重退化 堆排序 O(nlogn) — 璐神讲过，是否再讲？—— 还是讲了-_-|| 基数排序 — 简单了解即可，不常用 稳定的：冒泡、插入、归并，其它不稳定 小练习 求逆序对数： 给一列数a1,a2......an,求它的 逆序对数,即有多少个有序对 (i,j),使得i < j 但 ai > aj 第k小数： 输入n个整数和一个正整数k（1 <= k <= n）, 输出这些整数从小到大排序后的第k个 11月13日 & 11月20日 动态规划 斐波那契数列 f(n) = f(n-1) + f(n-2) 普通写法：递归 动态规划写法：自底向上，空间换时间 有时空间也可