java常用的7大排序算法汇总

### Java常用的七大排序算法 #### 1. 插入排序算法 插入排序是一种简单直观的排序算法。它的基本思想是：对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。 - **算法步骤**： 1. 将第一待排序的记录看作是一个有序序列，把第二个元素到最后一个元素当成是未排序序列。 2. 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。 3. 重复第二步，直到全部插入完成。 - **时间复杂度**：平均情况和最坏情况均为 O(n^2)，最好情况为 O(n)，当输入数组已经是排序好的情况下。 - **空间复杂度**：O(1)，因为插入排序只需要常量级别的额外空间。 #### 2. 选择排序算法 选择排序是一种简单直观的比较排序算法。其工作原理是每一次从未排序的部分找到最小（或最大）元素，存放到排序序列的起始位置，直到全部排完。 - **算法步骤**： 1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。 2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。 3. 以此类推，直到所有元素均排序完毕。 - **时间复杂度**：平均情况和最坏情况均为 O(n^2)。 - **空间复杂度**：O(1)，是原地排序（in-place）。 #### 3. 冒泡排序算法 冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。 - **算法步骤**： 1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个。 2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。 3. 针对所有的元素重复以上的步骤，除了最后一个。 4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。 - **时间复杂度**：平均情况和最坏情况均为 O(n^2)，最好情况为 O(n)，当输入数组已经是排序好的情况下。 - **空间复杂度**：O(1)，是原地排序。 #### 4. 快速排序算法 快速排序是一种非常高效的排序算法，由C.A.R. Hoare于1960年提出。它的基本思想是：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。 - **算法步骤**： 1. 从数列中挑出一个元素，称为"基准"（pivot）。 2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分割结束之后，该基准就处于数列的中间位置。这个称为分割（partition）操作。 3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。 - **时间复杂度**：平均情况为 O(n log n)，最坏情况为 O(n^2)。 - **空间复杂度**：O(log n)，主要消耗在于递归调用栈的空间占用。 ### 总结 以上介绍了Java中常用的四种排序算法，分别是插入排序、选择排序、冒泡排序和快速排序。这些排序算法各有特点，适用于不同的场景。例如，当数据量较小时，可以选择插入排序或选择排序；当数据量较大时，快速排序通常是更好的选择，因为它具有较好的平均性能。此外，这些算法的实现都非常直观，适合初学者学习排序算法的基础概念。