当前位置： 首页 > article >正文

详解java中的排序

article 2024/11/28 15:31:19

1. 题记

本文详解java中的排序。

2. 排序的基本概念

在 Java 中，排序是将一组数据元素按照特定的顺序（通常是升序或降序）重新排列的操作。排序算法的稳定性、时间复杂度和空间复杂度是衡量排序算法优劣的重要指标。
稳定性是指在排序过程中，如果两个元素的关键字相等，排序后它们的相对位置保持不变。时间复杂度反映了排序算法执行时间与数据规模之间的关系，空间复杂度则表示排序算法在执行过程中所需的额外存储空间。

3. Java 内置的排序方法

3.1 Arrays.sort()方法

  1. 基本数据类型排序：对于基本数据类型数组（如int[]、double[]、char[]等），Arrays.sort()方法提供了一种简单快捷的排序方式。例如，对一个整数数组进行排序：
import java.util.Arrays;
int[] numbers = {5, 3, 8, 2, 1};
Arrays.sort(numbers);
// 排序后numbers数组变为{1, 2, 3, 5, 8}

这个方法使用了优化的双轴快速排序（Dual - Pivot Quicksort）算法，时间复杂度在一般情况下为O(nlogn)，其中n是数组的长度。在最坏情况下（数组已经有序或接近有序），时间复杂度可能退化为O(n*n)，但这种情况很少出现。
2. 对象数组排序：当数组元素是对象时，需要对象实现Comparable接口或者提供一个Comparator接口的实现来定义排序规则。例如，有一个Person类：

class Person implements Comparable<Person> {
    int age;
    String name;
    public Person(int age, String name) {
        this.age = age;
        this.name = name;
    }
    @Override
    public int compareTo(Person other) {
        return this.age - other.age;
    }
}

可以这样排序：

Person[] persons = new Person[]{new Person(25, "Alice"), new Person(30, "Bob")};
Arrays.sort(persons);
// 排序后persons数组按照年龄从小到大排列
  1. Collections.sort()方法（用于List集合排序）
    当使用java.util.List集合（如ArrayList、LinkedList等）存储元素并需要排序时，可以使用Collections.sort()方法。例如，对于一个ArrayList存储整数：
import java.util.ArrayList;
import java.util.Collections;
ArrayList<Integer> list = new ArrayList<>();
list.add(5);
list.add(3);
list.add(8);
Collections.sort(list);
// 排序后list变为[3, 5, 8]

对于对象类型的List，同样需要元素实现Comparable接口或者提供Comparator实现。Collections.sort()方法内部也是基于数组排序算法实现的，时间复杂度和Arrays.sort()类似。

4. 常用排序算法及实现

4.1 冒泡排序（Bubble Sort）

  1. 基本原理：它是一种简单的排序算法，通过重复地走访要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
    示例：
public class BubbleSort {
    public static void bubbleSort(int[] array) {
        int n = array.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    // 交换元素
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }
}
  1. 时间复杂度：最坏情况和平均情况都是O(n*n)，最好情况（数组已经有序）是O(n)。

4.2 插入排序（Insertion Sort）

  1. 基本原理：它将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据。对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
    示例：
public class InsertionSort {
    public static void insertionSort(int[] array) {
        int n = array.length;
        for (int i = 1; i < n; i++) {
            int current = array[i];
            int j = i - 1;
            while (j >= 0 && array[j] > current) {
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = current;
        }
    }
}
  1. 时间复杂度：最坏情况和平均情况都是O(n*n)，最好情况（数组已经有序）是O(n)。

4.3 选择排序（Selection Sort）

  1. 基本原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
    示例：
public class SelectionSort {
    public static void selectionSort(int[] array) {
        int n = array.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            if (minIndex!= i) {
                // 交换元素
                int temp = array[i];
                array[i] = array[minIndex];
                array[minIndex] = temp;
            }
        }
    }
}
  1. 时间复杂度：最坏情况、平均情况和最好情况都是O(n*n)。

