排序：

排序的目标：取得有序序列以供便捷操作数据

排序策略：计算机不能像人那样通览所有数据，只能依据两两比较的结果来处理排序问题这个步骤是重复的：

1.比较两个数据项。

2.交换两个数据项或者复制其中一个。

每种具体排序算法的实现细节不同。

冒泡排序：

冒泡排序运行起来非常慢，但在概念上排序算法中最简单的，在刚开始研究排序时也是一种很好的排序算法

算法形容：

1.比较两个数据项

2.假如左边的数据项大，交换两个数据项

3.向右移动位置重复1、2步

编码的关键点:

1.需要冒泡的趟数

2.如何控制两两比较：i-1,i,i+1

3.如何优化不和已冒泡的最大值进行比较

3 6 2 10 8

第一趟：

3 2 6 10 8

3 2 6 8 10

第二趟：

3 2 6 8 10

第三趟：

3 2 6 8 10

第四趟：

2 3 6 8 10

代码如下：

冒泡排序

为一个既有数字又有小写字母的字符串进行字符排序。

? ? ? ? //要求使用冒泡排序：

选择排序：

选择排序改进了冒泡排序，冒泡是比较完就交换，而选择排序则是选出最小的才交换。

算法形容：

1.扫描整个序列

2.从中挑出最小的数据项

3.将最小的数据项放置到合适的位置

6 5 4 7

假设第一个最小

验证能否最小

6 5

记忆最新的最小位置 5

重复以上2步到数组末尾。

最小的位置被找到。

0索引和2索引交换位置。

如此循环选择n-1次 程序结束。

代码如下：

例子：

为一个既有数字又有大小写字母的字符串进行字符排序。

? ? ? ? ///大小写字母排序时需要注意只比较字母的先后次序

? ? ? ? ///例：1CaD =>1aCD

? ? ? ? ///要求使用选择排序

插入排序：

插入排序是简单排序里最好的一种，但是略微麻烦少量

算法形容：

1.假设部分有序（一般设第一个数据项为第一部分）

2.其余输入依次插入之前的有序序列

若序列基本有序 此排序算法最优

要注意为待插入元素找到合适位置

1 2 4 3 5

[1 2 4] 3 5

// 监视哨：

5 7 3 1 2

假设第一部分已经有序

5? ? 7 3 1 2

5 7? ? 3 1 2

int temp = 3;

5 ” ” 7 1 2

” ” 5 7? 1 2

3 5 7? ? 1 2

1 2 3 7 5

插入排序分为两种，一种是带监视哨的，一种是不带监视哨的。

监视哨：

不带监视哨：

例子：

对象数组的插入排序怎样做？

首先建立一个Person对象，实现IComparable接口

快速排序：

快速排序是高级排序里最流行的一种，大多数情况下都是最快的.

算法形容：

1.把序列划分为两个部分：左边较小的部分和右边较大的部分.

2.调用自己为左边排序.3.调用自己为右边排序.

要注意算法形容和递归的应用.

50 32 77 43 78 67

代码如下：

快速一

快速二

例子：

为一个对象集合追加10000个随机对象，并按照快速排序方案为其排序。最好计算出所消耗的时间。

折半(两分法)查找法：

在有序表中，把待查找数据值与查找范围的中间元素值进行比较，会有三种情况出现：

1）待查找数据值与中间元素值正好相等，则返回中间元素值的索引。

2）待查找数据值比中间元素值小，则以整个查找范围的前半部分作为新的查找范围，执行1），直到找到相等的值。

3）待查找数据值比中间元素值大，则以整个查找范围的后半部分作为新的查找范围，执行1），直到找到相等的值。

4）假如最后找不到相等的值，则返回错误提醒信息。一般返回索引-1表示未找到。

代码如下：

例子：

对一个对象集合排序后，按照用户需要查询的关键字对对象集合进行折半查询，查不到返回null，查询到返回查到的对象。

递归算法：

递归算法的思想

递归算法是把问题转化为规模缩小了的同类问题的子问题。而后递归调用函数（或者过程）来表示问题的解。在C语言中的运行堆栈为他的存在提供了很好的支持，过程一般是通过函数或者子过程来实现。

递归算法：在函数或者子过程的内部，直接或者者间接地调用自己的算法。

递归算法的特点：

递归算法是一种直接或者者间接地调用自身算法的过程。在计算机编写程序中，递归算法对处理一大类问题是十分有效的，它往往使算法的形容简洁而且易于了解。

递归算法处理问题的特点：

(1) 递归就是在过程或者函数里调用自身。

(2) 在使用递归策略时，必需有一个明确的递归结束条件，称为递归出口。

(3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。

(4) 在递归调用的过程当中系统为每一层的返回点、局部量等开拓了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。

递归算法的要求

递归算法所表现的“重复”一般有三个要求：

一是每次调用在规模上都有所缩小(通常是减半)；

二是相邻两次重复之间有紧密的联络，前一次要为后一次做准备(通常前一次的输出就作为后一次的输入)；

三是在问题的规模极小时必需用直接给出解答而不再进行递归调用，因此每次递归调用都是有条件的(以规模未达到直接解答的大小为条件)，无条件递归调用将会成为死循环而不能正常结束。

例子：

1.斐波纳契数列

?? 这里有一组数：1、1、2、3、5、8、13、21、34、55……

? ///要求计算用这个递归算法，计算出这组数的第40个数是多少？

通过客户输入n来确定任意个数的位置：

2.求n的阶乘

3.一对小兔子一年后长成大兔子，一对大兔子每半年生一对小兔子，兔子的寿命为2年，假定第一年年初投放了一对小兔子，请编程实现，第Ｎ年年末总共有多少对兔子，Ｎ由键盘输入！