Java中5种排序算法教程

排序是 IT 中的基本操作，是有效数据管理的核心。在实践中，即使是稍微大一点的应用程序也很难找到不使用至少一种排序算法的应用程序。
下面您将详细讨论流行的排序算法及其在 Java 中的实现。

1、选择排序
理解和实际应用基本排序算法（包括选择排序！）是每个初级开发人员技能发展的关键要素。尽管专业程序员在日常工作中很少从头开始实现排序算法，但了解它们的工作原理和构造方式至关重要。

选择排序是最简单的排序算法之一。尽管它很简单，但它是有效且适用的，特别是在元素列表较小的情况下。
其工作原理如下：

1. 它会遍历整个项目列表。
2. 查找具有最小值的元素。
3. 将此元素与列表中的第一个元素交换。
4. 它重复此过程，现在选择剩余元素中具有最低值的元素。
5. 它会继续这样的替换，直到整个列表排序完毕。

public static 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;
    }
}

最流行的排序算法之一是选择排序。
为什么值得感兴趣？

• 简单性——选择排序是最简单的排序算法之一，易于理解和实现。
• 没有额外的内存——它是一种就地算法，这意味着它不需要额外的内存来存储正在排序的项目。
• 对于小型集合有效- 对于小型项目列表，选择排序非常有效且高效。

• 时间复杂度– 它的时间复杂度为 O(n^2)，这使得它对于大型项目列表效率低下。
• 不稳定——算法不稳定，这意味着不能保证具有相同值的元素保持原始顺序。

选择排序是一种简单而有效的排序算法，在许多情况下都很有用。尽管它有其局限性，特别是对于大型列表，但值得了解它的工作原理并在代码中实现它。

2、归并排序
合并排序——这是基于“分而治之”概念的有效排序算法之一。该算法因其高效、稳定而在实际中得到广泛应用。

“分而治之”的概念是一种算法策略，涉及将复杂问题划分为更小、更易于管理的部分。子问题独立解决，然后我们将结果组合起来以获得父问题的解决方案。

归并排序——作用机制

1. 划分——第一步，将数组分为两个相等的部分，即左部分和右部分。数组的中间索引计算公式为 (left + right) / 2，其中“left”是数组开头的索引，“right”是数组末尾的索引。
2. 排序（征服）—— 然后对数组的两个部分（即左部分和右部分）进行递归排序，直到只剩下单个元素。这种排序是递归执行的。
3. 合并：对各个元素进行排序后，将它们合并为一个已排序的数组。此步骤比较左侧和右侧的元素，并将它们按适当的顺序放置在结果数组中。

归并排序算法是稳定的，这意味着它不会因排序而改变相等元素的顺序。它也是一种异地算法，这意味着它会为排序后的数据创建一个新数组，而不会覆盖原始数组。

public static void mergeSort(int[] array) {
    if (array.length <= 1) {
        return;
    }
 
    int middle = array.length / 2;
    int[] left = new int[middle];
    int[] right = new int[array.length - middle];
 
    for (int i = 0; i < middle; i++) {
        left[i] = array[i];
    }
    for (int i = middle; i < array.length; i++) {
        right[i - middle] = array[i];
    }
 
    mergeSort(left);
    mergeSort(right);
 
    merge(array, left, right);
}

该方法采用整数数组作为参数。我们计算数组的中心。我们创建两个数组，

• 左边的数组，我们将元素从数组的开头复制到中间，
• 右边的数组，从中间到末尾复制元素。
• 然后，我们对左右子数组递归调用mergeSort() 。

最后，我们调用merge()方法对元素进行排序并将它们合并到一个新数组中。

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

归并排序是一种在编程和计算机科学的各个领域都有广泛应用的排序算法。其效率和稳定性使其成为数据排序的有吸引力的选择。在实践中，它被用于对象列表的排序、图操作、数据库系统以及许多编程语言和框架的内置排序功能中。这使得理解合并排序对于任何开发人员来说都是宝贵的资产。

3、快速排序
快速排序使用一个简单但强大的概念。该算法将数据集划分为更小的子集，对每个子集进行排序，并将结果组合成一个结构化的整体。但请注意，快速排序并不是一种稳定的排序算法。这意味着具有相同值的元素可以改变它们在结果集中的相对顺序

快速排序——操作原理
“分而治之”的思想就是将一个问题分成更小的子问题，解决它们，并将结果组合成整体问题的解决方案。在快速排序的情况下，这意味着选择一个项目作为“枢轴”，将数据集分成两组（比“枢轴”更小和更大），对两组进行排序，并将它们组合成一个有序列表。

快速排序算法
下面显示的算法对数组中提供的整数进行排序。

