一文搞懂Java中的排序算法

Myth丶恋晨 2023-09-30 22:54 40阅读 0赞

> Java中的排序算法简介：初学者指南

微信搜索关注《Java学研大本营》，加入读者群，分享更多精彩

![f3322592b39ab3ff3dd727c83bfca5c3.png][]

### 简介 ###

排序算法是计算机科学的基础，它们提供了一种以结构化方式组织和管理数据的方法。从搜索数据集中的特定项目到优化数据处理，排序是每个程序员的一项基本技能。在这个初学者指南中，我们将向你介绍Java中一些流行的排序算法，并提供一些例子来帮助你理解它们的实现和使用。

### 排序算法的关键概念 ###

在深入研究具体的排序算法之前，了解一些基本概念是很重要的：

*  基于比较的排序与基于非比较的排序。基于比较的算法通过比较数据集的元素以确定它们的顺序，而非基于比较的算法则使用其他技术，如计数或弧度排序。
 *  稳定的与不稳定的排序。一个稳定的排序算法可以保持排序输出中相等元素的相对顺序，而一个不稳定的算法则不能保证这一点。
 *  就地排序与非就地排序。原地排序算法在原始内存位置对数据进行排序，需要最少的额外内存。离位算法则使用额外的内存来执行排序。
 *  时间复杂度和空间复杂度。这些措施表明一个算法的性能如何随着输入数据的大小而变化，帮助你评估其效率。

### Java中流行的排序算法 ###

让我们简单介绍一下一些流行的排序算法。

*  泡沫排序。一种简单的基于比较的算法，它重复地浏览列表，比较相邻的元素，如果它们的顺序不对，就把它们交换。这个过程不断重复，直到列表被排序。
 *  选择排序。另一种基于比较的算法，其工作原理是将输入分成一个已排序的区域和一个未排序的区域。它重复地从未排序区域选择最小（或最大）的元素，并将其移到排序区域的末端。
 *  插入式排序。这种基于比较的算法每次都会建立一个排序的输出。它对小型数据集或已经部分排序的数据来说是很有效的。
 *  合并排序。一种分而治之的算法，递归地将输入分成两半，对每一半进行排序，然后合并排序后的两半，产生最终的排序输出。
 *  快速排序。另一种分而治之的算法，其工作原理是从列表中选择一个“支点”元素，并根据其他元素是否小于或大于支点元素，将其分成两组。然后对这些子列表进行递归排序。

### 在Java中实现排序算法 ###

下面是每种算法的Java代码示例，以及对其工作原理的简要解释：

#### 泡沫排序： ####

public void bubbleSort(int[] arr) {
        int n = arr.length;
        boolean swapped;
        for (int i = 0; i < n - 1; i++) {
            swapped = false;
            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }
            if (!swapped) break;
        }
    }

在泡沫排序中，相邻的元素会被比较，如果它们的顺序不对就会被调换。这个过程重复进行，直到不需要交换为止，表明列表已经排序。

#### 选择排序: ####

public void selectionSort(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;
                }
            }
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }

在选择排序中，该算法将输入分为一个排序区域和一个未排序区域。它反复寻找未排序区域中的最小（或最大）元素，并将其移到排序区域的末端，直到整个列表被排序。

#### 插入排序: ####

public void insertionSort(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--;
            }
            arr[j + 1] = key;
        }
    }

插入式排序的工作方式是一次建立一个排序的输出。对于每个元素，该算法将其与排序区域中的元素进行比较，如果它们大于当前元素，则将其向右移动，并将该元素插入其正确位置。

#### 合并排序: ####

public void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }
    
    public void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;
    
        int[] leftArray = new int[n1];
        int[] rightArray = new int[n2];
    
        for (int i = 0; i < n1; i++) {
            leftArray[i] = arr[left + i];
        }
        for (int i = 0; i < n2; i++) {
            rightArray[i] = arr[mid + 1 + i];
        }
    
        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (leftArray[i] <= rightArray[j]) {
                arr[k++] = leftArray[i++];
            } else {
                arr[k++] = rightArray[j++];
            }
        }
    
        while (i < n1) {
            arr[k++] = leftArray[i++];
        }
        while (j < n2) {
            arr[k++] = rightArray[j++];
        }
    }

