【Java数据结构】想进大厂必须牢记于心的——常见八大排序算法(上)

简介: 笔记

🛸基本概念


⭐排序


排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。

平时的上下文中,如果提到排序,通常指的是排升序(非降序)。

通常意义上的排序,都是指的原地排序(in place sort)。


⭐稳定性


两个相等的数据,如果经过排序后,排序算法能 保证其相对位置不发生变化 ,则我们称该算法是具备 稳定性 的排序算法20.png


🛸七大基于比较的排序

21.png


⭐插入排序


🎄1. 直接插入排序


思路:


插入排序基本思想是将一个记录插入到已经排好序的有序表中,从而变成一个新的、记录数增1的有序表。

在其实现过程使用双层循环,外层循环对 除了第一个元素之外的所有元素,内层循环对 当前元素前面有序表进行待插入位置查找,并进行移动

图解:

22.gif


代码实现:


22.gif

     /**
     * 时间复杂度:
     *        最好:O(N) -> 数据是有序的
     *
     *        最坏:O(N^2) -> 无序的数据
     *
     * 空间复杂度:O(1)
     * 稳定性:稳定排序
     * @param array
     */
    //插入排序
    public static void insertSort (int[]array){
        for (int i = 1; i<array.length; i++){//外循环
        //从1开始表示:假设array[0] 已经放好位置了
        //后面的数字就是插入到它左边还是右边的问题。
            int tmp = array[i];//设置一个缓存tmp
            int j = i-1;
            for (; j >=0 ; j--){//内循环
                if (array[j]>tmp){//如果array[j]大于缓存值,说明要换位置
                    array[j+1] = array[j];
                }else{//否则直接退出当前这一次的循环
                    break;
                }
            }
            //最后记得要把缓存值插入到表中
            array[j+1] = tmp;//j此时有可能已经是-1了,所以要变成0下标就得+1
        }
    }

🎄2. 希尔排序(直接插入排序的优化)


思路:

希尔排序法又称缩小增量法。

希尔排序法的基本思想是:

先选定一个整数(gap),把待排序文件中所有记录分成gap个组,所有距离为gap的记录分在同一组内,并对每一组内的记录进行排序。然后,取gap / 2,重复上述分组和排序的工作。当gap到达1时,所有记录在同一组内排好序。

注意gap的问题:

23.png

1.希尔排序是对直接插入排序的优化。

2.当gap > 1时都是预排序,目的是让数组更接近于有序。当gap == 1时,数组已经接近有序的了,这时 相当于直接用插入排序,这样就会很快,因为 直接插入排序是越有序越快。这样整体而言,可以达到优化的效果。我们实现后可以进行性能测试的对比。

图解:

24.png

代码实现:

