Java数据结构与Java算法学习Day02---算法排序

目录

一、简单排序

1.1Comparable接口介绍 11

1.2冒泡排序 12、13、14

1.3选择排序 15、16、17

1.4插入排序 18、19、20

二、高级排序

2.1希尔排序 21、22、23

2.2归并排序 24

2.2.1递归 24

2.2.2归并排序 25

2.3快速排序 32

2.3.1快速排序的原理 32 

2.3.2快速排序API设计（代码实现）33

2.3.3快速排序的切分原理 （切分部分的原理） 34

2.3.4快速排序切分原理部分代码实现 35

2.3.5快速排序与归并排序的区别&&时间复杂度分析 36

2.4排序的稳定性 37

---

一、简单排序

1.1Comparable接口介绍 11

本部分参看ppt

下面的三种排序仅使用于少量的数据排序情况。

1.2冒泡排序 12、13、14

1.3选择排序 15、16、17

从数据中选出合适的数据，放到合适的位置。将符合要求的数据的索引和所设定位置处的索引进行交换。

1.4插入排序 18、19、20

相当于是倒叙的冒泡排序。

代码部分做出解释：其余部分参看PPT。 

最坏情况：就是后面的所有元素都需要与前面的数据进行比较与交换处理。

二、高级排序

2.1希尔排序 21、22、23

希尔排序是插入排序的优化版本。

希尔排序的原理： 

希尔排序的思路，如下例子所示： 

增长量h的确定：

希尔排序代码部分的实现：

参考PPt

排序代码：

外层for负责从第一个h开始处一步一步地往后移，内层for负责当前h所在组内元素的比较

希尔排序性能判断：

希尔排序性能不能采用事前分析法，因为涉及到数学的理解。所以采用事后分析法来对希尔排序性能进行判断。根据算法实际的跑的时间。实际测试跑试数据。

同插入排序进行比较，性能较好。

性能测试部分代码实现：

2.2归并排序 24

2.2.1递归 24

含义：就是不断的调用自身算法

注意：递归不能无限的自身调用，会造成栈内存溢出，需要有边界条件来约束自身调用。

提示报错信息：

该错误问题是：栈内存溢出异常

2.2.2归并排序 25

原理：

 注：归并排序主要是再归并的过程中进行排序的。

其中最难的部分：分组后进行排序好的内容，再次合并的梳理：（参考PPT部分）28、29

 对应该部分融合部分代码实现：

本部分的代码部分参考ppt：对下面部分的理解。

 归并排序时间复杂度分析：30、31

注：最终归并排序的时间复杂度为O（nlogn）。比其他简单的排序性能高O（nlogn）。

 归并排序的缺点：

2.3快速排序 32

2.3.1快速排序的原理 32 

 快速排序：冒泡排序的升级。

主要的点：寻找分界值

1、寻找分界值：找排序的数据的第一个数字作为分界值。

 注：原理部分参考ppt。

2.3.2快速排序API设计（代码实现）33

和归并排序的设计类似。

2.3.3快速排序的切分原理 （切分部分的原理） 34

 

ppt切分原理如何查看：都只是移动了一步。 

2.3.4快速排序切分原理部分代码实现 35

参考ppt

2.3.5快速排序与归并排序的区别&&时间复杂度分析 36

快速排序与归并排序的区别： 

1、快速排序不需要归并的动作。规定排序则需要。

2、快速排序不需要等分，因为选取的第一个初始值不一行是数组的均等分的值；归并排序是进行等分的。

时间复杂度分析：

最优情况：

均等分。

最差情况：

逆序。

2.4排序的稳定性 37

不稳定：冒泡排序、希尔排序、快速排序

稳定：插入排序、归并排序

注：

1、一次排序的话：选择高性能排序

2、多次排序：选择稳定排序