首页 > 编程语言 >JAVA中的八大排序 可视化精华模板 (思路+代码实践)

JAVA中的八大排序 可视化精华模板 (思路+代码实践)

时间：2024-09-10 23:51:06浏览次数：13  
标签：arr JAVA int 复杂度 元素 ++ 可视化 排序 模板

“批判他人总是想的太简单 剖析自己总是想的太困难”

文章目录

前言

写在开始：

今天我们来看一下八大排序,本文中的代码可以直接作为模板使用.

文章有误敬请斧正 不胜感恩！

以下是本篇文章正文内容，

在这里插入图片描述

# 排序[排序算法]

1.冒泡排序（时间复杂度o(n^2)）

概念

通过对待排序序列从前向后(从下标较小的元素开始),依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒。

步骤

  1. 比较相邻两个数据如果。第一个比第二个大，就交换两个数
  2. 对每一个相邻的数做同样1的工作，这样从开始一队到结尾一队在最后的数就是最大的数。
  3. 针对所有元素上面的操作，除了最后一个。
  4. 重复1~3步骤，直到顺序完成

可视化

img

代码实现

import java.util.Arrays;

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {1,3,5,4,2,6,8,285,32,56,52,1};
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // 交换相邻元素
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}

2.选择排序（时间复杂度o(n^2)）

概念

基本原理是每一次从待排序的数组里找到最小值（最大值）的下标，然后将最小值（最大值）跟待排序数组的第一个进行交换，然后再从剩余的未排序元素中寻找最（大）元素，然后放到已排序的序列的末尾。反复的进行这样的过程直到待排序的数组全部有序。

步骤

1.在待排序的序列中找到最小的元素，将最小元素与排序序列中首位元素交换位置

2.从剩余的未排序序列中，继续找出一个最小元素，将最小元素与排序好的序列的下一个位置进行交换

3.重复步骤 2 的工作，直至排序完成

可视化

img

代码实现

import java.util.Arrays;

public class selectSort {
    public static void main(String[] args) {
        int[] arr ={29,10,14,37,14,2,8,1,7,6,5};
        for (int i = 0; i < arr.length - 1; i++) {
            //注意min的取值
            int min = i;
            //j=i;意味着i之前的数都是有序的
            for (int j = i; j < arr.length; j++) {
                if (arr[j] < arr[min]){
                    min = j;
                }
            }
            //交换，每一次循环的i都是未排序数据的第一个
            int temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
        System.out.println(Arrays.toString(arr));
    }
}

3.插入排序（时间复杂度o(n^2)）

概念

基本思想是将未排序部分的每个元素按照大小插入到已排序部分的适当位置。

步骤

  1. 从第一个元素开始，该元素可以认为已经被排序
  2. 取下一个元素tem，从已排序的元素序列从后往前扫描
  3. 如果该元素大于tem，则将该元素移到下一位
  4. 重复步骤3，直到找到已排序元素中小于等于tem的元素
  5. tem插入到该元素的后面，如果已排序所有元素都大于tem，则将tem插入到下标为0的位置
  6. 重复步骤2~5

可视化

img

代码示例

import java.util.Arrays;

public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 4, 2, 6, 8, 285, 32, 56, 52, 1};
        for (int i = 0; i < arr.length - 1; ++i)
        {
            int end = i;//记录有序序列最后一个元素的下标
            int temp = arr[end + 1];//待插入的元素
            while (end >= 0)//单趟排
            {
                if (temp < arr[end]) {//比插入的数大就向后移
                    arr[end + 1] = arr[end];
                    end--;
                } else {//比插入的数小，跳出循环
                    break;
                }
            }
            //tem放到比插入的数小的数的后面
            arr[end  + 1] = temp;
        }
        System.out.println(Arrays.toString(arr));
    }
}

4.快速排序（时间复杂度nlog(2)n）

概念

快速排序（Quick Sort），又称划分交换排序（partition-exchange sort），通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

步骤

  1. 从数列中挑出一个元素，称为"基准"（pivot），通常选择第一个元素
  2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
  3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

可视化

动画一

img

动画二

img

静态演示

img

代码示例

import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {30, 40, 60, 10, 20, 50};
        quickSort(arr, 0, arr.length - 1);
