首页 > 编程语言 >排序算法：从原理到 Java 实现

排序算法：从原理到 Java 实现

时间：2024-11-01 17:16:31浏览次数：3  
标签：arr Java int 复杂度 元素 算法 排序

文章目录

排序算法：从原理到 Java 实现

一、引言

排序算法是计算机科学中最基本和最重要的算法之一。无论是在数据库查询、文件系统管理还是在日常的编程任务中，我们都经常需要对数据进行排序。本文将深入探讨几种常见的排序算法，包括冒泡排序、选择排序、插入排序、快速排序、归并排序以及堆排序，并通过 Java 代码实现来帮助读者更好地理解它们的工作原理。

二、常见排序算法原理及 Java 实现

（一）冒泡排序（Bubble Sort）

  1. 原理
    • 冒泡排序是一种简单的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。
    • 遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
  2. Java 实现
public class BubbleSort {
    public static void sort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // 交换 arr[j+1] 和 arr[j]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

（二）选择排序（Selection Sort）

  1. 原理
    • 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
    • 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
    • 以此类推，直到所有元素均排序完毕。
  2. Java 实现
public class SelectionSort {
    public static void sort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // 交换 arr[i] 和 arr[minIndex]
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

（三）插入排序（Insertion Sort）

  1. 原理
    • 把待排序的数组分成已排序和未排序两部分。
    • 初始时，已排序部分只有一个元素，即数组的第一个元素。
    • 从第二个元素开始，将每个元素插入到已排序部分的适当位置，使得已排序部分始终保持有序。
  2. Java 实现
public class InsertionSort {
    public static void sort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; ++i) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }
}

（四）快速排序（Quick Sort）

  1. 原理
    • 通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小。
    • 然后分别对这两部分记录继续进行排序，以达到整个序列有序。
  2. Java 实现
public class QuickSort {
    public static void sort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            sort(arr, low, pi - 1);
            sort(arr, pi + 1, high);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return i + 1;
    }
}

（五）归并排序（Merge Sort）

  1. 原理
    • 采用分治策略，将待排序数组分成两个子数组，分别对两个子数组进行排序。
    • 然后将两个已排序的子数组合并成一个有序的数组。
  2. Java 实现
public class MergeSort {
    public static void sort(int[] arr) {
        if (arr.length > 1) {
            int mid = arr.length / 2;
            int[] left = new int[mid];
            int[] right = new int[arr.length - mid];
            System.arraycopy(arr, 0, left, 0, mid);
            System.arraycopy(arr, mid, right, 0, arr.length - mid);
            sort(left);
            sort(right);
            merge(arr, left, right);
        }
    }

    private static void merge(int[] arr, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;
        while (i < left.length && j < right.length) {
            if (left[i] < right[j]) {
                arr[k++] = left[i++];
            } else {
                arr[k++] = right[j++];
            }
        }
        while (i < left.length) {
            arr[k++] = left[i++];
        }
        while (j < right.length) {
            arr[k++] = right[j++];
        }
    }
}

（六）堆排序（Heap Sort）

  1. 原理
    • 堆排序是利用堆这种数据结构而设计的一种排序算法。堆是一种完全二叉树，它分为大顶堆和小顶堆。
    • 大顶堆的每个节点的值都大于或等于其子节点的值，小顶堆的每个节点的值都小于或等于其子节点的值。
    • 堆排序的基本思想是将待排序的序列构建成一个堆，然后将堆顶元素与堆的最后一个元素交换，再对剩余的元素重新构建堆，直到整个序列有序。
  2. Java 实现
public class HeapSort {
    public static void sort(int[] arr) {
        int n = arr.length;
        // 构建大顶堆
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }
        // 排序
        for (int i = n - 1; i > 0; i--) {
            // 将堆顶元素与最后一个元素交换
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            // 对剩余的元素重新构建堆
            heapify(arr, i, 0);
        }
    }

    private static void heapify(int[] arr, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }
        if (largest!= i) {
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;
            // 递归调整子树
            heapify(arr, n, largest);
        }
    }
}