4.4 快速排序（Quicksort）

  1. 基本原理：它的基本思想是通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后分别对这两部分记录继续进行排序，以达到整个序列有序。
    示例（简单实现）：
public class QuickSort {
    public static void quickSort(int[] array, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(array, low, high);
            quickSort(array, low, pivotIndex - 1);
            quickSort(array, pivotIndex + 1, high);
        }
    }
    private static int partition(int[] array, int low, int high) {
        int pivot = array[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (array[j] <= pivot) {
                i++;
                // 交换元素
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        // 交换pivot和i + 1位置的元素
        int temp = array[i + 1];
        array[i + 1] = array[high];
        array[high] = temp;
        return i + 1;
    }
}
  1. 时间复杂度：平均情况是O(nlogn)，最坏情况（例如数组已经有序）是O(n*n)。

4.5 归并排序（Mergesort）

  1. 基本原理：它是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide - and - Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
    示例（简单实现）：
public class MergeSort {
    public static void mergeSort(int[] array) {
        if (array.length > 1) {
            int mid = array.length / 2;
            int[] left = new int[mid];
            int[] right = new int[array.length - mid];
            // 分割数组
            for (int i = 0; i < mid; i++) {
                left[i] = array[i];
            }
            for (int i = mid; i < array.length; i++) {
                right[i - mid] = array[i];
            }
            mergeSort(left);
            mergeSort(right);
            merge(array, left, right);
        }
    }
    private static void merge(int[] array, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                array[k++] = left[i++];
            } else {
                array[k++] = right[j++];
            }
        }
        while (i < left.length) {
            array[k++] = left[i++];
        }
        while (j < right.length) {
            array[k++] = right[j++];
        }
    }
}

时间复杂度：不管是最坏情况、平均情况还是最好情况，时间复杂度都是O(nlogn)，但它需要额外的空间来存储临时数组，空间复杂度是是O(n)。

5. Java中常用的其他第三方排序库

5.1 Guava

5.1.1 简介

Guava 是 Google 提供的一个广泛使用的 Java 核心库扩展，其中包含了强大的排序功能。它提供了丰富的工具方法来处理集合等数据结构，并且可以方便地进行排序操作。

5.1.2 排序相关功能：
  1. 对不可变集合排序：Guava 的ImmutableList等不可变集合可以使用ordering()方法进行排序。例如，对一个ImmutableList排序：
import com.google.common.collect.ImmutableList;
import com.google.common.collect.Ordering;
public class GuavaSortExample {
    public static void main(String[] args) {
        ImmutableList<Integer> numbers = ImmutableList.of(5, 3, 8, 2, 1);
        ImmutableList<Integer> sortedNumbers = Ordering.natural().sortedCopy(numbers);
        // sortedNumbers为[1, 2, 3, 5, 8]
    }
}

这里Ordering.natural()表示按照自然顺序（对于整数就是从小到大）排序，sortedCopy()方法会返回一个新的已排序的集合。
2. 自定义排序规则：可以通过Ordering类自定义排序规则。例如，对一个包含Person对象的ImmutableList按照年龄排序：

class Person {
    int age;
    String name;
    public Person(int age, String name) {
        this.age = age;
        this.name = name;
    }
}
import com.google.common.collect.ImmutableList;
import com.google.common.collect.Ordering;
public class GuavaSortPersonExample {
    public static void main(String[] args) {
        ImmutableList<Person> persons = ImmutableList.of(new Person(25, "Alice"), new Person(30, "Bob"));
        ImmutableList<Person> sortedPersons = Ordering.from((p1, p2) -> p1.age - p2.age).sortedCopy(persons);
        // sortedPersons按照年龄从小到大排序
    }
}

这里通过Ordering.from()方法传入一个比较器（这里使用 Lambda 表达式定义）来实现自定义排序。

5.2 Apache Commons Collections

5.2.1 简介

