AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

常见排序算法详解（Java）（一）

2022-05-17 84
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 笔记

（1）Comparable接口介绍

Java提供了一个接口Comparable就是用来定义排序 规则的，在这里我们以案例的形式对Comparable接口做一个简单的回顾。


需求：


1.定义一个学生类Student，具有年龄age和姓名username两个属性，并通过Comparable接口提供比较规则；


2.定义测试类Test，在测试类Test中定义测试方法Comparable getMax(Comparable c1,Comparable c2)完成测试


学生类：

package cn.itcast.algorithm.sort;
/**
 * 1.定义一个学生类Student，具有年龄age和姓名username两个属性，并通过Comparable接口提供比较规则；
 * @author caizhengjie
 */
public class Student implements Comparable<Student>{
    private String username;
    private int age;
    public String getUsername() {
        return username;
    }
    public void setUsername(String username) {
        this.username = username;
    }
    public int getAge() {
        return age;
    }
    public void setAge(int age) {
        this.age = age;
    }
    @Override
    public String toString() {
        return "Student{" +
                "username='" + username + '\'' +
                ", age=" + age +
                '}';
    }
    @Override
    public int compareTo(Student o) {
        return this.getAge() - o.getAge();
    }
}

测试类：

package cn.itcast.algorithm.test;
import cn.itcast.algorithm.sort.Student;
/**
 * 2.定义测试类Test，在测试类Test中定义测试方法Comparable getMax(Comparable c1,Comparable c2)完成测试
 */
public class TestComparable {
    public static void main(String[] args) {
        Student s1 = new Student();
        s1.setUsername("alex");
        s1.setAge(10);
        Student s2 = new Student();
        s2.setUsername("jack");
        s2.setAge(20);
        Comparable<Student> max = getMax(s1,s2);
        System.out.println(max);
    }
    public static Comparable<Student> getMax(Comparable<Student> c1,Comparable<Student> c2){
        int result = c1.compareTo((Student) c2);
        // 如果result<0，c1<c2
        // 如果result>0，c1>c2
        // 如果result=0，c1=c2
        if (result >= 0){
            return c1;
        } else {
            return c2;
        }
    }
}

运行结果：

Student{username='jack', age=20}


（2）冒泡排序

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。


需求：


排序前：{4,5,6,3,2,1}

排序后：{1,2,3,4,5,6}

排序原理：


比较相邻的元素。如果前一个元素比后一个元素大，就交换这两个元素的位置。


对每一对相邻元素做同样的工作，从开始第一对元素到结尾的最后一对元素。最终最后位置的元素就是最大值。1.png冒泡排序API设计：

2.png

冒泡排序的代码实现：

package cn.itcast.algorithm.sort;
/**
 * @author ：caizhengjie
 * @description：冒泡排序
 * @date ：2021/1/25 10:32 下午
 */
public class Bubble {
    /**
     * 对数组arr中的元素进行排序
     * @param arr
     */
    public static void sort(Comparable<Integer>[] arr){
        for (int i = arr.length - 1;i > 0;i--){
            for (int j = 0;j < i;j++){
                if (greater(arr[j],arr[j+1])){
                    exch(arr,j,j+1);
                }
            }
        }
    }
    /**
     * 比较v元素是否大于w元素
     * @param v
     * @param w
     * @return
     */
    public static boolean greater(Comparable<Integer> v,Comparable<Integer> w){
        return v.compareTo((Integer) w)>0;
    }
    /**
     * 数组元素i和j交换位置
     * @param arr
     * @param i
     * @param j
     */
    public static void exch(Comparable<Integer>[] arr,int i,int j){
        Comparable<Integer> comparable = arr[i];
        arr[i] = arr[j];
        arr[j] = comparable;
    }
}

package cn.itcast.algorithm.test;
import cn.itcast.algorithm.sort.Bubble;
import java.util.Arrays;
/**
 * @author ：caizhengjie
 * @description：TODO
 * @date ：2021/1/25 10:57 下午
 */