三、性能比较与分析

（一）时间复杂度

  1. 冒泡排序、选择排序、插入排序：
    • 这三种排序算法的时间复杂度都是O(n^2)，其中n是待排序数组的长度。在最坏情况下，即数组完全逆序时，需要进行n(n-1)/2次比较和交换操作。
  2. 快速排序：
    • 平均时间复杂度为O(nlogn)，最坏情况下为O(n^2)。当每次划分都不均匀时，会退化为冒泡排序的时间复杂度。但在实际应用中，快速排序的性能通常非常好。
  3. 归并排序：
    • 无论在最好、最坏还是平均情况下，时间复杂度都是O(nlogn)。这是因为归并排序每次都将数组分成两个子数组，然后分别对两个子数组进行排序，最后将两个已排序的子数组合并成一个有序的数组。
  4. 堆排序：
    • 时间复杂度为O(nlogn)。堆排序的时间复杂度主要取决于构建堆和调整堆的过程。构建堆的时间复杂度为O(n)，调整堆的时间复杂度为O(logn)，因此堆排序的总时间复杂度为O(nlogn)。

（二）空间复杂度

  1. 冒泡排序、选择排序、插入排序：
    • 这三种排序算法都是原地排序算法，空间复杂度为O(1)。它们只需要常数级别的额外空间来进行排序操作。
  2. 快速排序：
    • 平均情况下空间复杂度为O(logn)，最坏情况下为O(n)。快速排序在递归过程中需要使用栈空间来存储函数调用的上下文信息。
  3. 归并排序：
    • 空间复杂度为O(n)。归并排序在合并两个子数组时需要额外的空间来存储临时结果。
  4. 堆排序：
    • 空间复杂度为O(1)。堆排序是原地排序算法，只需要常数级别的额外空间来进行排序操作。

（三）稳定性

  1. 冒泡排序、插入排序、归并排序：
    • 这三种排序算法是稳定的排序算法，即如果两个元素相等，在排序后它们的相对顺序不会改变。
  2. 选择排序、快速排序、堆排序：
    • 这三种排序算法是不稳定的排序算法。例如，在选择排序中，每次选择最小元素并与当前位置的元素交换时，可能会改变相等元素的相对顺序。

四、题外话

（一）稳定性是什么？

排序算法的不稳定性是指在排序过程中，具有相同值的元素的相对顺序可能会发生改变。

例如，对于一个包含多个具有相同值元素的序列进行不稳定排序时，这些相同值元素在排序后的相对位置与初始状态相比可能会不同；而稳定排序算法则能保证具有相同值的元素在排序前后的相对位置不变。

（二）稳定性在实际应用中是一个重要的考虑因素吗？

一、稳定性重要的场景

  1. 数据库排序
    • 在数据库管理系统中，如果对包含多个字段的记录进行排序，稳定性可以确保在主要字段值相同时，按照次要字段的原始顺序排列。例如，先按照成绩降序排序，成绩相同的情况下按照学号升序排序。如果排序算法不稳定，可能会导致学号的顺序变得混乱，影响查询结果的准确性和可预测性。
  2. 多关键字排序
    • 当需要根据多个属性对对象进行排序时，稳定性可以确保在前面的属性值相同的情况下，后面的属性排序不会破坏已有的顺序。比如对学生先按照班级排序，再在班级内按照成绩排序。如果算法不稳定，可能会导致在班级内成绩相同的学生的相对顺序发生变化，给后续的分析和处理带来麻烦。
  3. 金融交易排序
    • 在金融领域，交易记录的顺序可能具有重要意义。如果对交易按照时间戳和金额进行排序，稳定性可以确保在时间戳相同的情况下，交易的原始顺序得以保留。这对于审计、合规性检查以及分析交易趋势等任务非常重要，因为顺序的变化可能会影响对交易流程和时间顺序的理解。

