算法路漫漫(一) 简单排序

标签：ted   出错   原理   二进制   描述   strong   插入排序   insert   二分法   1.认识时间复杂度 常数时间的操作：一个操作如果和数据量没有关系，每次都是固定时间内完成的操作，叫做常数操作。时间复杂度为一个算法流程中，常数操作数量的指标。常用O（读作big O）来表示。具体来说，在常数操作数量的表达式中，只要高阶项，不要低阶项，也不要高阶项的系数，剩下的部分如果记为f(N)，那么时间复杂度为O(f(N))。评价一个算法流程的好坏，先看时间复杂度的指标，然后再分析不同数据样本下的实际运行时间，也就是常数项时间。 衡量算法复杂度 1.内存（Memory） 2.时间（Time） 3.指令的数量（Number of Steps） 4.特定操作的数量 磁盘访问数量 网络包数量 5.渐进复杂度（Asymptotic Complexity） 算法的运行时间与什么相关 1.输入的数据。（例如：如果数据已经是排好序的，时间消耗可能会减少。） 2.输入数据的规模。（例如：6 和 6 * 109） 3.运行时间的上限。（因为运行时间的上限是对使用者的承诺。） 算法分析要保持大局观（Big Idea），其基本思路： 1.忽略掉那些依赖于机器的常量。 2.关注运行时间的增长趋势。 比如：T(n) = n3 + 99n3 + 9999 的趋势就相当于 T(n) = Θ(n3)。 渐近记号（Asymptotic Notation）通常有 O、 Θ 和 Ω 记号法。big O 表示按算法最差表现估算，big θ  表示按算法平均表现估算，big Ω 表示按算法最好表现估算。尽管技术上 Θ 记号较为准确，但通常仍然使用 O 记号表示。 使用 O 记号法（Big O Notation）表示最坏运行情况的上界。例如， 1.线性复杂度 O(n) 表示每个元素都要被处理一次。 2.平方复杂度 O(n2) 表示每个元素都要被处理 n 次。 Notation Intuition Informal Definition f is bounded above by g asymptotically Two definitions :Number theory: f is not dominated by g asymptotically Complexity theory: f is bounded below by g asymptotically f is bounded both above and below by g asymptotically    2.简单排序 2.1 选择排序 选择排序（Select Sort） 是直观的排序，通过确定一个 Key 最大或最小值，再从带排序的的数中找出最大或最小的交换到对应位置。再选择次之。双重循环时间复杂度为 O(n^2)    private void sellectionSorted(int[] arr){ if(arr == null || arr.length