本文已被Github仓库收录 https://github.com/silently9527/JavaCore程序员常用的IDEA插件:https://github.com/silently9527/ToolsetIdeaPlugin
完全开源的淘客项目:https://github.com/silently9527/mall-coupons-server
微信公众号:贝塔学Java
相信所有的程序员刚开始接触到的算法都会是排序算法,因为排序在对数据处理和计算有这重要的地位,排序算法往往是其他算法的基础;本文我们就先从初级排序算法开始学习算法。
在开始之前我们先定义一个排序算法通用的模板,在后面的排序算法都会实现这个模板
public interface SortTemplate { void sort(Comparable[] array); default void print(Comparable[] array) { for (Comparable a : array) { System.out.print(a + " "); } } default boolean less(Comparable a, Comparable b) { return a.compareTo(b) < 0; } default void exch(Comparable[] array, int i, int j) { Comparable tmp = array[i]; array[i] = array[j]; array[j] = tmp; } }
算法实现的思路:
代码实现:
public class SelectionSort implements SortTemplate { @Override public void sort(Comparable[] array) { int length = array.length; for (int i = 0; i < length; i++) { int min = i; for (int j = i + 1; j < length; j++) { if (less(array[j], array[min])) { min = j; } } exch(array, i, min); } } }
假如输入的数组是有序的,我们会发现选择排序运行的时候和未排序的时间一样长!
对于N个元素的数组,使用选择排序的时间复杂度是O(n²)
选择排序的是数据移动最少的,交换的次数与数组的大小是线性关系,N个元素的数组需要N次交换
算法实现的思路:
代码实现:
public class BubbleSort implements SortTemplate { @Override public void sort(Comparable[] array) { int length = array.length - 1; for (int i = 0; i < length; i++) { for (int j = 0; j < length - i; j++) { if (less(array[j + 1], array[j])) { exch(array, j, j + 1); } } } } }
对于N个元素的数组,使用冒泡排序的时间复杂度是O(n²)
想象我们在玩扑克牌时,整理扑克牌都是把每一张插入到左边已经排好序的牌中适当的位置。插入排序的思路类似
算法实现的思路:
代码实现:
public class InsertionSort implements SortTemplate { @Override public void sort(Comparable[] array) { int length = array.length; for (int i = 1; i < length; i++) { for (int j = i; j > 0 && less(array[j], array[j - 1]); j--) { exch(array, j, j - 1); } } } }
从代码的实现我们可以看出,当遇到了当前索引的元素大于了左边有序数组的最后一个元素时,内层循环就直接结束了,所以所我们排序的数组中存在着部分有序,那么插入排序算法会很快。
考虑最糟糕的情况,如果输入数组是一个倒置的,那么插入排序的效率和选择排序一样,时间复杂度是O(n²)
对于大规模的乱序数组插入排序很慢,是因为它只交换相邻的元素,元素只能一点一点的从数组中移动到正确的位置;插入排序对于部分有序的数组排序是的效率很高;
希尔排序基于这两个特点对插入排序进行了改进;
算法实现的思路
希尔排序高效的原因,在排序之初,各个子数组都很短,子数组排序之后都是部分有序的,这两种情况都很适合插入排序。
代码实现:
public class ShellSort implements SortTemplate { @Override public void sort(Comparable[] array) { int gap = 1; int length = array.length; while (gap < length / 3) { gap = 3 * gap + 1; } while (gap >= 1) { for (int i = gap; i < length; i++) { for (int j = i; j >= gap && less(array[j], array[j - gap]); j -= gap) { exch(array, j, j - gap); } } gap = gap / 3; } } }
文中或许会存在或多或少的不足、错误之处,有建议或者意见也非常欢迎大家在评论交流。
最后,写作不易,请不要白嫖我哟,希望朋友们可以点赞评论关注三连,因为这些就是我分享的全部动力来源🙏
文中所有源码已放入到了github仓库https://github.com/silently9527/JavaCore图片来源于网络
参考书籍:算法第四版