本文转载自微信公众号「贝塔学JAVA」,作者Silently9527。转载本文请联系贝塔学JAVA公众号。
本文已被Github仓库收录 https://github.com/silently9527/JavaCore
程序员常用的IDEA插件:https://github.com/silently9527/ToolsetIdeaPlugin
完全开源的淘客项目:https://github.com/silently9527/mall-coupons-server
前言
相信所有的程序员刚开始接触到的算法都会是排序算法,因为排序在对数据处理和计算有这重要的地位,排序算法往往是其他算法的基础;本文我们就先从初级排序算法开始学习算法。
排序算法的模板
在开始之前我们先定义一个排序算法通用的模板,在后面的排序算法都会实现这个模板
- 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(n2)」
选择排序的是「数据移动最少」的,交换的次数与数组的大小是线性关系,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(n2)」
插入排序
想象我们在玩扑克牌时,整理扑克牌都是把每一张插入到左边已经排好序的牌中适当的位置。插入排序的思路类似
算法实现的思路:
代码实现:
- 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(n2)」
希尔排序
对于大规模的乱序数组插入排序很慢,是因为它只交换相邻的元素,元素只能一点一点的从数组中移动到正确的位置;插入排序对于部分有序的数组排序是的效率很高;
希尔排序基于这两个特点对插入排序进行了改进;
算法实现的思路
希尔排序高效的原因,在排序之初,各个子数组都很短,子数组排序之后都是部分有序的,这两种情况都很适合插入排序。
代码实现:
- 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;
- }
- }
- }
本月DataWorks产品月刊为您带来 产品活动 1.参与阿里云DataWorks问卷调研 (Aliyu...
大数据市场如今正在呈爆炸式增长。根据调研机构Markets and Markets公司的调查,...
操作场景 您可以删除不需要的私有镜像。 删除私有镜像后,将无法找回,请谨慎操...
人脸识别 是目前商业应用最成熟、最广泛的人工智能技术之一,成为开发者、企业接...
阿里巴巴、腾讯、支付宝、网易、IBM、谷歌、京东、 百度、滴滴等一线互联网公司...
大家在开发Python的过程中,一定会遇到很多反斜杠的问题,很多人被反斜杠的数量...
案例背景 永安稻香小镇的体验式数字农业基地是余杭街道依托“阿里以西10分钟”的...
公司介绍 长沙营智信息技术有限公司旗下易撰网,2017年10月份上线以来,基于数据...
【51CTO.com快译】 数据分析是对数据进行判断、细化、更改和建模的过程,目的是...
【51CTO.com快译】不知道您是否听说过软件架构师最讨厌意大利面这个梗?它是指软...