Java 数据结构与算法系列精讲之排序算法

概述

从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章.

冒泡排序

冒泡排序 (Bubble Sort) 是一种简单的排序算法. 它重复地遍历要排序的数列, 一次比较两个元素, 如果他们的顺序错误就把他们交换过来. 遍历数列的工作是重复地进行直到没有再需要交换, 也就是说该数列已经排序完成. 这个算法的名字由来是因为越小的元素会经由交换慢慢 “浮” 到数列的顶端.

冒泡排序流程:

  • 通过比较相邻的元素, 判断两个元素位置是否需要互换
  • 进行 n-1 次比较, 结尾的元素就会是最大元素
  • 重复以上冒泡过程 n 次

代码实现:

import java.util.Arrays;

public class bubble {

    public static void main(String[] args) {

        // 创建数据
        int[] array = {426,375474,8465,453};

        // 实现排序
        System.out.println(Arrays.toString(array));
        System.out.println(Arrays.toString(bubbleSort(array)));
    }

    public static int[] bubbleSort(int[] array) {
        // 如果数组为空, 返回
        if (array.length == 0){
            return array;
        }

        // 执行冒泡过程n次, n为数组长度
        for (int i = 0; i < array.length; i++) {

            // 冒泡过程
            for (int j = 0; j < array.length - 1 - i; j++) {

                // 判断j索引的元素是否比j+1索引的元素大
                if (array[j+1] < array[j]) {
                    // 交换位置
                    int temp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = temp;
                }
            }
        }
        return array;
    }
}

输出结果:

[426, 375474, 8465, 453]
[426, 453, 8465, 375474]

插入排序

插入排序 (Insertion Sort) 是一种简单直观的排序算法. 它的工作原理是通过构建有序序列, 对于未排序数据, 在已排序序列中从后向前扫描,找到相应位置并插入. 插入排序在实现上, 在从后向前扫描过程中, 需要反复把已排序元素逐步向后挪位, 为最新元素提供插入空间.

插入排序流程:

  • 从第二个元素开始, 从后往前扫描
  • 逐个比较元素大小, 之道插入到合适的位置
  • 重复以上步骤 n-1 次

代码实现:

import java.util.Arrays;

public class insert {

    public static void main(String[] args) {

        // 创建数据
        int[] array = {426,375474,8465,453};

        // 实现排序
        System.out.println(Arrays.toString(array));
        System.out.println(Arrays.toString(insertionSort(array)));
    }

    public static int[] insertionSort(int[] array) {

        // 如果数组为空, 返回
        if (array.length == 0)
            return array;

        // 待排序元素
        int current;

        // 执行插入过程n-1次
        for (int i = 0; i < array.length - 1; i++) {

            // 指定待排序元素
            current = array[i + 1];

            int preIndex = i;

            // 执行插入过程, 往前一个个比对
            while (preIndex >= 0 && current < array[preIndex]) {
                array[preIndex + 1] = array[preIndex];
                preIndex--;
            }

            // 插入元素
            array[preIndex + 1] = current;
        }
        return array;
    }
}

输出结果:

​​​[426, 375474, 8465, 453]
[426, 453, 8465, 375474]

归并排序

归并排序 (Merge Sort) 是一种建立在归并操作上的算法, 是分治的一个经典应用.

归并排序流程:

  • 把数组拆分成两个 n/2 长度的子序列
  • 对这两个子序列分别采用归并排序
  • 将排序好的序列合并成最终序列

代码实现:

import java.util.Arrays;

public class merge {

    public static void main(String[] args) {

        // 创建数据
        int[] array = {426,375474,8465,453};

        // 实现排序
        System.out.println(Arrays.toString(array));
        System.out.println(Arrays.toString(mergeSort(array)));
    }

    public static int[] mergeSort(int[] array) {

        // 如果数组长度小于2, 返回
        if (array.length < 2) {
            return array;
        }

        // 分治
        int mid = array.length / 2;
        int[] left = Arrays.copyOfRange(array, 0, mid);
        int[] right = Arrays.copyOfRange(array, mid, array.length);
        return merge(mergeSort(left), mergeSort(right));
    }

