Java数组篇[9]：数组排序算法大比拼

哈喽，各位小伙伴们，你们好呀，我是喵手。运营社区：C站/掘金/腾讯云/阿里云/华为云/51CTO；欢迎大家常来逛逛

今天我要给大家分享一些自己日常学习到的一些知识点，并以文字的形式跟大家一起交流，互相学习，一个人虽可以走的更快，但一群人可以走的更远。

我是一名后端开发爱好者，工作日常接触到最多的就是Java语言啦，所以我都尽量抽业余时间把自己所学到所会的，通过文章的形式进行输出，希望以这种方式帮助到更多的初学者或者想入门的小伙伴们，同时也能对自己的技术进行沉淀，加以复盘，查缺补漏。

小伙伴们在批阅的过程中，如果觉得文章不错，欢迎点赞、收藏、关注哦。三连即是对作者我写作道路上最好的鼓励与支持！

前言

排序算法是计算机科学中的基石之一。在Java编程中，掌握不同的排序算法对于处理数据集合至关重要。

摘要

本文将介绍几种常见的排序算法，并在Java中实现它们。我们还将比较它们的性能和适用场景。

概述

排序算法可以根据时间复杂度、空间复杂度和稳定性等不同标准进行分类。常见的排序算法包括冒泡排序、选择排序、插入排序、归并排序和快速排序等。

冒泡排序

冒泡排序通过重复遍历要排序的数列，比较每对相邻元素的大小，并在必要时交换它们的位置。

代码语言：java复制

void bubbleSort(int[] array) {
    boolean swapped;
    for (int i = 0; i < array.length - 1; i  ) {
        swapped = false;
        for (int j = 0; j < array.length - 1 - i; j  ) {
            if (array[j] > array[j   1]) {
                // Swap elements
                int temp = array[j];
                array[j] = array[j   1];
                array[j   1] = temp;
                swapped = true;
            }
        }
        if (!swapped) break; // Optimization if the array is already sorted
    }
}

针对如上示例代码，这里我给大家详细的代码剖析下，以便于帮助大家理解的更为透彻，帮助大家早日掌握。

这段Java代码实现了冒泡排序算法。冒泡排序是一种简单的排序算法，它重复地遍历要排序的数组，比较相邻的元素，并在必要时交换它们的位置。以下是对代码的逐行解释：