//        [20, 10, 30, 60, 40, 50]
//        [10, 20, 30, 60, 40, 50]
//        [10, 20, 30, 60, 40, 50]
//        [10, 20, 30, 50, 40, 60]
//        [10, 20, 30, 40, 50, 60]
//        [10, 20, 30, 40, 50, 60]
    }

    //快速排序
    public static void quickSort(int[] arr, int start, int end) {
        //递归结束的标记
        if (start < end) {
            //把数组中第0个数字作为标准数
            int stard = arr[start];
            //记录需要排序的下标
            int low = start;
            int high = end;
            //循环找比标准数大的数和标准数小的数
            while (low < high) {
                //如果右边数字比标准数大，下标向前移
                while (low < high && arr[high] >= stard) {
                    high--;
                }
                //右边数字比标准数小，使用右边的数替换左边的数
                arr[low] = arr[high];
                //如果左边数字比标准数小
                while (low < high && arr[low] <= stard) {
                    low++;
                }
                //左边数字比标准数大，使用左边的数替换右边的数
                arr[high] = arr[low];
            }
            //把标准数赋给低所在的位置的元素
            arr[low] = stard;
            //打印每次排序后的结果
            System.out.println(Arrays.toString(arr));

            //递归处理所有标准数左边的数字（含标准数）
            quickSort(arr, start, low);
            //递归处理所有标准数右边的数字
            quickSort(arr, low + 1, end);
        }
    }
}

5.归并排序（时间复杂度O(nlogn)）

概念

是创建在归并操作上的一种有效的排序算法。算法是采用分治法的一个非常典型的应用，且各层分治递扫可以同时进行。归并排序思路简单，速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。

步骤

  1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列:
  2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置;
  3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置:
  4. 重复步骤 3 直到某一指针达到序列尾:
  5. 将另一序列剩下的所有元素直接复制到合并序列尾

可视化

img

代码示例

public static int[] mergeSort(int[] arr, int l, int h){
        if (l == h){
            return new int[] {arr[l]};
        }
        int mid = (l+h)/2;
        int[] leftArr = mergeSort(arr, l, mid);
        int[] rightArr = mergeSort(arr, mid + 1, h);
        int[] newArr = new int[leftArr.length+rightArr.length];
        int m = 0, i = 0, j = 0;
        while (i < leftArr.length && j < rightArr.length){
            newArr[m++] = leftArr[i] < rightArr[j] ? leftArr[i++]:rightArr[j++];
        }
        while (i < leftArr.length)
            newArr [m++] = leftArr[i++];
        while (j < rightArr.length)
            newArr [m++] = rightArr[j++];
        return newArr;
}

6.桶排序 (时间复杂度与内置的排序有关)

概念

桶排序(Bucket sort) 是一种非比较的排序算法。桶排序采用了一些分类和分治的思想，把元素的值域分成若干段，每一段对应一个桶。在排序的时候，首先把每一个元素放到其对应的桶中，再对每一个桶中的元素分别排序，再按顺序把每个桶中的元素依次取出，合并成最终答案。

步骤

  1. 将值域分成若干段，每段对应一个桶
  2. 将待排序元素放入对应的桶中
  3. 将个桶内的元素进行排序
  4. 将桶中的元素依次取出

可视化

img

代码示例

public static void sort(int[] arr){
        List[] buckets = new ArrayList[10];
        for (int i = 0; i < buckets.length; i++) {
            buckets[i] = new ArrayList<Integer>();
        }
        for (int value : arr) {//对每个数值进行分类
            buckets[value / 1000].add(value);
        }
        for (List bucket : buckets) {
            Collections.sort(bucket);
        }
        int k = 0;
        for (List bucket : buckets) {
            if (!bucket.isEmpty()) {
                for (Object o : bucket) {
                    arr[k++] = (int) o;
                }
            }
        }
    }

7.希尔排序(时间复杂度o(n*1.3))

概念

实质上是采用分组插入的方法。先将整个待排序记录序列分割成几组，从而减少参与直接插入排序的数据量，对每组分别进行直接插入排序，然后增加每组的数据量，重新分组。

这样当经过几次分组排序后，整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

希尔对记录的分组，不是简单地“逐段分割"，而是将相隔某个“增量”的记录分成组。它并不能保证每趟排序至少能将一个元素放到其最终位置上。

步骤

1.先选定一个小于N的整数gap作为第一增量，然后将所有距离为gap的元素分在同一组，并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量，重复上述操作…
2.当增量的大小减到1时，就相当于整个序列被分到一组，进行一次直接插入排序，排序完成

可视化

img

示例代码

     public static void shellSort(int[] arr, int n){
        for (int gap = n / 2; gap > 0; gap /= 2){
            for (int i = gap; i < n; i++){
                int temp = arr[i];
                int j = i;
                while (j >= gap && arr[j - gap] > temp){
                        arr[j] = arr[j - gap];
                        j -= gap;
                }
                arr[j] = temp;
            }
        }
    }

8.基数排序（时间复杂度o(n*k)）

概念

将所有待比较数值（自然数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

步骤

  1. 确定数组中的最大元素有几位（MAX）（确定执行的轮数）
  2. 创建09个桶（桶的底层是队列），因为所有的数字元素都是由09的十个数字组成
  3. 依次判断每个元素的个位，十位至MAX位，存入对应的桶中，出队，存入原数组；
  4. 直至MAX轮结束输出数组。

可视化

img

示例代码