合并排序是一种分而治之的算法，它递归地将输入分成两半，对每一半进行排序，然后将排序后的两半合并，产生最终的排序输出。`merge`函数将两个排序的子数组合并为一个排序的数组。

#### 快速排序 ####

public void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(arr, low, high);
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }
    
    public 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;
    }

快速排序是另一种分而治之的算法，其工作原理是从列表中选择一个“枢轴”元素，并根据其他元素是否小于或大于枢轴，将其分成两组。然后对这些子列表进行递归排序。分区函数对数组进行重新排列，并返回枢轴索引。

### 选择正确的排序算法 ###

在选择排序算法时，要考虑以下因素:

*  数据集的大小
 *  数据是否已经被部分排序
 *  稳定性或额外内存使用的重要性

请记住，每种算法都有其最佳情况、平均情况和最坏情况，这些情况会影响性能。了解这些情况将有助于你根据问题和数据集选择正确的算法。

### 结论 ###

了解Java中的排序算法对任何程序员都是至关重要的，因为它有助于优化数据处理和操作任务。通过练习所提供的例子和探索更高级的排序算法，你将在计算机科学的这个重要领域打下坚实的基础。欢迎你扫码关注我们，分享你在排序算法方面的经验。

### 推荐书单 ###

#### 《Java编程讲义》 ####

《Java编程讲义》根据目前Java开发领域的实际需求，从初学者角度出发，详细讲解了Java技术的基础知识。全书共15章，包括Java开发入门，Java语言基础，Java控制结构，数组，面向对象编程，继承和多态，抽象类、接口和内部类，异常处理，Java常用类库，集合与泛型，Lambda表达式，输入-输出流，多线程，JDBC数据库技术，网络编程等内容。内容全面覆盖．1ava开发必备的基础知识点，结合生活化案例展开讲解，程序代码给出了详细的注释，能够使初学者轻松领会Java技术精髓，快速掌握Java开发技能。　　《Java编程讲义》适合作为高等院校相关专业的教材及教学参考书，也适合作为Java开发入门者的自学用书，还可供开发人员查阅、参考。

**购买链接：https://item.jd.com/13495830.html**

![52953030f82ae03939638e2b91ae1096.png][]

> > ### 精彩回顾 ###
> > 
> > [一文搞懂Java的装饰器设计模式][Java]
> > 
> > [一文搞懂Java的工厂设计模式][Java 1]
> > 
> > [Java中的内存管理和垃圾回收机制 (下)][Java_]
> > 
> > [Java中的内存管理和垃圾回收机制 (中)][Java_ 1]
> > 
> > [Java中的内存管理和垃圾回收机制 (上)][Java_ 2]

> > 微信搜索关注《Java学研大本营》
> > 
> > 访问【IT今日热榜】，发现每日技术热点

[f3322592b39ab3ff3dd727c83bfca5c3.png]: https://img-blog.csdnimg.cn/img_convert/f3322592b39ab3ff3dd727c83bfca5c3.png
[52953030f82ae03939638e2b91ae1096.png]: https://img-blog.csdnimg.cn/img_convert/52953030f82ae03939638e2b91ae1096.png
[Java]: https://mp.weixin.qq.com/s?__biz=MzkzMDM3MjI3Nw==&mid=2247486795&idx=1&sn=2a794b46dc6ffbdd34b085c2819b6bab&scene=21#wechat_redirect
[Java 1]: https://mp.weixin.qq.com/s?__biz=MzkzMDM3MjI3Nw==&mid=2247486557&idx=1&sn=4c0c2d13cca6d560962a4ef995fd413c&scene=21#wechat_redirect
[Java_]: https://mp.weixin.qq.com/s?__biz=MzkzMDM3MjI3Nw==&mid=2247487011&idx=1&sn=7392f7750114450771d6681d616101b4&scene=21#wechat_redirect
[Java_ 1]: https://mp.weixin.qq.com/s?__biz=MzkzMDM3MjI3Nw==&mid=2247487010&idx=1&sn=3d01acebf7ef89127b351246b3d6ad8c&scene=21#wechat_redirect
[Java_ 2]: https://mp.weixin.qq.com/s?__biz=MzkzMDM3MjI3Nw==&mid=2247487005&idx=1&sn=0f6a8adcc68a63d44b27204be9c5501e&scene=21#wechat_redirect