这是 Apache 提供的一个处理集合的工具库，它也包含了一些用于排序的实用方法。它提供了对各种集合类型的操作，并且在很多 Java 项目中用于补充 Java 标准库的功能。

5.2.2 排序相关功能：
  1. 对List排序：使用ListUtils类可以对java.util.List进行排序。例如：
import org.apache.commons.collections4.ListUtils;
import java.util.ArrayList;
import java.util.List;
public class CommonsCollectionsSortExample {
    public static void main(String[] args) {
        List<Integer> numbers = new ArrayList<>();
        numbers.add(5);
        numbers.add(3);
        numbers.add(8);
        List<Integer> sortedNumbers = ListUtils.sort(numbers);
        // sortedNumbers为[3, 5, 8]（假设按照自然顺序排序）
    }
}
  1. 对于自定义对象的排序，需要对象实现java.lang.Comparable接口或者提供一个Comparator接口实现，就像在 Java 标准库中排序一样。因为ListUtils.sort()方法内部也是基于java.util.Collections.sort()的原理实现的。

5.3 Eclipse Collections

5.3.1 简介

这是一个高性能、功能丰富的集合框架，它提供了高效的排序操作以及其他集合相关的高级功能。它的设计目标是提供更好的性能和更灵活的 API，并且与 Java 标准集合框架兼容。

5.3.2 排序相关功能：
  1. 快速排序操作：例如，对一个MutableList（Eclipse Collections 中的可变列表类型）进行排序：
import org.eclipse.collections.api.list.MutableList;
import org.eclipse.collections.impl.factory.Lists;
public class EclipseCollectionsSortExample {
    public static void main(String[] args) {
        MutableList<Integer> numbers = Lists.mutable.with(5, 3, 8, 2, 1);
        MutableList<Integer> sortedNumbers = numbers.sortThis();
        // sortedNumbers为[1, 2, 3, 5, 8]
    }
}
  1. 对于自定义对象排序，同样可以通过实现Comparable接口或者提供Comparator来定义排序规则。并且 Eclipse Collections 还支持更复杂的排序方式，如根据多个属性排序等高级操作。

6. 后记

在实际的 Java 编程中，排序是非常基础且重要的功能，大家一定要掌握。

本文完。
码字不易，宝贵经验分享不易，请各位支持原创，转载注明出处，多多关注作者，家人们的点赞和关注是我笔耕不辍的动力。


http://www.kler.cn/a/412936.html

相关文章：

  • Js-对象-04-Array
  • 365天深度学习训练营-第P6周：VGG-16算法-Pytorch实现人脸识别
  • 【Linux庖丁解牛】—软件安装vim！
  • 【软考速通笔记】系统架构设计师③——信息安全技术基础知识
  • 【作业九】RNN-SRN-Seq2Seq
  • CSDN 博客自动发布脚本（Python 含自动登录、定时发布）
  • Vue封装sql编辑器
  • Java基础面试题05：简述快速失败(fail-fast)和安全失败(fail-safe)的区别 ？
  • 【软件安装】在Ubuntu中安装mysql5.7
  • LeetCode【代码随想录】刷题（数组篇）
  • 深信服技术服务工程师（网络安全、云计算方向）面试题
  • XX科技面试笔试题
  • 操作系统 内存管理——针对实习面试
  • Python Selenium简介（三）
  • 【微服务】Nacos
  • Scrapy图解工作流程-cnblog
  • 《免费的学习网站推荐3》
  • PostgreSQL中的内存上下文管理
  • 量化交易系统
  • 什么是一份好的技术文档？
  • 【力扣热题100】—— Day2.移动零
  • MySQL解决数据导入导出含有外键的情况
  • Python学习第十三天--面向对象，类和对象
  • 量化交易系统开发-实时行情自动化交易-4.5.1.机器学习策略实现
  • 计算机网络安全实验-使用Kali进行Metasploit操作宿主机摄像头的相关操作步骤
  • 【Jenkins】自动化部署 maven 项目笔记