快速排序算法
下面显示的算法对数组中提供的整数进行排序。

static void quickSort(int[] arr) {
    if (arr == null || arr.length == 0) {
        return;
    }
 
    int high = arr.length - 1;
    quickSort(arr, 0, high);
}
 
static void quickSort(int[] arr, int begin, int end) {
    if (begin < end) {
        int pivotIndex = partition(arr, begin, end);
 
        quickSort(arr, begin, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, end);
    }
}
 
static int partition(int[] arr, int begin, int end) {
    int pivot = arr[end];
    int i = (begin - 1);
 
    for (int j = begin; j < end; j++) {
        if (arr[j] <= pivot) {
            i++;
 
            int swapTemp = arr[i];
            arr[i] = arr[j];
            arr[j] = swapTemp;
        }
    }
 
    int swapTemp = arr[i + 1];
    arr[i + 1] = arr[end];
    arr[end] = swapTemp;
 
    return i + 1;
}

1. QuickSort()方法是用户的入口点。检查传递的数组不为空或长度为零，然后使用附加参数调用同一方法的版本。
2. 该方法实现了递归快速排序算法。
3. begin < end条件意味着我们正在排序的子数组包含多个元素。
4. 我们调用partition()方法来获取主元索引(pivotIndex)，然后递归地对两个子数组进行排序：从begin到pivotIndex -1和从pivotIndex + 1到end。
5. partition()方法确定给定子数组的主元索引 (pivotIndex)。
6. 它使用两个相互移动的指针（i 和 j），如果元素在轴上的位置错误，则交换元

快速排序的优点和缺点
优点：

• 最佳平均时间复杂度： QuickSort的平均时间复杂度为O(n log n)，使其成为解决一般问题的最快排序算法之一。这意味着在大多数情况下，即使对于大型数据集，QuickSort 的运行速度也非常快。
• 良好的缓存利用率： 与其他排序算法（例如合并排序或堆排序）相比， QuickSort显示出更好的 CPU 缓存利用率。这是由于参考局部性，这是将数据划分为更小的子集的结果。
• 可扩展性： QuickSort对于大型数据集具有非常高的可扩展性和效率。它快速排序大量数据的能力使其在数据库和事务处理系统等工业应用中非常有用。
• 枢轴选择的灵活性：能够选择不同的枢轴选择策略（例如第一个元素、最后一个元素、中位数、随机元素），使算法能够适应特定的输入数据要求，从而提高其在各种场景下的性能。
• 适用于分布式数据： QuickSort对于分散（无序）或随机分布的数据特别有效，因为这种情况可以最大限度地降低算法最坏情况性能(O(n^2))的风险。

• 结构化数据问题，即最坏情况 O(n^2) 时间复杂度：在最坏情况下，当输入数据已经排序或几乎排序时（或者在主元选择不当的任何其他情况下），QuickSort 的时间复杂度退化为 O(n^2)。与 O(n log n) 的平均复杂度相比，效率要低得多。快速排序的最佳情况发生在主元将数据分成近似相等的两部分时，这保证了后续排序的效率。然而，对于已经部分或完全排序的数据，选择主元可能会导致划分非常不均匀。例如，如果您通过透视从已排序集合的一端选择一个元素，则分割部分之一可能包含大部分元素，而另一个部分可能包含很少元素或不包含任何元素。这种情况会导致效率低下，因为算法必须对较大的部分进行更多的递归调用，这不是最优的。
• 排序算法不稳定 当应用算法后相同输入元素的顺序可能发生变化时，排序算法被称为“不稳定”。换句话说，如果我们在原始数据集中有两个具有相同键值的元素A和B，并且排序算法改变了它们的相对位置，我们说它是一个不稳定的算法。在对整数进行排序的情况下，这并不重要 - 数字 1 始终是数字 1，无论我们将其写为 11 还是 11 但是，当我们对整数进行排序时，这可能很重要列出客户的姓名，例如，名单上的第一位是来自格但斯克的 Jan Kowalski，另一位是来自华沙的 Jan Kowalski。
• 无法保证一致的性能：由于 QuickSort 的性能取决于输入数据和主元选择，因此很难保证跨应用程序的一致性能。在某些情况下，其他排序算法可能更可预测且更可靠。

幸运的是，在 Java 世界中，由于内置的​​ Array.sort()函数，您通常不必自己实现排序算法。它自动使用快速排序算法，无需手动实现。

快速排序（Quick Sort），简称快速排序，是一种高级排序算法，在很多情况下都是有效且有用的。无论您的进步水平如何，都值得学习和理解该算法，以扩展您对算法和数据排序的知识。