二、稳定性不太重要的场景

  1. 一般数据分析
    • 在某些数据分析任务中，只关注数据的整体分布和统计特征，而不关心相同值元素的具体顺序。例如，计算数据集的均值、中位数、标准差等统计量时，排序的稳定性并不影响结果。此时，可以选择更高效的不稳定排序算法，以提高计算速度。
  2. 图像和信号处理
    • 在图像和信号处理领域，数据通常以矩阵或向量的形式表示，排序操作相对较少。而且，即使进行排序，通常也是对单个维度进行，并且不关心相同值元素的顺序。例如，在对图像的像素强度进行排序以找到最大值或最小值时，稳定性不是关键因素。

（三）有些算法又稳定又快，为什么还需要有那么多排序算法？

一、不同场景的适用性不同

  1. 数据特点
    • 不同的数据集可能具有不同的特点。例如，对于近乎有序的数据集，插入排序可能非常高效；而对于数据量大且分布比较随机的情况，快速排序等更复杂的算法可能表现更好。
    • 如果数据中包含大量重复元素，稳定排序可能更有优势以保持相同元素的相对顺序，但在某些情况下，对稳定性要求不高时，不稳定排序算法可能速度更快。
  2. 数据规模
    • 对于小型数据集，简单的排序算法如冒泡排序可能就足够快，而复杂的稳定且快速的算法可能会引入过多的开销。
    • 对于超大规模数据集，可能需要考虑分布式排序等特殊的方法，而不仅仅是传统的单一算法。

二、算法的空间复杂度

稳定且快速的排序算法可能需要较大的额外空间。例如，归并排序虽然稳定且在很多情况下效率较高，但它需要额外的与输入数据规模相同的空间来进行合并操作。在内存受限的环境中，这可能成为一个问题。

三、实现复杂性和资源需求

  1. 编程复杂性
    • 一些稳定且快速的排序算法可能在实现上比较复杂，需要更多的代码和调试时间。这可能会增加开发成本和引入潜在的错误。
  2. 硬件资源
    • 某些算法可能对特定的硬件资源有较高的要求。例如，一些算法可能更适合在具有大量内存的系统上运行，而在资源受限的嵌入式系统或移动设备上，可能需要更简单、资源需求低的排序算法。

四、特殊需求

  1. 实时性要求
    • 在某些实时系统中，对排序的时间要求非常严格，可能需要根据具体的实时约束选择特定的算法，而不一定是通用的稳定且快速的算法。
  2. 特定数据类型或结构
    • 对于特定的数据类型，如链表、树等数据结构，可能需要专门设计的排序算法，而通用的稳定且快速的排序方法可能并不适用。

综上所述，虽然稳定且快速的排序方法在很多情况下是理想的选择，但不能解决所有的排序问题，需要根据具体的应用场景和需求来选择最合适的排序算法。

五、总结

排序算法是计算机科学中的基础算法之一，掌握不同的排序算法对于提高编程能力和解决实际问题非常重要。本文介绍了六种常见的排序算法，包括冒泡排序、选择排序、插入排序、快速排序、归并排序以及堆排序，并通过 Java 代码实现展示了它们的工作原理。在实际应用中，我们需要根据数据规模、时间复杂度、空间复杂度和稳定性等因素选择合适的排序算法。希望本文能够帮助读者更好地理解排序算法，并在实际编程中灵活运用。

标签：arr,Java,int,复杂度,元素,算法,排序
From： https://blog.csdn.net/KELLENSHAW/article/details/143436200