    public static int[] merge(int[] left, int[] right) {

        // 创建数组用于存放合并后的序列
        int[] result = new int[left.length + right.length];

        for (int index = 0, i = 0, j = 0; index < result.length; index++) {
            // 左序列取完
            if (i >= left.length)
                result[index] = right[j++];
            // 右序列取完
            else if (j >= right.length)
                result[index] = left[i++];
            // 左序列的第i个大于有序列的第j个
            else if (left[i] > right[j])
                result[index] = right[j++];
            else
                result[index] = left[i++];
        }
        return result;
    }
}

输出结果:

[426, 375474, 8465, 453]
[426, 453, 8465, 375474]

快速排序

快速排序 (Quicksort) 通过一趟排序将要排序的数据分割成独立的两部分, 其中一部分的所有数据都比另外一部分的所有数据都要小, 然后再按此方法对这两部分数据分别进行快速排序, 整个排序过程可以递归进行, 以此达到整个数据变成有序序列.

​​

快速排序流程:

  • 从数组中挑出一个元素作为基准 (Pivot), 通常为第一个或者最后一个元素将比基准元素
  • 小的值放到基准前面, 比基准元素大的值放到基准后面
  • 递归进行分区操作

代码实现:

import java.util.Arrays;

public class quick {

    public static void main(String[] args) {

        // 创建数据
        int[] array = {426, 375474, 8465, 453};

        // 实现排序
        System.out.println(Arrays.toString(array));
        quickSort(array, 0, array.length - 1);
        System.out.println(Arrays.toString(array));
    }

    public static void quickSort(int[] arr, int low, int high) {

        // 定义
        int p, i, j, temp;

        if (low >= high) {
            return;
        }

        // p就是基准数, 每个数组的第一个
        p = arr[low];
        i = low;
        j = high;

        while (i < j) {
            //右边当发现小于p的值时停止循环
            while (arr[j] >= p && i < j) {
                j--;
            }

            //这里一定是右边开始,上下这两个循环不能调换(下面有解析,可以先想想)

            //左边当发现大于p的值时停止循环
            while (arr[i] <= p && i < j) {
                i++;
            }

            temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
        }

        // 交换p和arr[i]
        arr[low] = arr[i];
        arr[i] = p;

        // 分别进行快排
        quickSort(arr, low, j - 1);
        quickSort(arr, j + 1, high);
    }
}

输出结果:

[426, 375474, 8465, 453]
[426, 453, 8465, 375474]

总结

算法 时间复杂度 稳定性 适用场景
冒泡排序 O ( n 2 ) O(n^2) O(n2) 稳定 数组大致为从小到大
插入排序 O ( n 2 ) O(n^2) O(n2) 稳定 适用于数组较小的场景
归并排序 O ( n l o g n ) O(nlogn) O(nlogn) 稳定 适用于数组较大的场景
快速排序 O ( n l o g n ) O(nlogn) O(nlogn) 不稳定 适用于数组较大的场景

