算法初级（排序算法）

结构化编程&伪代码

说到排序算法，就要先讲一下什么是结构化编程，总结一下来说，结构化编程有以下特点：
1.一行一行执行
2.有条件控制语句 (if...else...)
3.有循环控制语句 (while(exp) do...)

同时，在讲解算法前，还要了解一下什么是伪代码，伪代码就是完全属于你自己构建的代码，语法也是你自己定的，使用伪代码更能帮助你理解算法是什么。

算法

• 算法有以下五个特征
  1.输入：一个算法必须有零个或以上输入量。
  2.输出：一个算法应有一个或以上输出量，输出量是算法计算的结果。
  3.明确性：算法的描述必须无歧义，以保证算法的实际执行结果是精确地匹配要求或期望，通常要求实际运行结果是确定的。
  4.有限性：依据图灵的定义，一个算法是能够被任何图灵完全系统模拟的一串运算，而图灵机只有有限个状态、有限个输入符号和有限个转移函数（指令）。而一些定义更规定算法必须在有限个步骤内完成任务。
  5.有效性：又称可行性。能够实现，算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。

• 所有算法的设计模式（大分类）
  1.分治法：把一个问题分割成互相独立的多个部分分别求解的思路。这种求解思路带来的好处之一是便于进行并行计算。
  2.动态规划法：当问题的整体最优解就是由局部最优解组成的时候，经常采用的一种方法。
  3.贪心算法：常见的近似求解思路。当问题的整体最优解不是（或无法证明是）由局部最优解组成，且对解的最优性没有要求的时候，可以采用的一种方法。
  4.线性规划法：见条目。
  5.简并法：把一个问题通过逻辑或数学推理，简化成与之等价或者近似的、相对简单的模型，进而求解的方法。

五种排序算法

接下来就要开始讲算法了，今天讲的是五种排序算法。

动图网址

1. 冒泡排序(体育委员两两摸头法)

• 原理
  1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  2.对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
  3.针对所有的元素重复以上的步骤，除了最后一个。
  4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

• 动态图

  
  冒泡排序

2. 选择排序(体育老师一指禅法)

• 原理
  1.首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
  2.然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
  3.以此类推，直到所有元素均排序完毕。

• 动态图

  
  选择排序

3. 插入排序(起扑克牌法)

• 原理
  1.首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
  2.然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
  3.以此类推，直到所有元素均排序完毕。

• 动态图

  
  插入排序

4. 桶排序(强迫症收扑克法)

• 原理
  1.设置一个定量的数组当作空桶子。
  2.寻访序列，并且把项目一个一个放到对应的桶子去。
  3.对每个不是空的桶子进行排序。
  4.从不是空的桶子里把项目再放回原来的序列中。
• 动态图

5. 快速排序

• 原理
  1.从数列中挑出一个元素，称为“基准”（pivot），
  2.重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分割结束之后，该基准就处于数列的中间位置。这个称为分割（partition）操作。
  3.递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。

• 动态图

  
  快速排序

[END]