private static void radixSort(int[] arr) {
    //待排序列最大值
    int max = arr[0];
    int exp;//指数
    //计算最大值
    for (int anArr : arr) {
        if (anArr > max) {
            max = anArr;
        }
    }
    //从个位开始，对数组进行排序
    for (exp = 1; max / exp > 0; exp *= 10) {
        //分桶个数
        ArrayList<Integer>[] lists = new ArrayList[10];
        for (int i = 0; i < 10; i++) {
            lists[i] = new ArrayList<>();
        }
        for (int k : arr){
            lists[(k/exp)%10].add(k);
        }
        int index = 0;
        for (ArrayList<Integer> i : lists){
            for (Integer k : i){
                arr[index] = k;
                index++;
            }
        }
    }
}

在这里插入图片描述

总结

今天我们的学习笔记就到这里,排序的精髓还在多练.
在这边还是需要多多使用我们的代码
形成肌肉记忆,才是我们的终极目的.
制作不易,请多多点赞!如果这篇文章对你有帮助,请评论,分享哦!

标签：arr,JAVA,int,复杂度,元素,++,可视化,排序,模板
From： https://blog.csdn.net/2301_79175212/article/details/142112119

相关文章

  • Java SE 语法学习
    JavaSE语法java数据类型基本数据类型整数类型byte占1个字节，范围：-128-127short占2个字节，范围：-32768-32767int占4个字节，范围：-2147483648-2147483647long占8个字节，范围：-9223372036854775808-9223372036854775807浮点数类型double占8个字节float占4个字节字符类......
  • JavaWeb【day12】--（SpringBootWeb登录认证）
    案例-登录认证在前面的课程中，我们已经实现了部门管理、员工管理的基本功能，但是大家会发现，我们并没有登录，就直接访问到了Tlias智能学习辅助系统的后台。这是不安全的，所以我们今天的主题就是登录认证。最终我们要实现的效果就是用户必须登录之后，才可以访问后台系统中的功能。......
  • JavaWeb【day15】--（Maven高级）
    Maven高级Web开发讲解完毕之后，我们再来学习Maven高级。其实在前面的课程当中，我们已经学习了Maven。我们讲到Maven是一款构建和管理Java项目的工具。经过前面10多天web开发的学习，相信大家对于Maven这款工具的基本使用应该没什么问题了。我们掌握了Maven工具的基本......
  • Java API 之 String类详解（掌握字符串操作的利器）
    深入剖析JavaString类：掌握字符串操作的艺术String类是Java中最基础、最常用的类之一，它用于表示文本字符串。String类提供了丰富的API，可以用来操作字符串，例如连接、分割、查找、替换等。本篇博客将深入剖析String类，并通过详细的代码示例展示其所有常用方法的用途，让......
  • 高级java每日一道面试题-2024年9月06日-基础篇-Java中的PO、VO、BO、DO、DAO、DTO、PO
    如果有遗漏,评论区告诉我进行补充面试官:Java中的PO、VO、BO、DO、DAO、DTO、POJO是什么意思?我回答:PO持久化对象（PersistentObject）PO是持久化对象，用于表示数据库中的实体或表的映射通常与数据库表的结构和字段对应PO的属性对应数据库表的字段，可以进行持久化操作（新......
  • 为什么Java已经不推荐使用Stack了？
    为什么不推荐使用StackJava已不推荐使用Stack，而是推荐使用更高效的ArrayDeque为什么不推荐使用性能低：是因为Stack继承自Vector，而Vector在每个方法中都加了锁。由于需要兼容老的项目，很难在原有的基础上进行优化，因此Vector就被淘汰掉了，使用ArrayList和CopyOnWriteAr......
  • 模板
    太懒，于是就有了这个博客板子#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefsigneduns;typedefdoubledob;typedefunsignedlonglongull;#definepir(a,b)pair<a,b>#defineMP(a,b)map<a,b>#defineUMP(a,b......
  • 自学JavaDay7
    面向对象类与对象类    现实世界中如果事物与事物有共同特征，那么我们就把他们称之为一类，比如鱼类，运动类，电竞类等等。类是人类大脑思考总结出的一个模板，是一个抽象的概念。一个事物都应该具备状态和行为，比如学生，状态包括性别，年龄等等行为包括学习，跑步等等   ......
  • JavaScript语法入门四
    变量变量就是在内存中开辟一块用于存储信息的空间。变量命名1.        变量名称必须仅包含字母，数字，符号 $ 和 _。2.        首字符必须非数字。3.        采用驼峰式命名法（camelCase），就是，单词一个接一个，除了第一个单词，其他的每个单词都以大写字母开头......
  • [Java并发]线程安全的List
    线程安全的List目前比较常用的构建线程安全的List有三种方法：使用Vector容器使用Collections的静态方法synchronizedList(List<T>list)采用CopyOnWriteArrayList容器使用Vector容器Vector类实现了可扩展的对象数组，并且它是线程安全的。它和ArrayList在常用方法的实现上很......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99