|
Java常用的排序算法有以下几种：
冒泡排序（Bubble Sort）选择排序（Selection Sort）插入排序（Insertion Sort）希尔排序（Shell Sort）归并排序（Merge Sort）快速排序（Quick Sort）堆排序（Heap Sort）计数排序（Counting Sort）桶排序（Bucket Sort）基数排序（Radix Sort）
这些排序算法都有各自的优缺点，应根据具体情况选择适合的算法。
算法复杂度
排序算法时间复杂度（平均）时间复杂度（最坏）时间复杂度（最好）空间复杂度稳定性冒泡排序O(n^2)O(n^2)O(n)O(1)稳定选择排序O(n^2)O(n^2)O(n^2)O(1)不稳定插入排序O(n^2)O(n^2)O(n)O(1)稳定希尔排序O(n log n)O(n^2)O(n)O(1)不稳定归并排序O(n log n)O(n log n)O(n log n)O(n)稳定快速排序O(n log n)O(n^2)O(n log n)O(log n)不稳定堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定计数排序O(n+k)O(n+k)O(n+k)O(k)稳定桶排序O(n^2)O(n^2)O(n)O(n+k)稳定基数排序O(n*k)O(n*k)O(n*k)O(n+k)稳定
其中，n表示输入元素的数量，k表示元素的取值范围大小。
稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。空间复杂度：是指算法在计算机 内执行时所需存储空间的度量，它也是数据规模n的函数。
1. 冒泡排序（Bubble Sort）
冒泡排序是一种简单的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就交换位置。这个过程持续对数列的末尾进行，直到整个数列都排序完成。
import org.junit.jupiter.api.Assertions;
import java.util.Arrays;
public class Bubble {
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i
if (arr[j] > arr[j + 1]) {
// 交换arr[j+1]和arr[j]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
public static void main(String[] args) {
int[] arr = {5, 2, 8, 3, 1, 6};
int[] expectedArr = {1, 2, 3, 5, 6, 8};
Bubble.bubbleSort(arr);
System.out.println("arr = " + Arrays.toString(arr));
Assertions.assertArrayEquals(expectedArr, arr);
}
}
在上面的代码中， bubbleSort 函数接受一个整数数组作为输入，并使用冒泡排序算法对其进行排序。外部循环运行 n - 1 次，其中 n 是数组的长度，内部循环运行 n - i - 1 次，其中 i 是外部循环的当前迭代次数。这是因为在每次外部循环迭代后，最大的元素肯定在数组的末尾，因此我们不需要再次比较它。
在内部循环中，我们比较相邻的元素并交换它们，如果它们的顺序不正确。这样，最大的元素就“冒泡”到数组的末尾。在每次遍历数组后，最大的元素都处于它的最终位置，因此我们可以将内部循环的大小减少1。
冒泡排序的时间复杂度为O(n^2)，这使得它在大型列表和实际应用中效率低下。但是，由于其简单性，它是向初学者教授排序的好算法。
2. 选择排序（Selection Sort）
选择排序是一种简单的排序算法，它的基本思想是每次从待排序的元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的元素排完。
import org.junit.jupiter.api.Assertions;
import java.util.Arrays;
public class Selection {
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i
if (arr[j]
int[] arr = {5, 2, 8, 3, 1, 6};
int[] expectedArr = {1, 2, 3, 5, 6, 8};
Selection.selectionSort(arr);
System.out.println("arr = " + Arrays.toString(arr));
Assertions.assertArrayEquals(expectedArr, arr);
}
}
在上面的代码中， selectionSort 函数接受一个整数数组作为输入，并使用选择排序算法对其进行排序。外部循环运行 n - 1 次，其中 n 是数组的长度。在内部循环中，我们找到未排序部分中的最小元素，并将其索引存储在 minIndex 变量中。然后，我们将最小元素与已排序部分的末尾交换。在每次外部循环迭代后，已排序部分的长度增加1，未排序部分的长度减少1。
选择排序的时间复杂度为O(n^2)，这使得它在大型列表和实际应用中效率低下。但是，由于其简单性，它是向初学者教授排序的好算法。
3. 插入排序（Insertion Sort）
插入排序是一种简单的排序算法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。
import org.junit.jupiter.api.Assertions;
import java.util.Arrays;
public class Insertion {
public static void insertionSort(int[] arr) {
int n = arr.length;
// 外部循环从第二个元素开始，
// 因为我们将第一个元素视为已排序部分
for (int i = 1; i
arr[j + 1] = arr[j];
j--;
}
// 在不小当前值key的位置，插入当前值key
arr[j + 1] = key;
}
}
public static void main(String[] args) {
int[] arr = {5, 2, 8, 3, 1, 6};
int[] expectedArr = {1, 2, 3, 5, 6, 8};
Insertion.insertionSort(arr);
System.out.println("arr = " + Arrays.toString(arr));
Assertions.assertArrayEquals(expectedArr, arr);
}
}
在上面的代码中， insertionSort 函数接受一个整数数组作为输入，并使用插入排序算法对其进行排序。外部循环从第二个元素开始，因为我们将第一个元素视为已排序部分。在内部循环中，我们将要插入的元素与已排序部分的元素进行比较，如果要插入的元素小于已排序部分的元素，则将已排序部分的元素向右移动一位，以便为要插入的元素腾出空间。在内部循环结束后，我们将要插入的元素插入到正确的位置。在每次外部循环迭代后，我们可以确保前i个元素已经被排序。
插入排序的时间复杂度为O(n^2)，这使得它在大型列表和实际应用中效率低下。但是，插入排序的实现非常简单，它在小型列表上的性能非常好。
4. 希尔排序（Shell Sort）
希尔排序是一种改进的插入排序算法，它的基本思想是将待排序的数组按照一定的间隔进行分组，对每组使用插入排序算法进行排序，然后缩小间隔，再对分组进行排序，直到间隔为1为止。
逐渐减小间隔大小的方法有助于提高排序过程的效率，可以减少比较和交换的次数。这是希尔排序算法的一个关键特点。
import org.junit.jupiter.api.Assertions;
import java.util.Arrays;
public class Shell {
public static void shellSort(int[] arr) {
int n = arr.length;
// 初始化间隔（gap）的值，它决定了每次迭代中子数组的大小
// 从数组长度的一半开始作为初始间隔值，gap就是分割的子数组数量
for (int gap = n / 2; gap > 0; gap /= 2) {
// 循环从间隔值开始，遍历数组直到数组的末尾；代表循环所有的子数组
for (int i = gap; i
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
}
}
public static void main(String[] args) {
int[] arr = {5, 2, 8, 3, 1, 6};
int[] expectedArr = {1, 2, 3, 5, 6, 8};
Shell.shellSort(arr);
System.out.println("arr = " + Arrays.toString(arr));
Assertions.assertArrayEquals(expectedArr, arr);
}
}
在上面的代码中， shellSort 函数接受一个整数数组作为输入，并使用希尔排序算法对其进行排序。外部循环使用一个间隔变量 gap ，初始值为数组长度的一半，每次循环将 gap 除以2，直到 gap 为1。内部循环从第 gap 个元素开始，将要插入的元素与已排序部分的元素进行比较，如果要插入的元素小于已排序部分的元素，则将已排序部分的元素向右移动 gap 个位置，以便为要插入的元素腾出空间。在内部循环结束后，我们将要插入的元素插入到正确的位置。在每次外部循环迭代后，我们可以确保数组的前 gap 个元素已经被排序。
希尔排序的时间复杂度为O(n^2)，但实际上它的性能比插入排序要好得多，特别是在大型列表上。希尔排序的性能取决于间隔序列的选择，但是目前还没有一种最优的间隔序列。
5. 归并排序（Merge Sort）
归并排序是一种分治思想的排序算法，它的基本思想是将待排序的数组分成若干个子序列，每个子序列都是有序的，然后再将子序列合并成一个有序的数组。
import org.junit.jupiter.api.Assertions;
import java.util.Arrays;
public class Merge {
public static void main(String[] args) {
int[] arr = {5, 2, 8, 3, 1, 6};
int[] expectedArr = {1, 2, 3, 5, 6, 8};
Merge.mergeSort(arr, 0, arr.length - 1);
System.out.println("arr = " + Arrays.toString(arr));
Assertions.assertArrayEquals(expectedArr, arr);
}
public static void mergeSort(int[] arr, int left, int right) {
if (left
// 子数组 L 的大小
int n1 = mid - left + 1;
// 右子数组 R 的大小
int n2 = right - mid;
// 创建两个临时数组 L 和 R ，分别用来存储左子数组和右子数组的元素
int[] L = new int[n1];
int[] R = new int[n2];
// 使用 for 循环将原始数组 arr 中的元素复制到临时数组 L 和 R 中，分别从 left 和 mid + 1 开始
for (int i = 0; i
R[j] = arr[mid + 1 + j];
}
// 初始化三个变量 i、j和k，分别指向数组 L 、R 和原始数组 arr 的起始位置
int i = 0, j = 0, k = left;
// 使用 while 循环，比较 L 和 R 的元素，并将较小的元素放回原始数组 arr 中
while (i
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// 当 L 或 R 中的元素用完时，将剩余的元素依次放回原始数组 arr 中
while (i
arr[k] = R[j];
j++;
k++;
}
// merge 方法执行完毕后，两个子数组范围内的元素已经按照从小到大的顺序合并到了原始数组 arr 中
}
}
在上面的代码中， mergeSort 函数接受一个整数数组、一个左索引和一个右索引作为输入，并使用归并排序算法对指定范围内的数组元素进行排序。该函数使用递归将数组分成两个子数组，然后对它们进行排序，并最后将它们合并成一个有序数组。 merge 函数用于将两个有序数组合并成一个有序数组。它创建两个临时数组 L 和 R ，将左子数组的元素存储在 L 中，将右子数组的元素存储在 R 中，然后将它们合并成一个有序数组并存储在原始数组中。
归并排序的时间复杂度为O(nlogn)，它的性能比冒泡排序和插入排序要好得多，特别是在大型列表上。
6. 快速排序（Quick Sort）
快速排序是一种分治思想的排序算法，它的基本思想是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后再分别对这两部分记录继续进行排序，以达到整个序列有序的目的。
import org.junit.jupiter.api.Assertions;
import java.util.Arrays;
public class Quick {
public static void main(String[] args) {
int[] arr = {5, 2, 8, 6, 1, 3};
int[] expectedArr = {1, 2, 3, 5, 6, 8};
Quick.quickSort(arr, 0, arr.length - 1);
System.out.println("arr = " + Arrays.toString(arr));
Assertions.assertArrayEquals(expectedArr, arr);
}
// 接收一个数组 arr，一个低索引 low ，和一个高索引 high 作为参数
public static void quickSort(int[] arr, int low, int high) {
// 检查 low 是否小于 high。如果不是，则意味着数组只有一个元素或为空，因此不需要排序
if (low
// 将最后一个元素作为枢轴元素（ arr[high] ）
int pivot = arr[high];
// 将 i 初始化为 low - 1，用于跟踪较小元素的索引
int i = low - 1;
for (int j = low; j
// 如果当前元素 arr[j] 小于枢轴元素，则增加 i 并交换 arr[i] 和 arr[j]
// 较小元素索引+1
i++;
// 将当前元素 arr[j] 放在较小元素索引位置
// 将较小元素放在前面
swap(arr, i, j);
}
// 其他情况，则较小元素索引没有增加，说明当前元素应该放在右边
}
// 将枢轴元素（ arr[high] ）与索引 i + 1 处的元素交换。
// 确保枢轴元素左边是较小元素，右边是较大元素
swap(arr, i + 1, high);
// 将 i + 1 作为枢轴索引返回
return i + 1;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
在上面的代码中， quickSort 函数接受一个整数数组、一个低索引和一个高索引作为输入，并使用快速排序算法对指定范围内的数组元素进行排序。该函数使用递归将数组分成两个子数组，然后对它们进行排序，并最后将它们合并成一个有序数组。 partition 函数用于将数组分成两个子数组。它选择数组中的最后一个元素作为基准元素，然后将小于基准元素的元素放在左边，将大于基准元素的元素放在右边，并返回基准元素的索引。 swap 函数用于交换数组中的两个元素。
快速排序的时间复杂度为O(nlogn)，它的性能比冒泡排序和插入排序要好得多，特别是在大型列表上。
7. 堆排序（Heap Sort）
堆排序是一种树形选择排序算法，它的基本思想是将待排序的数组构建成一个大根堆（或小根堆），然后将堆顶元素与堆底元素交换位置，再将剩余元素重新构建成堆，重复执行交换和重构堆的操作，直到整个数组有序。
堆排序是一种基于堆数据结构的排序算法，它的时间复杂度为O(nlogn)。
堆的概念
集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：Ki
int n = arr.length;
// 构建大根堆，
// 这段代码是构建大根堆的过程，它的循环次数为n/2-1次，是因为在完全二叉树中，叶子节点不需要进行堆化操作，
// 所以只需要对非叶子节点进行堆化，而非叶子节点的数量为n/2-1个。因此，只需要循环n/2-1次即可完成大根堆的构建。
// 非叶子节点在一维数组中就是前面 n/2-1
for (int i = n / 2 - 1; i >= 0; i--) {
// 从最底层的根节点开始堆化，每次执行完成后，都找出最大值，并放在根节点位置
// 逐层往上找，循环结束后，第一个元素肯定是最大值
heapify(arr, n, i);
}
// 依次取出堆顶元素，并将余下元素继续堆化，得到有序序列
for (int i = n - 1; i >= 0; i--) {
// 第一个for循环已经找出最大值，所以先做交货，把最大值换到最后一个位置
// 把最大值交换到最后一个位置，下一次循环最后一个位置就不比较了
swap(arr, 0, i);
// 继续找出最大值，放在第一个位置
heapify(arr, i, 0);
}
}
private static void heapify(int[] arr, int heapSize, int i) {
int largest = i; // 初始化假设最大值为根节点
int left = 2 * i + 1; // 相对于索引i的左节点索引
int right = 2 * i + 2; // 相对于索引i的右节点索引
// 找到左右子节点中的最大值
if (left arr[largest]) {
// 如果有左节点，且左节点大于根节点，则记录左节点为最大值
largest = left;
}
if (right arr[largest]) {
// 如果有右节点，且右节点大于最大值，则记录右节点为最大值
largest = right;
}
// 上面两个if之后，肯定找到最大值
if (largest != i) {
// i 是根节点下标
// 如果最大值不是根节点，则交换根节点与最大值节点，
// 并递归地对最大值节点进行堆化
swap(arr, i, largest);
heapify(arr, heapSize, largest);
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] arr = {5, 2, 8, 3, 12, 35, 57, 1, 6};
int[] expectedArr = {1, 2, 3, 5, 6, 8, 12, 35, 57};
Heap.heapSort(arr);
System.out.println("arr = " + Arrays.toString(arr));
Assertions.assertArrayEquals(expectedArr, arr);
}
}
在上面的代码中， heapSort 函数接受一个整数数组作为输入，并使用堆排序算法对该数组进行排序。该函数首先构建一个大根堆，然后依次取出堆顶元素，得到有序序列。 heapify 函数用于对一个节点进行堆化操作。它接受三个参数：待堆化的数组、数组的大小和要堆化的节点的索引。该函数首先找到左右子节点中的最大值，如果最大值不是根节点，则交换根节点与最大值节点，并递归地对最大值节点进行堆化。 swap 函数用于交换数组中的两个元素。
8. 计数排序（Counting Sort）
计数排序是一种非比较排序算法，它的基本思想是统计数组中每个元素出现的次数，然后根据元素出现的次数依次将元素放入有序的数组中。
计数排序时间复杂度为O(n+k)，其中k为待排序的元素的最大值。
import org.junit.jupiter.api.Assertions;
import java.util.Arrays;
public class Counting {
public static void countingSort(int[] arr) {
int n = arr.length;
// 取出数组中最大值
int max = getMax(arr);
int[] count = new int[max + 1];
// 统计每个元素出现的次数
for (int i = 0; i
// 因为count包含了每个数据出现的次数，所以从小到大，
// 逐个往前加得到就是原数组中每个元素在有序序列中应有的位置
count[i] += count[i - 1];
}
// 输出有序序列
int[] sortedArr = new int[n];
for (int i = n - 1; i >= 0; i--) {
int item = arr[i];//元素
int itemPos = count[item];// 元素在有序数组中的位置
sortedArr[itemPos - 1] = item; // 将元素填入有序数组
count[item]--;
}
// 将有序序列复制回原数组
System.arraycopy(sortedArr, 0, arr, 0, n);
}
private static int getMax(int[] arr) {
int max = arr[0];
for (int i = 1; i
max = arr[i];
}
}
return max;
}
public static void main(String[] args) {
int[] arr = {5, 2, 6, 8, 3, 1, 6, 5, 12};
int[] expectedArr = {1, 2, 3, 5, 5, 6, 6, 8, 12};
Counting.countingSort(arr);
System.out.println("arr = " + Arrays.toString(arr));
Assertions.assertArrayEquals(expectedArr, arr);
}
}
9. 桶排序（Bucket Sort）
桶排序是一种非比较排序算法，它的基本思想是将待排序的数组分到有限数量的桶里，然后对每个桶进行排序，最后依次将所有桶中的元素取出来，组成有序的数组。
桶排序的时间复杂度为O(n)，其中n为待排序元素的个数。
import org.junit.jupiter.api.Assertions;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class Bucket {
public static void main(String[] args) {
int[] arr = {5, 2, 8, 3, 12, 35, 57, 1, 6};
int[] expectedArr = {1, 2, 3, 5, 6, 8, 12, 35, 57};
Bucket.bucketSort(arr, 20);
System.out.println("arr = " + Arrays.toString(arr));
Assertions.assertArrayEquals(expectedArr, arr);
}
/**
* 桶排序
* @param arr 待排序数组
* @param bucketSize 桶大小，数据不宜过大，桶越大，后续对桶内数据排序越耗时
*/
public static void bucketSort(int[] arr, int bucketSize) {
if (arr.length == 0) {
return;
}
// 循环数组，先找到最小值和最大值
int minValue = arr[0];
int maxValue = arr[0];
for (int i = 1; i
minValue = arr[i];
} else if (arr[i] > maxValue) {
maxValue = arr[i];
}
}
// 根据桶的大小，计算桶个数，并初始化桶
int bucketCount = (maxValue - minValue) / bucketSize + 1;
List buckets = new ArrayList(bucketCount);
for (int i = 0; i
int bucketIndex = (arr[i] - minValue) / bucketSize;
buckets.get(bucketIndex).add(arr[i]);
}
int currentIndex = 0;
for (int i = 0; i
arr[currentIndex++] = bucket.get(j);
}
}
}
}
在上面的代码中， bucketSort 函数接受一个整数数组和桶的大小作为输入，并使用桶排序算法对该数组进行排序。该函数首先找到输入数组中的最小值和最大值，并计算桶的个数。然后，该函数创建一个大小为桶的个数的桶列表，用于存储每个桶中的元素。接下来，该函数依次遍历输入数组，将每个元素放入相应的桶中。然后，该函数对每个桶中的元素进行排序，并将排序后的元素按顺序合并起来得到有序序列。
10. 基数排序（Radix Sort）
基数排序是一种非比较排序算法，它的基本思想是将待排序的数组按照位数（个位、十位、百位）进行划分，然后依次对每个位上的数字进行排序，最终得到有序的数组。
基数排序的时间复杂度为O(d(n+k))，其中d为最大元素的位数，n为待排序元素的个数，k为桶的个数。
public class Radix {
public static void radixSort(int[] arr) {
if (arr.length == 0) {
return;
}
// 循环取得数组中的最大值
int maxNum = arr[0];
for (int i = 1; i
maxNum = arr[i];
}
}
// 根据最大值算出数组中的最大位数，个位、十位、百位、千位等
int maxDigit = 0;
while (maxNum != 0) {
maxNum /= 10;
maxDigit++;
}
// 初始化10个list，分别存放位数是0-9的10组数字
List buckets = new ArrayList(10);
for (int i = 0; i
// 循环数组，将数据分别存入桶中
// 第一次循环，桶里面的个位数顺序排序完成
// 第二次循环，个位、十位都排序完成
// 第三次循环，个位、十位、百位都排序完成
for (int j = 0; j
List bucket = buckets.get(j);
for (int k = 0; k
int[] arr = {5, 2, 8, 3, 12, 35, 57, 1, 6};
int[] expectedArr = {1, 2, 3, 5, 6, 8, 12, 35, 57};
Radix.radixSort(arr);
System.out.println("arr = " + Arrays.toString(arr));
Assertions.assertArrayEquals(expectedArr, arr);
}
}
在上面的代码中， radixSort 函数接受一个整数数组作为输入，并使用基数排序算法对该数组进行排序。该函数首先找到输入数组中的最大值，并计算最大值的位数。然后，该函数创建一个大小为10的桶列表，用于存储每个桶中的元素。接下来，该函数依次遍历输入数组的每一位，将每个元素放入相应的桶中。然后，该函数将每个桶中的元素按顺序合并起来得到有序序列。
参考
https://github.com/byteflying/AlgorithmManRelease
|