1. 冒泡排序（Bubble Sort）
冒泡排序重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来，直到整个数列有序。
public class BubbleSort {
public static void bubbleSort(int[] arr) {
int n = arr.length;
// 外层循环控制排序的轮数
for (int i = 0; i < n - 1; i++) {
// 标记是否有元素交换，若没有则提前结束排序
boolean swapped = false;
// 内层循环比较相邻元素并交换
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// 交换 arr[j] 和 arr[j + 1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// 如果没有发生交换，说明数组已经有序，提前退出
if (!swapped) {
break;
}
}
}
}2. 选择排序（Selection Sort）
选择排序每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾，直到全部待排序的数据元素排完。
public class SelectionSort {
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;
}
}
// 交换当前元素和最小值元素
if (minIndex != i) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
}3. 插入排序（Insertion Sort）
插入排序通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
public class InsertionSort {
public static void insertionSort(int[] arr) {
int n = arr.length;
// 从第二个元素开始，将其插入到前面已排序的序列中
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// 将大于 key 的元素后移
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
// 插入 key
arr[j + 1] = key;
}
}
}4. 希尔排序（Shell Sort）
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。
public class ShellSort {
public static void shellSort(int[] arr) {
int n = arr.length;
// 初始增量为数组长度的一半
for (int gap = n / 2; gap > 0; gap /= 2) {
// 对每个分组进行插入排序
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
// 插入元素
arr[j] = temp;
}
}
}
}5. 归并排序（Merge Sort）
归并排序采用分治法，将已有序的子序列合并，得到完全有序的序列。
public class MergeSort {
public static void mergeSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
int[] temp = new int[arr.length];
mergeSort(arr, 0, arr.length - 1, temp);
}
private static void mergeSort(int[] arr, int left, int right, int[] temp) {
if (left < right) {
int mid = left + (right - left) / 2;
// 递归排序左半部分
mergeSort(arr, left, mid, temp);
// 递归排序右半部分
mergeSort(arr, mid + 1, right, temp);
// 合并左右两部分
merge(arr, left, mid, right, temp);
}
}
private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
int i = left;
int j = mid + 1;
int t = 0;
// 比较左右两部分元素，将较小的放入临时数组
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[t++] = arr[i++];
} else {
temp[t++] = arr[j++];
}
}
// 将左半部分剩余元素放入临时数组
while (i <= mid) {
temp[t++] = arr[i++];
}
// 将右半部分剩余元素放入临时数组
while (j <= right) {
temp[t++] = arr[j++];
}
t = 0;
// 将临时数组元素复制回原数组
while (left <= right) {
arr[left++] = temp[t++];
}
}
}6. 快速排序（Quick Sort）
快速排序使用分治法，通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后分别对这两部分记录继续进行排序。
public class QuickSort {
public static void quickSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
quickSort(arr, 0, arr.length - 1);
}
private static void quickSort(int[] arr, int left, int right) {
if (left < right) {
int partitionIndex = partition(arr, left, right);
// 递归排序左半部分
quickSort(arr, left, partitionIndex - 1);
// 递归排序右半部分
quickSort(arr, partitionIndex + 1, right);
}
}
private static int partition(int[] arr, int left, int right) {
int pivot = arr[right];
int i = left - 1;
// 将小于 pivot 的元素交换到左边
for (int j = left; j < right; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 将 pivot 放到正确位置
int temp = arr[i + 1];
arr[i + 1] = arr[right];
arr[right] = temp;
return i + 1;
}
}7. 堆排序（Heap Sort）
堆排序利用堆这种数据结构，将数组构建成最大堆，然后依次将堆顶元素与最后一个元素交换，并调整堆，直到整个数组有序。
public class HeapSort {
public static void heapSort(int[] arr) {
int n = arr.length;
// 构建最大堆
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 一个个交换元素
for (int i = n - 1; i > 0; i--) {
// 将堆顶元素与当前未排序部分的最后一个元素交换
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// 调整堆
heapify(arr, i, 0);
}
}
private static void heapify(int[] arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
// 找到左子节点、右子节点和根节点中的最大值
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
// 如果最大值不是根节点，则交换并继续调整
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, n, largest);
}
}
}8. 计数排序（Counting Sort）
计数排序是一种非比较排序算法，它的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。
public class CountingSort {
public static void countingSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
int max = arr[0];
int min = arr[0];
// 找出数组中的最大值和最小值
for (int num : arr) {
if (num > max) {
max = num;
}
if (num < min) {
min = num;
}
}
int range = max - min + 1;
int[] count = new int[range];
// 统计每个元素出现的次数
for (int num : arr) {
count[num - min]++;
}
int index = 0;
// 将统计结果放回原数组
for (int i = 0; i < range; i++) {
while (count[i] > 0) {
arr[index++] = i + min;
count[i]--;
}
}
}
}9. 桶排序（Bucket Sort）
桶排序将数组分到有限数量的桶子里，每个桶子再个别排序，最后将所有桶中的元素合并。
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class BucketSort {
public static void bucketSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
int min = arr[0];
int max = arr[0];
// 找出数组中的最大值和最小值
for (int num : arr) {
if (num < min) {
min = num;
}
if (num > max) {
max = num;
}
}
int bucketCount = (max - min) / arr.length + 1;
List<List<Integer>> buckets = new ArrayList<>();
// 初始化桶
for (int i = 0; i < bucketCount; i++) {
buckets.add(new ArrayList<>());
}
// 将元素放入对应的桶中
for (int num : arr) {
int bucketIndex = (num - min) / arr.length;
buckets.get(bucketIndex).add(num);
}
int index = 0;
// 对每个桶进行排序并合并结果
for (List<Integer> bucket : buckets) {
Collections.sort(bucket);
for (int num : bucket) {
arr[index++] = num;
}
}
}
}10. 基数排序（Radix Sort）
排序是一种非比较型整数排序算法，它按每个位数分别比较，将整数按位数切割成不同的数字，然后进行排序。
public class RadixSort {
public static void radixSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
int max = arr[0];
// 找出数组中的最大值
for (int num : arr) {
if (num > max) {
max = num;
}
}
// 对每一位进行计数排序
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSortForRadix(arr, exp);
}
}
private static void countingSortForRadix(int[] arr, int exp) {
int n = arr.length;
int[] output = new int[n];
int[] count = new int[10];
// 统计每个位上数字的出现次数
for (int i = 0; i < n; i++) {
count[(arr[i] / exp) % 10]++;
}
// 计算累积次数
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
// 从后往前将元素放入输出数组
for (int i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
// 将输出数组复制回原数组
for (int i = 0; i < n; i++) {
arr[i] = output[i];
}
}
}