public class BubbleTest {
    public static void main(String[] args) {
        Integer[] arr = {4,5,6,3,2,1};
        Bubble.sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

冒泡排序的时间复杂度分析 ：

冒泡排序使用了双层for循环，其中内层循环的循环体是真正完成排序的代码，所以， 我们分析冒泡排序的时间复杂度，主要分析一下内层循环体的执行次数即可。


在最坏情况下，也就是假如要排序的元素为{6,5,4,3,2,1}逆序，那么：

元素比较的次数为：

(N-1)+(N-2)+(N-3)+…+2+1=((N-1)+1)*(N-1)/2=N^2/2-N/2;


元素交换的次数为：

(N-1)+(N-2)+(N-3)+…+2+1=((N-1)+1)*(N-1)/2=N^2/2-N/2;


总执行次数为：

(N ^ 2/2-N/2)+(N ^ 2/2-N/2)=N^2-N;


按照大O推导法则，保留函数中的最高阶项那么最终冒泡排序的时间复杂度为O(N^2).


（3）选择排序

选择排序是一种更加简单直观的排序方法。


需求：


排序前：{4,6,8,7,9,2,10,1}

排序后：{1,2,4,5,7,8,9,10}

排序原理：


每一次遍历的过程中，都假定第一个索引处的元素是最小值，和其他索引处的值依次进行比较，如果当前索引处 的值大于其他某个索引处的值，则假定其他某个索引出的值为最小值，最后可以找到最小值所在的索引


交换第一个索引处和最小值所在的索引处的值


3.png

选择排序API设计：

4.png

选择排序的代码实现：

package cn.itcast.algorithm.sort;
/**
 * @author ：caizhengjie
 * @description：选择排序
 * @date ：2021/1/26 10:14 下午
 */
public class Selection {
    /**
     * 对数组arr中的元素进行排序
     * @param arr
     */
    public static void sort(Comparable<Integer>[] arr){
        for (int i=0;i <= arr.length-2;i++){
            // 假定本次遍历，最小值所在的索引是i
            int minIndex = i;
            for (int j=i+1;j<arr.length;j++){
                if (greater(arr[minIndex],arr[j])){
                    // 跟最小值换索引
                    minIndex = j;
                }
            }
            // 交换i索引处和minTndex索引处的值
            exch(arr,i,minIndex);
        }
    }
    /**
     * 比较v元素是否大于w元素
     * @param v
     * @param w
     * @return
     */
    public static boolean greater(Comparable<Integer> v,Comparable<Integer> w){
        return v.compareTo((Integer) w)>0;
    }
    /**
     * 数组元素i和j交换位置
     * @param arr
     * @param i
     * @param j
     */
    public static void exch(Comparable<Integer>[] arr,int i,int j){
        Comparable<Integer> comparable = arr[i];
        arr[i] = arr[j];
        arr[j] = comparable;
    }
}

package cn.itcast.algorithm.test;
import cn.itcast.algorithm.sort.Selection;
import java.util.Arrays;
/**
 * @author ：caizhengjie
 * @description：TODO
 * @date ：2021/1/26 10:35 下午
 */
public class SelectionTest {
    public static void main(String[] args) {
        Integer[] arr = {4,6,8,7,9,2,10,1};
        Selection.sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

选择排序的时间复杂度分析：


选择排序使用了双层for循环，其中外层循环完成了数据交换，内层循环完成了数据比较，所以我们分别统计数据 交换次数和数据比较次数：


数据比较次数：


(N-1)+(N-2)+(N-3)+…+2+1=((N-1)+1)*(N-1)/2=N^2/2-N/2;


数据交换次数： N-1


时间复杂度：N ^ 2/2-N/2+（N-1）=N ^ 2/2+N/2-1; 根据大O推导法则，保留最高阶项，去除常数因子，时间复杂度为O(N^2);


（4）插入排序

插入排序（Insertion sort）是一种简单直观且稳定的排序算法。


需求：


排序前：{4,3,2,10,12,1,5,6}

排序后：{1,2,3,4,5,6,10,12}

排序原理：


把所有的元素分为两组，已经排序的和未排序的；


找到未排序的组中的第一个元素，向已经排序的组中进行插入；


倒叙遍历已经排序的元素，依次和待插入的元素进行比较，直到找到一个元素小于等于待插入元素，那么就把待 插入元素放到这个位置，其他的元素向后移动一位；



5.png

插入排序API设计：

6.png

插入排序代码实现：

package cn.itcast.algorithm.sort;
/**
 * @author ：caizhengjie
 * @description：插入排序
 * @date ：2021/1/26 10:45 下午
 */
public class Insertion {
    /**
     * 对数组arr中的元素进行排序
     * @param arr
     */
    public static void sort(Comparable<Integer>[] arr){
        for (int i=1;i< arr.length;i++){
            // 当前元素为a[i]，依次和i前面的元素比较，找到一个小于等于a[i]的元素
            for (int j=i;j>0;j--){
                if (greater(arr[j-1],arr[j])){
                    // 交换元素
                    exch(arr,j-1,j);
                } else {
                    // 找到了该元素，结束
                    break;
                }
            }
        }
    }
    /**
     * 比较v元素是否大于w元素
     * @param v
     * @param w
     * @return
     */
    public static boolean greater(Comparable<Integer> v,Comparable<Integer> w){
        return v.compareTo((Integer) w)>0;
    }
    /**
     * 数组元素i和j交换位置
     * @param arr
     * @param i
     * @param j
     */
    public static void exch(Comparable<Integer>[] arr,int i,int j){
        Comparable<Integer> comparable = arr[i];
        arr[i] = arr[j];
        arr[j] = comparable;
    }
}

package cn.itcast.algorithm.test;
import cn.itcast.algorithm.sort.Insertion;
import java.util.Arrays;
/**
 * @author ：caizhengjie
 * @description：TODO
 * @date ：2021/1/26 10:52 下午
 */
public class InsertionTest {
    public static void main(String[] args) {
        Integer[] arr = {4,3,2,10,12,1,5,6};
        Insertion.sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

插入排序的时间复杂度分析：

插入排序使用了双层for循环，其中内层循环的循环体是真正完成排序的代码，所以，我们分析插入排序的时间复 杂度，主要分析一下内层循环体的执行次数即可。


最坏情况，也就是待排序的数组元素为{12,10,6,5,4,3,2,1}，那么：


比较的次数为：


(N-1)+(N-2)+(N-3)+…+2+1=((N-1)+1)*(N-1)/2=N^2/2-N/2;


交换的次数为：


(N-1)+(N-2)+(N-3)+…+2+1=((N-1)+1)*(N-1)/2=N^2/2-N/2;


总执行次数为：


(N ^ 2/2-N/2)+(N ^ 2/2-N/2)=N^2-N;


按照大O推导法则，保留函数中的最高阶项那么最终插入排序的时间复杂度为O(N^2).


（5）希尔排序

希尔排序是插入排序的一种，又称“缩小增量排序”，是插入排序算法的一种更高效的改进版本。


需求：


排序前：{9,1,2,5,7,4,8,6,3,5}

排序后：{1,2,3,4,5,5,6,7,8,9}

排序原理：


选定一个增长量h，按照增长量h作为数据分组的依据，对数据进行分组；


对分好组的每一组数据完成插入排序；


减小增长量，最小减为1，重复第二步操作。7.png

增长量h的确定：增长量h的值每一固定的规则，我们这里采用以下规则：

int h=1 
while(h<5){
  h=2h+1；//3,7 
} 
// 循环结束后我们就可以确定h的最大值； 
// h的减小规则为：
h=h/2

希尔排序的API设计：

8.png

希尔排序的代码实现：

package cn.itcast.algorithm.sort;
/**
 * @author ：caizhengjie
 * @description：希尔排序
 * @date ：2021/1/30 4:28 下午
 */
public class Shell {
    /**
     * 对数组arr中的元素进行排序
     * @param arr
     */
    public static void sort(Comparable<Integer>[] arr){
        // 1.根据数组arr的长度，确定增长量h的初始值
        int h = 1;
        while (h < arr.length/2){
            h = 2*h + 1;
        }
        // 2.希尔排序
        while (h >= 1){
            // 找到待插入的元素
            for (int i = h;i < arr.length;i++){
                // arr[i]就是待插入的元素,把arr[i]插入到arr[i-h],arr[i-2h],arr[i-3h]...序列中
                for (int j = i;j >= h;j-=h){
                    //arr[j]就是待插入元素，依次和arr[j-h],arr[j-2h],arr[j-3h]进行比较，
                    // 如果arr[j]小，那么 交换位置，如果不小于，arr[j]大，则插入完成。
                    if (greater(arr[j - h],arr[j])){
                        // 交换元素
                        exch(arr,j-h,j);
                    } else {
                        // 带插入元素已经找到合适的位置，结束循环
                        break;
                    }
                }
            }
            // 减少h的值
            h = h/2;
        }
    }
    /**
     * 比较v元素是否大于w元素
     * @param v
     * @param w
     * @return
     */
    public static boolean greater(Comparable<Integer> v,Comparable<Integer> w){
        return v.compareTo((Integer) w)>0;
    }
    /**
     * 数组元素i和j交换位置
     * @param arr
     * @param i
     * @param j
     */
    public static void exch(Comparable<Integer>[] arr,int i,int j){
        Comparable<Integer> comparable = arr[i];
        arr[i] = arr[j];
        arr[j] = comparable;
    }
}

package cn.itcast.algorithm.test;
import cn.itcast.algorithm.sort.Shell;
import java.util.Arrays;
/**
 * @author ：caizhengjie
 * @description：TODO
 * @date ：2021/1/30 4:46 下午
 */
public class ShellTest {
    public static void main(String[] args) {
        Integer[] arr = {9,1,2,5,7,4,8,6,3,5};
        Shell.sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

希尔排序的时间复杂度分析：

我们可以使用事后分析法对希尔排序和插入排序做性能比较。


在资料的测试数据文件夹下有一个reverse_shell_insertion.txt文件，里面存放的是从100000到1的逆向数据，我们 可以根据这个批量数据完成测试。测试的思想：在执行排序前前记录一个时间，在排序完成后记录一个时间，两个 时间的时间差就是排序的耗时。


希尔排序和插入排序性能比较测试代码：

package cn.itcast.algorithm.test;
import cn.itcast.algorithm.sort.Insertion;
import cn.itcast.algorithm.sort.Shell;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
/**
 * @author ：caizhengjie
 * @description：TODO
 * @date ：2021/1/30 5:07 下午
 */
public class SortCompare {
    public static void main(String[] args) throws Exception {
        // 创建一个ArrayList集合，保存读取出来的整数
        ArrayList<Integer> list = new ArrayList<>();
        // 读取reverse_arr.txt文件并保存到ArrayList中
        BufferedReader bufferedReader = new BufferedReader(
                new InputStreamReader(new FileInputStream("resources/reverse_arr.txt")));
        while (bufferedReader.readLine() != null){
            // line是字符串，把line换成Integer，存储到集合中
            int i = Integer.parseInt(bufferedReader.readLine());
            list.add(i);
        }
        bufferedReader.close();
        // 把集合转换成数组
        Integer[] arr = new Integer[list.size()];
        list.toArray(arr);
        // 调用测试代码完成测试
        // 希尔排序：18毫秒
        // testShell(arr);
        // 插入排序：5057毫秒
        testInsertion(arr);
    }
    /**
     * 测试希尔排序
     * @param arr
     */
    public static void testShell(Integer[] arr){
        // 获取执行前的时间
        long start = System.currentTimeMillis();
        // 执行算法代码
        Shell.sort(arr);
        // 获取执行之后的时间
        long end = System.currentTimeMillis();
        // 算出程序执行的时间并输出
        System.out.println("希尔排序的执行时间为："+(end - start)+"毫秒");
    }
    /**
     * 测试插入排序
     * @param arr
     */
    public static void testInsertion(Integer[] arr){
        // 获取执行前的时间
        long start = System.currentTimeMillis();
        // 执行算法代码
        Insertion.sort(arr);
        // 获取执行之后的时间
        long end = System.currentTimeMillis();
        // 算出程序执行的时间并输出
        System.out.println("插入排序的执行时间为："+(end - start)+"毫秒");
    }
}

通过测试发现，在处理大批量数据时，希尔排序的性能确实高于插入排序。






文章标签：
Java
搜索推荐
索引
API
关键词：
算法java
Java排序算法
排序算法Java
常见排序算法详解Java
游客wkxim4agoo6le
目录
相关文章
java冯坚持
|
1月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题：Dijkstra和Floyd算法详细描述，java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法，这两种算法分别用于解决单源和多源最短路径问题，并且提供了Java语言的实现代码。
java冯坚持
74 3
数据结构与算法细节篇之最短路径问题：Dijkstra和Floyd算法详细描述，java语言实现。
软件求生
|
3月前
|
搜索推荐 算法 Java
手写快排：教你用Java写出高效排序算法！
快速排序（QuickSort）是经典的排序算法之一，基于分治思想，平均时间复杂度为O(n log n)，广泛应用于各种场合。在这篇文章中，我们将手写一个Java版本的快速排序，从基础实现到优化策略，并逐步解析代码背后的逻辑。
软件求生
157 1
喜欢猪猪
|
1月前
|
算法 Java 数据中心
探讨面试常见问题雪花算法、时钟回拨问题，java中优雅的实现方式
【10月更文挑战第2天】在大数据量系统中，分布式ID生成是一个关键问题。为了保证在分布式环境下生成的ID唯一、有序且高效，业界提出了多种解决方案，其中雪花算法（Snowflake Algorithm）是一种广泛应用的分布式ID生成算法。本文将详细介绍雪花算法的原理、实现及其处理时钟回拨问题的方法，并提供Java代码示例。
喜欢猪猪
74 2
yinying293
|
3月前
|
算法 Java
LeetCode经典算法题：矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题：矩阵中省份数量经典题目+三角形最大周长java多种解法详解
yinying293
52 6
热爱技术的小郑
|
3月前
|
搜索推荐 算法 Java
经典排序算法之-----选择排序（Java实现）
这篇文章通过Java代码示例详细解释了选择排序算法的实现过程，包括算法的基本思想、核心代码、辅助函数以及测试结果，展示了如何通过选择排序对数组进行升序排列。
热爱技术的小郑
46 0
经典排序算法之-----选择排序（Java实现）
如夜了我衣衫太薄便归家靠路灯
|
3月前
|
搜索推荐 算法 Java
经典十大排序算法【Java版完整代码】
经典十大排序算法【Java版完整代码】
如夜了我衣衫太薄便归家靠路灯
70 1
yinying293
|
3月前
|
存储 算法 Java
LeetCode经典算法题：打家劫舍java详解
LeetCode经典算法题：打家劫舍java详解
yinying293
70 2
yinying293
|
3月前
|
人工智能 算法 Java
LeetCode经典算法题：井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题：井字游戏+优势洗牌+Dota2参议院java解法
yinying293
50 1
yinying293
|
3月前
|
存储 算法 Java
LeetCode经典算法题：预测赢家+香槟塔java解法
LeetCode经典算法题：预测赢家+香槟塔java解法
yinying293
61 1
土木林森
|
3月前
|
数据采集 搜索推荐 算法
【高手进阶】Java排序算法：从零到精通——揭秘冒泡、快速、归并排序的原理与实战应用，让你的代码效率飙升！
【8月更文挑战第21天】Java排序算法是编程基础的重要部分，在算法设计与分析及实际开发中不可或缺。本文介绍内部排序算法，包括简单的冒泡排序及其逐步优化至高效的快速排序和稳定的归并排序，并提供了每种算法的Java实现示例。此外，还探讨了排序算法在电子商务、搜索引擎和数据分析等领域的广泛应用，帮助读者更好地理解和应用这些算法。
土木林森
44 0

热门文章

最新文章

  • 1
    字符串相似度算法 递归与动态规划求解分析
  • 2
    【TDOA定位】基于chan和talor算法实现TDOA定位含性能对比matlab代码
  • 3
    【算法】算法之美—Fire Net
  • 4
    【编程练习】收集的一些c++代码片，算法排序，读文件，写日志，快速求积分等等
  • 5
    算法导论第十四章 数据结构的扩张
  • 6
    JVM内存模型及垃圾回收算法
  • 7
    【算法研究】Bresenham画线算法
  • 8
    openssl中算法的组织方式
  • 9
    iOS 算法之排序、查找、递归
  • 10
    【字符串处理算法】删除特定的字符的算法设计及C代码实现
  • 1
    Dubbo03【管理控制台和监控中心搭建】，Java开发实用必备的几款插件
    59
  • 2
    Java中int[]与Integer[]相互转化的方法，java基础知识面试重点总结
    37
  • 3
    Java 并发编程中的锁优化策略
    35
  • 4
    Java一分钟之-设计模式：装饰器模式与代理模式
    67
  • 5
    《手把手教你》系列技巧篇（四十六）-java+ selenium自动化测试-web页面定位toast-下篇（详解教程）
    66
  • 6
    刷题两个月，从入门到字节跳动offer丨GitHub标星16k+，美团Java面试题
    66
  • 7
    《MySQL 入门教程》第 05 篇 账户和权限，Java高并发编程详解深入理解pdf
    54
  • 8
    Java的前景如何，好不好自学？，万字Java技术类校招面试题汇总
    55
  • 9
    es集群安装，邮储银行java面试
    81
  • 10
    数据结构~缓存淘汰算法--LRU算法（Java的俩种实现方式，万字解析
    101

    • 相关课程

    更多
  • Java面试疑难点解析 - 面试技巧及语言基础
  • Java面试疑难点解析 - Java Web开发
  • Java面试疑难点解析 - 系统架构及项目设计
  • Java编程入门
  • Java面向对象编程
  • Java高级编程

    • 相关电子书

    更多
  • Spring Cloud Alibaba - 重新定义 Java Cloud-Native
  • The Reactive Cloud Native Arch
  • JAVA开发手册1.5.0

    • 相关实验场景

    更多
  • 使用Swing算法实现商品推荐
  • 阿里云平台上进行Java程序的编译与运行
  • RSA密码算法设计与实现
  • 欧拉图的构造性证明与算法实现
  • 使用Java面向对象编写网络通信程序应用
  • 手动部署Java Web环境（Alibaba Cloud Linux 2）
    • 下一篇
    无影云桌面