到此这篇关于Java 数据结构与算法系列精讲之排序算法的文章就介绍到这了,更多相关Java 排序算法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • java数据结构与算法之奇偶排序算法完整示例

    本文实例讲述了java数据结构与算法之奇偶排序算法.分享给大家供大家参考,具体如下: 算法思想: 基本思路是奇数列排一趟序,偶数列排一趟序,再奇数排,再偶数排,直到全部有序 举例吧, 待排数组[6 2 4 1 5 9] 第一次比较奇数列,奇数列与它的邻居偶数列比较,如6和2比,4和1比,5和9比 [6 2 4 1 5 9] 交换后变成 [2 6 1 4 5 9] 第二次比较偶数列,即6和1比,5和5比 [2 6 1 4 5 9] 交换后变成 [2 1 6 4 5 9] 第三趟又是奇数列,选择的是

  • Java数据结构和算法之冒泡,选择和插入排序算法

    目录 1.冒泡排序 2.选择排序 3.插入排序 4.总结 1.冒泡排序 这个名词的由来很好理解,一般河水中的冒泡,水底刚冒出来的时候是比较小的,随着慢慢向水面浮起会逐渐增大,这物理规律我不作过多解释,大家只需要了解即可. 冒泡算法的运作规律如下: ①.比较相邻的元素.如果第一个比第二个大,就交换他们两个. ②.对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对.这步做完后,最后的元素会是最大的数(也就是第一波冒泡完成). ③.针对所有的元素重复以上的步骤,除了最后一个. ④.持续每次对越

  • java数据结构排序算法之树形选择排序详解

    本文实例讲述了java数据结构排序算法之树形选择排序.分享给大家供大家参考,具体如下: 这里我们就来说说选择类排序之一的排序:树形选择排序 在简单选择排序中,每次的比较都没有用到上次比较的结果,所以比较操作的时间复杂度是O(N^2),想要降低比较的次数,则需要把比较过程中的大小关系保存下来.树形选择排序是对简单选择排序的改进. 树形选择排序:又称锦标赛排序(Tournament Sort),是一种按照锦标赛的思想进行选择排序的方法.首先对n个记录的关键字进行两两比较,然后在n/2个较小者之间再进

  • Java深入了解数据结构中常见的排序算法

    目录 一,概念 1,排序 2,稳定性 二,排序详解 1,插入排序 ①直接插入排序 2,选择排序 ①直接选择排序 ②堆排序 3,交换排序 ①冒泡排序 ②快速排序 4,归并排序 一,概念 1,排序 排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作. 平时的上下文中,如果提到排序,通常指的是排升序(非降序). 通常意义上的排序,都是指的原地排序(in place sort). 2,稳定性 两个相等的数据,如果经过排序后,排序算法能保证其相对位置不发生变化,则我们称该算

  • java数据结构排序算法之归并排序详解

    本文实例讲述了java数据结构排序算法之归并排序.分享给大家供大家参考,具体如下: 在前面说的那几种排序都是将一组记录按关键字大小排成一个有序的序列,而归并排序的思想是:基于合并,将两个或两个以上有序表合并成一个新的有序表 归并排序算法:假设初始序列含有n个记录,首先将这n个记录看成n个有序的子序列,每个子序列长度为1,然后两两归并,得到n/2个长度为2(n为奇数的时候,最后一个序列的长度为1)的有序子序列.在此基础上,再对长度为2的有序子序列进行亮亮归并,得到若干个长度为4的有序子序列.如此重

  • Java数据结构之基于比较的排序算法基本原理及具体实现

    目录 1. 七大基于比较的排序-总览 1.1常见基于比较的排序分类 1.2时间复杂度,空间复杂度以及稳定性. 2.直接插入排序 2.1 直接插入排序的基本思想 2.2 直接插入排序动画演示 2.3 代码示例 2.4 时间复杂度,空间复杂度以及稳定性 3. 希尔排序 3.1 算法思想 3.2 图片演示 3.3 代码示例 3.4 时间复杂度,空间复杂度以及稳定性 4.选择排序 4.1 算法思想 4.2 动画演示 4.3 代码示例 4.4 时间复杂度,空间复杂度以及稳定性 5.堆排序 5.1 算法思想

  • Java 数据结构与算法系列精讲之排序算法

    概述 从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 冒泡排序 冒泡排序 (Bubble Sort) 是一种简单的排序算法. 它重复地遍历要排序的数列, 一次比较两个元素, 如果他们的顺序错误就把他们交换过来. 遍历数列的工作是重复地进行直到没有再需要交换, 也就是说该数列已经排序完成. 这个算法的名字由来是因为越小的元素会经由交换慢慢 "浮" 到数列的顶端. 冒泡排序流程: 通过比较相邻的元素, 判断两个元素位置是否需要互换 进行 n-1 次比较,

  • Java 数据结构与算法系列精讲之贪心算法

    概述 从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 贪心算法 贪心算法 (Greedy Algorithm) 指的是在每一步选择中都采取在当前状态下最好或最优的选择, 从而希望导致结果是最好或最优的算法. 贪心算法锁得到的结果不一定是最优的结果, 但是都是相对近似最优的结果. 贪心算法的优缺点: 优点: 贪心算法的代码十分简单 缺点: 很难确定一个问题是否可以用贪心算法解决 电台覆盖问题 假设存在以下的广播台, 以及广播台可以覆盖的地区: 广播台 覆盖地区 K1 北京

  • Java 数据结构与算法系列精讲之KMP算法

    概述 从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. KMP 算法 KMP (Knuth-Morris-Pratt), 是一种改进的字符串匹配算法. KMP 算法解决了暴力匹配需要高频回退的问题, KMP 算法在匹配上若干字符后, 字符串位置不需要回退, 从而大大提高效率. 如图: 举个例子 (字符串 "abcabcdef" 匹配字符串 "abcdef"): 次数 暴力匹配 KMP 算法 说明 1 abcabcdef abcdef

  • Java 数据结构与算法系列精讲之字符串暴力匹配

    概述 从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 字符串匹配 字符串匹配 (String Matching) 指的是判断一个字符串是否包含另一个字符串. 举个例子: 字符串 "Hello World" 包含字符串 "Hello" 字符串 "Hello World" 不包含字符串 "LaLaLa" 暴力匹配 暴力匹配 (Brute-Force) 的思路: 如果charArray1[i] ==

  • Java 数据结构与算法系列精讲之单向链表

    目录 概述 链表 单向链表 单向链表实现 Node类 add方法 remove方法 get方法 set方法 contain方法 main 完整代码 概述 从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章. 链表 链表 (Linked List) 是一种递归的动态数据结构. 链表以线性表的形式, 在每一个节点存放下一个节点的指针. 链表解决了数组需要先知道数据大小的缺点, 增加了节点的指针域, 空间开销较大. 链表包括三类: 单向链表 双向链表 循环链表 单向链表 单向链表

  • Java 数据结构与算法系列精讲之环形链表

    目录 概述 链表 环形链表 环形链表实现 Node类 insert方法 remove方法 main 完整代码 概述 从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 链表 链表 (Linked List) 是一种递归的动态数据结构. 链表以线性表的形式, 在每一个节点存放下一个节点的指针. 链表解决了数组需要先知道数据大小的缺点, 增加了节点的指针域, 空间开销较大. 链表包括三类: 单向链表 双向链表 循环链表 环形链表 环形链表 (Circular Linked Li

  • Java 数据结构与算法系列精讲之栈

    目录 概述 栈 栈实现 push方法 pop方法 main 完整代码 概述 从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章. 栈 栈 (Stack) 是一种运算受限的线性表, 遵循先进后出的原则 (Last-In-First-Out). 举个例子, 当我们灌调料的时候, 后灌进去的调料会先被使用. 栈只能在表尾部进行插入和删除的操作. 开口的一端被称为栈顶, 另一端则被称为栈底. 如图: 栈实现 push 方法 栈 (Stack) 的 push 方法, 把项压入栈顶部.

  • Java 数据结构与算法系列精讲之数组

    目录 概述 数组 声明数组的两个方法 创建数组的两个方法 索引 自定义数组 泛型 构造函数 元素操作 调用 完整代码 概述 从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章. 数组 数组 (Array) 是有序数据的集合, 在 Java 中 java.util.Arrays包含用来操作数组的各种方法, 比如排序和搜索等. 其所有方法均为静态方法, 调用起来非常简单. 声明数组的两个方法 方法一: 数据类型[] array; 方法二: 数据类型 array[]; 创建数组的两

  • Java 数据结构与算法系列精讲之二叉堆

    目录 概述 优先队列 二叉堆 二叉堆实现 获取索引 添加元素 siftUp 完整代码 概述 从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 优先队列 优先队列 (Priority Queue) 和队列一样, 是一种先进先出的数据结构. 优先队列中的每个元素有各自的优先级, 优先级最高的元素最先得到服务. 如图: 二叉堆 二叉堆 (Binary Heap) 是一种特殊的堆, 二叉堆具有堆的性质和二叉树的性质. 二叉堆中的任意一节点的值总是大于等于其孩子节点值. 如图: 二

  • Java 数据结构与算法系列精讲之时间复杂度与空间复杂度

    目录 概述 算法的衡量标准 时间复杂度 最优时间复杂度 平均时间复杂度 最坏时间复杂度 O(1) O(n) O(n^2) O(logN) 空间复杂度 O(1) O(n) 概述 从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章. 算法的衡量标准 当我们需要衡量一个算法的的优越性, 通常会使用时间复杂度 (Time Complexity) 和空间复杂度 (Space Complexity) 来衡量. 时间复杂度 时间复杂度 (Time Complexity) 通常用 O(n)

随机推荐