Java数据结构与算法-排序算法

技术博客：悬笔e绝

文章转载自http://www.xuanbiyijue.com/2018/02/14/数据结构与算法-排序算法/

常见的五种排序算法：

冒泡排序；选择排序；插入排序；归并排序；快速排序；

前三种是基本排序算法，后两个是高级的排序算法；

冒泡排序

最慢的排序算法之一，数据值会像气泡一样从数组的一段漂浮到另一端

基本思路：

1.依次比较相邻的两个数，如果第一个比第二个小，不变。如果第一个比第二个大，调换顺序。一轮下来，最后一个是最大的数

2.对除了最后一个之外的数重复第一步，直到只剩一个数

图形展示：

冒泡排序

代码实现：

选择排序

基本思路：

1.找出最小的数，和第一个交换位置

2.在剩下的数中，找出最二小的数，和第二个交换位置

3.依次类推，排出顺序

图形展示

选择排序

代码实现：

插入排序

基本思路：

1.把数组分为[已排序]和[未排序]两部分

2.从[未排序]抽出第一个数，和[已排序]部分比较，插入到合适的位置

图形展示：

插入排序

代码实现：

归并排序（分而治之）

基本思路：

1.不断将数组对半分，直到每个数组只有一个

2.将分出来的部分重新合并

3.合并的时候按顺序排列

图形展示：

归并排序

代码实现：

快速排序

基本思路：

1.以一个数为基准(第一个数或者中间的数都可以)，比基准小的放到左边，比基准大的放到右边

2.再按此方法对这两部分数据分别进行快速排序（递归进行）

3.不能再分后退出递归，并将数组合并

图形展示：

快速排序

代码实现：