4、插入排序
排序只是根据集合中元素的某些特征对一组数据进行排列。根据您的需要，可以使用多种排序算法对集合中的元素进行排序。

排序算法是一种按照特定顺序（通常是数字顺序或字典顺序）放置列表或数组元素的算法。有许多可用的排序算法，每种算法在性能、简单性和内存使用方面都有其优点和缺点。

插入排序是一种简单的排序算法，它通过重复地将另一个元素插入到已排序元素的正确位置来对数组进行排序。

插入排序是最早的排序算法之一，已经使用了几个世纪。该算法最初用于纸牌游戏，玩家用手对纸牌进行排序，将新纸牌插入手中的适当位置。
最早记录的插入排序参考来自 14 世纪波斯数学家和天文学家Abu Ja'far Muhammad ibn Musa al-Khwarizmi所著的《计算机编程的艺术》一书。
尽管多年来开发了更高效的排序算法，但插入排序仍在某些应用中使用，例如作为更复杂的排序算法（如Timsort和Shell Sort）的一部分。

插入排序——算法：
插入排序算法在迭代时将每个元素插入到正确的位置。在每次迭代中，都会将该元素与先前的元素进行比较，直到找到正确的位置，然后移动左侧的元素以为新元素腾出空间。

现在我们知道什么是插入排序算法，是时候看看并理解该算法的实现了。

public class InsertionSort {
 
    public static void sort(int[] arr) {
        int length = arr.length;
        for (int i = 1; i < length; 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;
        }
    }
}

在上面的代码中，我们通过将每个元素与之前排序的元素进行比较，将其插入到正确的位置。
外层循环从数组的第二个元素（索引 1）开始，一直到数组的末尾。
外循环的当前元素存储在键中。
内部循环 (while) 向后迭代到数组的开头，直到到达数组的开头或找到小于或等于键的元素。
外循环继续进行，直到处理完所有项目。

插入排序——何时使用它
在决定使用插入排序算法之前，让我们检查一下何时真正值得使用该算法：

• 由于其实现和理解简单，因此非常适合开始学习算法。
• 对于小输入大小或几乎排序的数组非常有效。
• 它可以实现为就地排序算法，这意味着它不需要额外的内存来对输入数组进行排序。
• 由于其时间复杂度为 O(n^2)，对于大型列表或数组来说它可能很慢且效率低下，并且通常不在生产代码中使用。
• 对于较大的输入大小或排序性能至关重要的应用程序，建议使用更高级的算法，例如快速排序或合并排序。

该算法经常用于比较复杂的算法中，对于那些开始学习排序算法的人来说是一个很好的学习算法。

5、冒泡排序
冒泡排序涉及重复遍历列表，在此期间我们比较集合中的相邻项目，如果顺序错误则交换它们的位置。这种排序算法因其较小的项目在列表顶部“冒泡”而较大的项目“下沉”在底部的方式而得名。

冒泡排序被认为是最古老的排序算法之一。它由John W. Mauchly和J. Presper Eckert于1949 年首次描述，作为 ENIAC 计算机设计的一部分。 冒泡排序有时被称为“汇排序”。

冒泡排序——什么时候使用它？

• 冒泡排序是最容易理解和实现的排序算法之一。
• 由于其简单性，冒泡排序常用于学习引入算法的概念，或排序算法。
• 当输入集合很小并且几乎已排序时效果很好。在这种情况下，它可能比更复杂的排序算法更快。
• 由于其时间复杂度为 O(n^2)，对于大型列表或数组来说它可能很慢且效率低下，并且通常不在生产代码中使用。
• 对于大型集合，其他更有效的排序算法（例如快速排序、合并排序或堆排序）可能更适合 ，并且在这些情况下通常是首选算法。

public class BubbleSort {
 
    public static void sort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] < arr[j + 1]) {
                    swap(arr, j, j + 1);
                }
            }
        }
    }
 
private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

在上面的代码中，我们循环遍历数组并比较相邻元素。
请注意，我使用了 2 个嵌套的for循环。外循环从第一个元素运行到倒数第二个元素，内循环从数组未排序部分的第一个元素运行到倒数第二个元素。
如果元素的顺序不正确，我们调用swap方法来交换它们的位置。swap
方法采用一个数组和要交换的两个元素的索引，并使用临时变量temp来执行交换。

冒泡排序是一种简单直观的排序算法，其工作原理是重复替换数组中的相邻元素。
由于其简单性，它是一种很好的算法，可以在算法本身和排序算法领域迈出第一步

总结
我们介绍了冒泡排序、插入排序、快速排序等许多方法，每种方法都有独特的功能和效率。对于任何想要探索编程中排序秘密的人来说，这是一本极好的指南。