void bubbleSort(int[] array) {：定义了一个名为bubbleSort的方法，它接受一个整型数组array作为参数。
boolean swapped;：声明了一个布尔类型的变量swapped，用于跟踪在内层循环中是否发生了元素交换。
for (int i = 0; i < array.length - 1; i ) {：外层循环，从索引0开始，直到数组的倒数第二个元素。array.length - 1确保了循环不会超出数组边界。
swapped = false;：在每次外层循环开始时，将swapped标志设置为false。
for (int j = 0; j < array.length - 1 - i; j ) {：内层循环，从索引0开始，每次迭代后减少遍历的范围，因为经过每次外层循环，最大的元素都会被放到它应该在的位置。
if (array[j] > array[j 1]) {：比较当前元素array[j]和下一个元素array[j 1]。
int temp = array[j];：如果当前元素大于下一个元素，准备交换它们，首先保存当前元素的值到临时变量temp。
array[j] = array[j 1];：将下一个元素的值赋给当前元素。
array[j 1] = temp;：将临时变量temp的值（原当前元素的值）赋给下一个元素，完成交换。
swapped = true;：设置swapped标志为true，表示发生了交换。
if (!swapped) break;：如果在一次完整的内层循环中没有发生任何交换，那么数组已经排序完成，可以提前退出循环。

这种优化可以提高冒泡排序在部分或完全有序的数组上的性能。然而，即使有这种优化，冒泡排序在最坏情况下的时间复杂度仍然是O(n^2)，其中n是数组的长度。冒泡排序是稳定的排序算法，因为它不会改变相同元素之间的顺序。

选择排序

选择排序通过在未排序的元素中找到最小（或最大）元素，然后将其放置在已排序序列的末尾。

代码语言：java复制

void selectionSort(int[] array) {
    for (int i = 0; i < array.length - 1; i  ) {
        int minIndex = i;
        for (int j = i   1; j < array.length; j  ) {
            if (array[j] < array[minIndex]) {
                minIndex = j;
            }
        }
        // Swap elements
        int temp = array[i];
        array[i] = array[minIndex];
        array[minIndex] = temp;
    }
}

针对如上示例代码，这里我给大家详细的代码剖析下，以便于帮助大家理解的更为透彻，帮助大家早日掌握。

这段Java代码实现了选择排序算法。选择排序通过在未排序的部分找到最小（或最大）的元素，然后将其与已排序序列的最后一个元素交换位置。以下是对代码的逐行解释：

void selectionSort(int[] array) {：定义了一个名为selectionSort的方法，它接受一个整型数组array作为参数。
for (int i = 0; i < array.length - 1; i ) {：外层循环，从索引0开始，直到数组的倒数第二个元素。循环变量i表示已排序部分的最后一个元素的索引。
int minIndex = i;：初始化minIndex为当前循环的起始索引i，这是假设当前位置的元素就是未排序部分的最小值。
for (int j = i 1; j < array.length; j ) {：内层循环，从i 1开始遍历未排序的部分。
if (array[j] < array[minIndex]) {：比较当前遍历到的元素array[j]和当前记录的最小元素array[minIndex]。
minIndex = j;：如果找到更小的元素，则更新minIndex为当前元素的索引。
int temp = array[i];：在内层循环结束后，如果minIndex发生了变化，说明找到了一个新的最小值。在交换前，先保存当前i位置的元素值。
array[i] = array[minIndex];：将找到的最小元素值放到已排序序列的末尾，即i位置。
array[minIndex] = temp;：将原来i位置的元素放到minIndex位置，完成交换。

选择排序是一种简单的排序算法，但它不是稳定的排序算法，因为它可能会改变相同元素的顺序。选择排序的时间复杂度在最坏和平均情况下都是O(n^2)，其中n是数组的长度。尽管选择排序在理论上不如其他O(n log n)的排序算法，它的实现简单，在数据集较小或部分有序的情况下仍然表现良好。

插入排序

插入排序通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

代码语言：java复制

void insertionSort(int[] array) {
    for (int i = 1; i < array.length; i  ) {
        int key = array[i];
        int j = i - 1;
        while (j >= 0 && array[j] > key) {
            array[j   1] = array[j];
            j--;
        }
        array[j   1] = key;
    }
}

针对如上示例代码，这里我给大家详细的代码剖析下，以便于帮助大家理解的更为透彻，帮助大家早日掌握。

这段Java代码实现了插入排序算法。插入排序是一种简单直观的排序算法，它通过构建有序序列，对未排序的数据在已排序的序列中从后向前扫描，找到相应位置并插入。以下是对代码的逐行解释：

void insertionSort(int[] array) {：定义了一个名为insertionSort的方法，它接受一个整型数组array作为参数。
for (int i = 1; i < array.length; i ) {：外层循环从数组的第二个元素开始（索引1），直到数组的最后一个元素。第一个元素（索引0）默认认为是已排序的。
int key = array[i];：将当前遍历到的元素array[i]保存到变量key中，这个元素将被插入到已排序的部分。
int j = i - 1;：初始化j为当前元素的前一个元素的索引，这是开始比较的起始点。
while (j >= 0 && array[j] > key) {：使用while循环从后向前扫描已排序的序列，如果找到第一个小于或等于key的元素，则退出循环。
array[j 1] = array[j];：将当前元素array[j]向后移动一个位置，为key腾出插入空间。
j--;：将索引j向前移动，继续比较前一个元素。
array[j 1] = key;：在找到key应该插入的位置后，将其插入到正确的位置。

插入排序是一种稳定的排序算法，因为它不会改变相同元素之间的顺序。它的平均和最坏情况时间复杂度都是O(n^2)，其中n是数组的长度。然而，对于小规模数据或基本有序的数据，插入排序可以表现得非常高效。

插入排序的一个优势是它不需要额外的存储空间（除了变量key和j之外），这使得它是一个就地排序算法。此外，插入排序在排序过程中可以逐步产生部分排序的数组，这在某些应用场景中非常有用。

归并排序

归并排序采用分治法，将数组分为两部分，分别对它们进行排序，然后合并结果。

代码语言：java复制

void mergeSort(int[] array) {
    if (array.length < 2) return;

    int[] left = Arrays.copyOfRange(array, 0, array.length / 2);
    int[] right = Arrays.copyOfRange(array, array.length / 2, array.length);
    mergeSort(left);
    mergeSort(right);

    merge(array, left, right);
}

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  ];
    }
}

针对如上示例代码，这里我给大家详细的代码剖析下，以便于帮助大家理解的更为透彻，帮助大家早日掌握。

这段Java代码实现了归并排序算法，它是一种分治算法，通过递归地将数组分成更小的部分，然后合并这些部分以生成有序数组。以下是对代码的逐行解释：

void mergeSort(int[] array) {：定义了一个名为mergeSort的方法，它接受一个整型数组array作为参数。
if (array.length < 2) return;：如果数组长度小于2，即数组为空或只有一个元素，则不需要排序，直接返回。
int[] left = Arrays.copyOfRange(array, 0, array.length / 2);：将原数组从开始到中间的部分复制到left数组。
int[] right = Arrays.copyOfRange(array, array.length / 2, array.length);：将原数组从中间到结束的部分复制到right数组。
mergeSort(left);：递归调用mergeSort方法对left数组进行排序。
mergeSort(right);：递归调用mergeSort方法对right数组进行排序。
merge(array, left, right);：调用merge方法将排序后的left和right数组合并回原数组array。
void merge(int[] array, int[] left, int[] right) {：定义了merge方法，它将两个已排序的数组left和right合并到原数组array中。
int i = 0, j = 0, k = 0;：初始化三个索引变量i，j和k。i和j分别用于遍历left和right数组，k用于遍历结果数组array。
while (i < left.length && j < right.length) { ... }：当left和right数组中都有元素时，比较left[i]和right[j]的值，将较小的元素复制到结果数组array中，并相应地递增索引。
if (left[i] < right[j]) { ... } else { ... }：根据比较结果，复制较小的元素到结果数组，并递增相应的索引。
while (i < left.length) { ... }：当left数组中还有剩余元素时，将它们复制到结果数组中。
while (j < right.length) { ... }：当right数组中还有剩余元素时，将它们复制到结果数组中。

归并排序是一种稳定的排序算法，它不会改变相同元素之间的顺序。它的平均和最坏情况时间复杂度都是O(n log n)，其中n是数组的长度。归并排序需要O(n)的额外空间来存储递归调用中创建的临时数组，这使得它在空间复杂度上不如一些就地排序算法高效。然而，归并排序的高效率和稳定性使其在处理大量数据时非常有用。

快速排序

快速排序采用分治法，通过一个划分操作选择一个“基准”元素，将数组分为两个子数组。

代码语言：java复制

void quickSort(int[] array, int begin, int end) {
    if (begin < end) {
        int partitionIndex = partition(array, begin, end);

        quickSort(array, begin, partitionIndex - 1);
        quickSort(array, partitionIndex   1, end);
    }
}

int partition(int[] array, int begin, int end) {
    int pivot = array[end];
    int i = (begin - 1);

    for (int j = begin; j < end; j  ) {
        if (array[j] <= pivot) {
            i  ;
            // Swap elements
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }
    // Swap elements
    int temp = array[i   1];
    array[i   1] = array[end];
    array[end] = temp;

    return i   1;
}

针对如上示例代码，这里我给大家详细的代码剖析下，以便于帮助大家理解的更为透彻，帮助大家早日掌握。

这段Java代码实现了快速排序算法，它是一种高效的分治算法，通过选择一个“基准”元素并将数组分为两部分，一部分包含比基准小的元素，另一部分包含比基准大的元素。然后递归地在这两部分上重复这个过程。以下是对代码的逐行解释：

void quickSort(int[] array, int begin, int end) {：定义了一个名为quickSort的方法，它接受一个整型数组array以及两个整数begin和end作为参数，表示要排序的数组部分的起始和结束索引。
if (begin < end) {：如果起始索引小于结束索引，说明有多个元素需要排序。
int partitionIndex = partition(array, begin, end);：调用partition方法获取基准元素的索引，这是分区操作的一部分。
quickSort(array, begin, partitionIndex - 1);：递归地对基准元素左边的部分进行快速排序。
quickSort(array, partitionIndex 1, end);：递归地对基准元素右边的部分进行快速排序。
}：quickSort方法的结束括号。
int partition(int[] array, int begin, int end) {：定义了partition方法，它负责执行分区操作并返回基准元素的最终索引。
int pivot = array[end];：选择基准元素为结束索引end处的元素。
int i = (begin - 1);：初始化索引i为begin - 1，i将用于跟踪比基准小的元素的最后一个位置。
for (int j = begin; j < end; j ) { ... }：遍历从begin到end - 1的元素。
if (array[j] <= pivot) { ... }：如果当前元素小于或等于基准元素，执行交换操作。
int temp = array[i];：将i位置的元素保存到临时变量temp。
array[i] = array[j];：将当前元素array[j]复制到i位置。
array[j] = temp;：将临时变量temp的值复制到j位置，完成交换。
i ;：由于进行了交换，递增i以指向新的比基准小的元素的最后一个位置。
int temp = array[i 1];：在循环结束后，将基准元素array[end]与i 1位置的元素交换。
array[i 1] = array[end];：将基准元素移动到它的最终位置。
array[end] = temp;：将i 1位置的元素复制到end位置。
return i 1;：返回基准元素的最终索引。