相关文章

  • 基于springboot的Java学习论坛平台
    基于springboot的Java学习论坛平台摘要在Internet高速发展的今天，我们生活的各个领域都涉及到计算机的应用，其中包括学习平台的网络应用，在外国学习平台已经是很普遍的方式，不过国内的管理平台可能还处于起步阶段。学习平台具有学习信息管理功能的选择。学习平台采用java技术......
  • Java方法设计原则与实践：从Effective Java到团队案例
    作者：京东物流京东物流背景本文通过阅读《EffectiveJava》、《CleanCode》、《京东JAVA代码规范》等代码质量书籍，结合团队日常代码实践案例进行整理，抛砖引玉、分享一些在编写高质量代码方面的见解和经验。这些书籍提供了丰富的理论知识，而团队的实际案例则展示了这些原则在实际......
  • 【Java】ThreadLocal详解
    引言在多线程编程中，如何安全地共享数据是一个重要的课题。Java提供了ThreadLocal类，以便在每个线程中维护线程局部变量，允许每个线程拥有自己的独立变量副本。本文将探讨ThreadLocal的工作原理、使用场景以及一些最佳实践。1.什么是ThreadLocal？ThreadLocal是Java......
  • 人脸识别算法 - 专利1分析
      专利CN117576758A中说明了一种人脸识别算法的整体识别流程，本文将对这篇文章进行详细讲解，并说明有创造性的算法部分。  前置知识：人脸识别   人脸识别技术是一种通过计算机技术和模式识别算法来识别和验证人脸的技术。它能够用于识别人脸的身份、检测人脸的表情......
  • 车辆违停视频分析网关AI智能分析车辆检测算法在车辆智能管控场景中的应用
    随着人工智能技术的快速发展，视频AI智能分析网关在车辆检测与车牌识别领域的应用越来越广泛。尤其在智能交通管理领域，这一技术正发挥着至关重要的作用。视频分析网关AI智能分析车辆检测算法，基于深度学习技术，通过训练大量标注数据，实现了对视频中车辆的快速、准确检测与车牌识别。这......
  • 离岗检测视频分析网关AI智能分析在岗离岗检测算法的原理与应用
    在岗离岗检测算法是一项利用计算机视觉和深度学习技术的应用，它通过解析监控视频流来辨认和追踪人员，进而确定他们是否处于特定的工作区域内。算法网关视频分析网关在众多领域中都有着重要的应用价值，特别是在那些需要确认员工在岗状态的场景中，例如在工厂、仓库、银行、医院等场所。......
  • 二：java 基础知识（2）-- 初始java/语法基础
    目录idea中文插件第一个Java程序Java数据类型，常量与变量1.数据类型    1.1基本数据类型    1.2引用数据类型2.常量2.1特性2.2 定义常量​编辑3.变量        3.1 变量的定义与初始化        3.2变量的类型局部变量：在......
  • 智慧工地算法视频分析服务器区域入侵检测AI视频分析技术在煤矿的实战应用
    智慧煤矿中应用的智慧矿山算法视频分析服务器，依托于人工智能算法对矿井下的视频资料进行深入的分析与处理。这项技术能够利用图像识别和模式识别等方法，实时监测视频中的重要信息，包括工作人员的行为、设备运行状况以及环境指标等，为煤矿的安全作业和预防事故提供了强有力的技术支......
  • Java 在金融科技(FinTech)中的应用
    在探讨Java在金融科技(FinTech)中的应用时，首先要明白Java由于其高性能、安全性、可移植性等特性，在金融行业中占据了举足轻重的地位。这些特点使得Java成为开发高频交易系统、风险管理平台、数据处理框架等金融应用的首选语言。尤其是在安全性方面，Java提供了一套严格的安全机制，包......
  • Java 字符流详解
    在Java的I/O体系中，字符流（Reader和Writer）是专门用于处理文本数据的输入输出流。与字节流不同，字符流以字符为单位进行读取和写入，能够更好地处理文本信息，尤其是包含多字节字符（如中文）的文本文件。本文将从字符流的类关系图开始，详细介绍字符流的原理、使用方法以及常见问题......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99