一篇文章了解Java基础算法 排序 递归和折半查找 看完受益匪浅

一、排序

1.1 排序概述

排序（sorting）的功能是将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。

内部排序和外部排序

一类是整个排序过程在内存储器中进行，称为内部排序；另一类是由于待排序元素数量太大，以至于内存储器无法容纳全部数据，排序需要借助外部存储设备才能完成，这类排序称为外部排序。本章介绍的排序方法都属于内部排序比较排序和非比较排序

大部分排序都是需要通过比较首先来判断大小，作为排序的依据的。但是也有例外的，比如计数排序、基数排序，不需要进行比较。效率可以做到更高，但是会有一些限制条件，也可能需要更多的空间。冒泡排序、选择排序、直接插入排序是最基本的三种排序，效率最低，但是算法简单。排序的学习一般从这三种排序算法开始。1.2 冒泡排序

冒泡排序的算法

整个数列分成两部分：前面是无序数列，后面是有序数列初始状态下，整个数列都是无序的，有序数列是空如果一个数列有n个元素，则至多需要n-1趟循环才能保证数列有序每一趟循环可以让无序数列中最大数排到最后，（也就是说有序数列的元素个数增加1）每一趟循环都从数列的第一个元素开始进行比较，依次比较相邻的两个元素，比较到无序数列的末尾即可（而不是数列的末尾）如果前一个大于后一个，交换

【示例1】冒泡排序算法

缺点1：每一趟比较都要比较到数组的最后，没有必要，只要比较到无序数列的最后即可

for(int j=0;j

缺点2：不管是否有序，都要进行n-1趟循环；

如何判断有序：比较了一趟，没有发生交换 解决：定义一个符号量flag，默认有序true；发生交换，置为false， 一趟循环结束后，根据flag的值判断是否有序；有序，退出即可；【示例2】完善冒泡排序算法

算法动态展示网站：（可评论找我要网址(＾＿－)）

算法动画图解app（破解版支持中文）

1.3 选择排序

选择排序的算法

整个数列分成两部分：前面是有序数列，后面是无序数列初始状态下，整个数列都是无序的，有序数列是空一共n个数，需要n-1趟循环（一趟都不能少）每比较完一趟，有序数列数量+1，无序数列数量-1每趟先假设无序数列的第1个元素（整个数列的第i个元素）是最小的，让当前的最小数，从第i+1个元素开始比较，一直比较到最后一个元素。如果发现更小的数，就假设当前数是最小数。一趟比较完后，将发现最小数和无序数列的第一个数交换（如果最小数不是无序数列的第一个数）

【示例3】选择排序

二、递归和折半查找

2.1 递归

递归（recursion）是一种常见的解决问题的方法，即把问题逐渐简单化。递归的基本思想就是“自己调用自己”，一个使用递归技术的方法将会直接或者间接的调用自己。利用递归可以用简单的程序来解决一些复杂的问题。比如：斐波那契数列的计算、汉诺塔、快速排序等问题。

【示例4】使用递归实现n!

递归的调用过程

【示例5】使用递归实现斐波那契数列

斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）。

递归问题的特点

一个问题可被分解为若干层简单的子问题

子问题和其上层问题的解决方案一致

外层问题的解决依赖于子问题的解决

递归结构包括两个部分：

递归结束条件：什么时候不调用自身方法。如果没有条件，将陷入死循环。

递归体。解答：什么时候需要调用自身方法。

递归的优点

自然的思路，简单的程序

递归的缺点

但是递归调用会占用大量的系统堆栈，内存耗用多，

在递归调用层次多时速度要比循环慢的多

2.2 折半查找

折半查找又称为二分查找，这种查找方法需要待查的查找表满足两个条件：

首先，查找表必须使用顺序存储结构；

其次，查找表必须按关键字大小有序排列。

key=21的查找过程

key=85的查找过程

【示例6】非递归的折半查找

【示例7】递归的折半查找

本文为【尚学堂·百战程序员】授课课件，喜欢的话请点赞＋评论转发！将持续更新Java学习资料！感谢您的支持！