/**
     * @param array 排序的数组
     * @param gap   每组的间隔  -》 组数
     */
    public static void shell(int[] array,int gap) {
    //如果将gap全部换成1,会发现其实就是直接插入排序
    //所以当gap到1的时候,这就表示这是最后一次排序
    //这最后一次排序其实就是一个直接插入排序
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i-gap;
            for (; j >= 0; j -= gap) {
                if(array[j] > tmp) {
                    array[j+gap] = array[j];
                }else {
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }
    /**
     * 时间复杂度:不好算  n^1.3 - n^1.5 之间
     * 空间复杂度:O(1)
     * 稳定性:不稳定的排序
     *      技巧:如果在比较的过程当中 没有发生跳跃式的交换 那么就是稳定的
     * @param array
     */
    public static void shellSort(int[] array) {
        //处理gap
        int gap = array.length;
        while (gap > 1) {
            gap /= 2;//保证最后一个序列间隔是 1  除几都行
            shell(array,gap);
        }
    }


⭐选择排序


🎄3. 选择排序


思路:

将一组数据分为有序区(排过序的数据)和无序区(未排序数据),每一次从无序区间选出最大(或最小)的一个元素,存放在无序区间的最后(或最前),直到全部待排序的数据元素排完 。


选择排序的步骤:

1>首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置。

2>再从剩余未排序元素中继续寻找最小(大)元素,然后放到未排序序列的起始位置。

3>重复第二步,直到所有元素均排序完毕。


图解:

25.gif

代码实现:

/**
     * 时间复杂度:
     *      最好:O(N^2)
     *      最坏:O(N^2)
     * 空间复杂度:O(1)
     * 稳定性:不稳定的
     * @param array
     */
    public static void selectSort(int[] array) {
        for (int i = 0; i < array.length; i++) {//下标i前边的为有序区间
            for (int j = i+1; j < array.length; j++) {
                if(array[j] < array[i]) {
                    int tmp = array[i];
                    array[i] = array[j];
                    array[j] = tmp;
                }
            }
        }
    }


🎄4.堆排序(如果不了解堆的话可以看看我上一篇讲 堆 的博客)


思路:


准备知识:

堆的结构可以分为大根堆和小根堆,是一个 完全二叉树,而堆排序是根据堆的这种数据结构设计的一种排序,下面先来看看什么是大根堆和小根堆


性质:

每个结点的值都大于其左孩子和右孩子结点的值,称之为大根堆;

每个结点的值都小于其左孩子和右孩子结点的值,称之为小根堆。

如下图

50.png

我们对上面的图中每个数都进行了标记,上面的结构映射成数组就变成了下面这个样子

51.png

基本步骤:


首先将待排序的数组构造成一个大根堆(升序用大根堆,降序就用小根堆),此时,整个数组的最大值就是堆结构的顶端

将顶端的数与末尾的数交换,此时,末尾的数为最大值,将末尾这个最大值提取出去,剩余待排序数组个数为n-1

将剩余的n-1个数再构造成大根堆,再将顶端数与n-1位置的数交换,如此反复执行,便能得到有序数组

图解:52.gif

代码实现:

    //堆的向下调整
    public static void siftDown(int[] array,int root,int len) {//len表示末尾元素下标
        int parent = root;
        int child = 2*parent+1;//先找到左孩子节点
        while (child <= len) {//当child>length的时候说明当前子树已经调整好了
             //先根据左孩子节点判断右孩子节点是否存在,且是否大于左孩子节点
            if(child+1 <= len && array[child] < array[child+1]) {//如果存在,且值大于左孩子节点
                child++;
            }
            //child的下标就是左右孩子的最大值下标
            if(array[child] > array[parent]) {//如果孩子节点最大值,大于父节点,则要交换位置,因为要建大根堆
                int tmp = array[child];
                array[child] = array[parent];
                array[parent] = tmp;
                //继续向下看是否符合大根堆的条件
                parent = child;//更新parent下标
                child = 2*parent+1;//更新child下标
            }else {//否则不用换位置
                break;
            }
        }
    }
    //建堆
    public static void createHeap(int[] array) {
        //从小到大排序 -》 大根堆
        for (int i = (array.length-1 - 1) / 2;  i >= 0 ; i--) {
            siftDown(array,i,array.length-1);
        }
    }
    /**
     * 时间复杂度:O(N*logN)  都是这个时间复杂度
     * 复杂度:O(1)
     * 稳定性:不稳定的排序
     * @param array
     */
    public static void heapSort(int[] array) {
        createHeap(array);//O(n)
        int end = array.length-1;//end表示当前末尾元素的下标
        while (end > 0) {//O(N*logN)
            int tmp = array[end];//因为要交换末尾与堆顶元素,所以先缓存末尾元素
            //已经建好堆了,这时堆顶(0下标元素)就是当前的最大值
            array[end] = array[0];//将他提取出来,放到数组的末尾,固定住
            array[0] = tmp;//将末尾元素换到堆顶
            end--;//固定了一个当前堆中的最大值之后,下一次参与排序的元素就得减少一个
            siftDown(array,0,end);//将剩余元素继续变成一个大根堆
        }
    } 
相关文章
|
1月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
69 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
23天前
|
存储 Java
Java中的HashMap和TreeMap,通过具体示例展示了它们在处理复杂数据结构问题时的应用。
【10月更文挑战第19天】本文详细介绍了Java中的HashMap和TreeMap,通过具体示例展示了它们在处理复杂数据结构问题时的应用。HashMap以其高效的插入、查找和删除操作著称,而TreeMap则擅长于保持元素的自然排序或自定义排序,两者各具优势,适用于不同的开发场景。
38 1
|
25天前
|
存储 Java
告别混乱!用Java Map优雅管理你的数据结构
【10月更文挑战第17天】在软件开发中,随着项目复杂度增加,数据结构的组织和管理至关重要。Java中的Map接口提供了一种优雅的解决方案,帮助我们高效、清晰地管理数据。本文通过在线购物平台的案例,展示了Map在商品管理、用户管理和订单管理中的具体应用,有效提升了代码质量和维护性。
80 2
|
25天前
|
存储 Java 开发者
Java Map实战:用HashMap和TreeMap轻松解决复杂数据结构问题!
【10月更文挑战第17天】本文深入探讨了Java中HashMap和TreeMap两种Map类型的特性和应用场景。HashMap基于哈希表实现,支持高效的数据操作且允许键值为null;TreeMap基于红黑树实现,支持自然排序或自定义排序,确保元素有序。文章通过具体示例展示了两者的实战应用,帮助开发者根据实际需求选择合适的数据结构,提高开发效率。
57 2
|
8天前
|
缓存 算法 Java
本文聚焦于Java内存管理与调优,介绍Java内存模型、内存泄漏检测与预防、高效字符串拼接、数据结构优化及垃圾回收机制
在现代软件开发中,性能优化至关重要。本文聚焦于Java内存管理与调优,介绍Java内存模型、内存泄漏检测与预防、高效字符串拼接、数据结构优化及垃圾回收机制。通过调整垃圾回收器参数、优化堆大小与布局、使用对象池和缓存技术,开发者可显著提升应用性能和稳定性。
29 6
|
14天前
|
存储 Java 索引
Java中的数据结构:ArrayList和LinkedList的比较
【10月更文挑战第28天】在Java编程世界中,数据结构是构建复杂程序的基石。本文将深入探讨两种常用的数据结构:ArrayList和LinkedList,通过直观的比喻和实例分析,揭示它们各自的优势与局限,帮助你在面对不同的编程挑战时做出明智的选择。
|
22天前
|
存储 算法 Java
Java 中常用的数据结构
【10月更文挑战第20天】这些数据结构在 Java 编程中都有着广泛的应用,掌握它们的特点和用法对于提高编程能力和解决实际问题非常重要。
24 6
|
23天前
|
存储 Java 开发者
Java中的Map接口提供了一种优雅的方式来管理数据结构,使代码更加清晰、高效
【10月更文挑战第19天】在软件开发中,随着项目复杂度的增加,数据结构的组织和管理变得至关重要。Java中的Map接口提供了一种优雅的方式来管理数据结构,使代码更加清晰、高效。本文通过在线购物平台的案例,展示了Map在商品管理、用户管理和订单管理中的具体应用,帮助开发者告别混乱,提升代码质量。
26 1
|
29天前
|
存储 算法 Java
Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性
Java Set因其“无重复”特性在集合框架中独树一帜。本文解析了Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性,并提供了最佳实践建议,包括选择合适的Set实现类和正确实现自定义对象的hashCode()与equals()方法。
32 4
|
1月前
|
存储 算法 Java
Java常用的数据结构
【10月更文挑战第3天】 在 Java 中,常用的数据结构包括数组、链表、栈、队列、树、图、哈希表和集合。每种数据结构都有其特点和适用场景,如数组适用于快速访问,链表适合频繁插入和删除,栈用于实现后进先出,队列用于先进先出,树和图用于复杂关系的表示和查找,哈希表提供高效的查找性能,集合用于存储不重复的元素。合理选择和组合使用这些数据结构,可以显著提升程序的性能和效率。