十大排序算法
整合一些算法和动图
冒泡排序
冒泡排序（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 - 1 - i; j++) {
// 比较相邻元素，如果顺序错误则交换
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// 如果没有进行交换，说明已经排好序，提前退出循环
if (!swapped) {
break;
}
}
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(arr);
System.out.println("排序后的数组:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
选择排序
它的基本思想是每次从待排序的序列中选择最小（或最大）的元素，将其放在序列的起始位置，依次进行，直到所有元素都被排序完成。javajavajavajavajava
选择排序
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;
}
}
// 交换找到的最小值与当前元素
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
public static void main(String[] args) {
int[] arr = {64, 25, 12, 22, 11};
selectionSort(arr);
System.out.println("排序后的数组:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
插入排序
将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
img
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;
// 向前查找比当前元素大的元素，依次向后移动
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
// 找到合适的位置插入
arr[j + 1] = key;
}
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6};
insertionSort(arr);
System.out.println("排序后的数组:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
快速排序
快速排序（QuickSort）是由东尼·霍尔（Tony Hoare）发展的一种高效排序算法。平均情况下，排序 n 个元素需要 Ο(nlogn) 次比较，而在最坏情况下，可能需要 Ο(n²) 次比较，但这种情况很少发生。事实上，快速排序通常比其他 Ο(nlogn) 算法更快，因为其内部循环可以在大多数硬件架构上高效实现。
快速排序通过分治法（Divide and Conquer）将一个序列（list）分为两个子序列（sub-lists）来进行排序。作为分治思想在排序算法中的经典应用，快速排序本质上是在冒泡排序基础上的递归分治法的扩展。
快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。
在这里插入图片描述
public class QuickSort {
// 主方法，用于测试
public static void main(String[] args) {
int[] array = {34, 7, 23, 32, 5, 62, 32, 7, 9};
quickSort(array, 0, array.length - 1);
System.out.println("排序后的数组：");
for (int num : array) {
System.out.print(num + " ");
}
}
// 快速排序的主方法
public static void quickSort(int[] array, int low, int high) {
if (low < high) {
int pivotIndex = partition(array, low, high);
quickSort(array, low, pivotIndex - 1); // 排序左半部分
quickSort(array, pivotIndex + 1, high); // 排序右半部分
}
}
// 分区方法，选择一个基准点并进行分区
private static int partition(int[] array, int low, int high) {
int pivot = array[high]; // 选择最右边的元素作为基准点
int i = low - 1; // i 是小于基准点的区域的索引
for (int j = low; j < high; j++) {
if (array[j] < pivot) {
i++;
swap(array, i, j); // 交换小于基准点的元素到左边
}
}
swap(array, i + 1, high); // 将基准点放到正确的位置
return i + 1; // 返回基准点的位置
}
// 交换数组中的两个元素
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
希尔排序
希尔排序（Shell Sort），又称递减增量排序算法，是插入排序的一种高效改进版本，但它不是稳定排序算法。
希尔排序的改进主要基于插入排序的两个关键特性：
- 插入排序对基本有序数据效率高：当数据几乎已经排好序时，插入排序的效率可以接近线性。
- 插入排序的局限性：插入排序每次只能移动一个元素，这使得它在处理大规模无序数据时效率较低。
希尔排序的基本思想是：
- 分组排序：首先将待排序的序列分割成若干个较小的子序列，并对这些子序列进行插入排序。子序列的分组是通过递减的增量（gap）来完成的。初始时，增量较大，随着排序的进行，增量逐渐减小。
- 最终排序：当增量减小到1时，整个序列的记录已经“基本有序”，此时对全体记录进行一次插入排序即可完成排序。
希尔排序的关键在于选择合理的增量序列。不同的增量序列对排序的效率有很大的影响，常见的增量序列包括初期的增量为 n/2，后续的增量逐渐减少到 1。
图片来源于网络
public class ShellSort {
// 主方法，用于测试
public static void main(String[] args) {
int[] array = {34, 7, 23, 32, 5, 62, 32, 7, 9};
shellSort(array);
System.out.println("排序后的数组：");
for (int num : array) {
System.out.print(num + " ");
}
}
// 希尔排序方法
public static void shellSort(int[] array) {
int n = array.length;
// 初始增量设置为数组长度的一半
for (int gap = n / 2; gap > 0; gap /= 2) {
// 对每个增量值进行插入排序
for (int i = gap; i < n; i++) {
int temp = array[i];
int j = i;
// 对当前元素进行插入排序
while (j >= gap && array[j - gap] > temp) {
array[j] = array[j - gap];
j -= gap;
}
array[j] = temp;
}
}
}
}
归并排序
归并排序（Merge Sort）是一种基于分治法的有效排序算法。它的基本思想是将待排序的序列递归地分割成两个子序列，直到每个子序列仅包含一个元素，然后将这些子序列逐步合并成一个有序序列。归并排序可以分为自上而下的递归实现和自下而上的迭代实现两种方法。
请添加图片描述
public class MergeSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
// 对 arr 进行拷贝，不改变参数内容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
if (arr.length < 2) {
return arr;
}
int middle = (int) Math.floor(arr.length / 2);
int[] left = Arrays.copyOfRange(arr, 0, middle);
int[] right = Arrays.copyOfRange(arr, middle, arr.length);
return merge(sort(left), sort(right));
}
protected int[] merge(int[] left, int[] right) {
int[] result = new int[left.length + right.length];
int i = 0;
while (left.length > 0 && right.length > 0) {
if (left[0] <= right[0]) {
result[i++] = left[0];
left = Arrays.copyOfRange(left, 1, left.length);
} else {
result[i++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}
}
while (left.length > 0) {
result[i++] = left[0];
left = Arrays.copyOfRange(left, 1, left.length);
}
while (right.length > 0) {
result[i++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}
return result;
}
}堆排序
堆排序（Heap Sort）是一种基于堆数据结构的有效排序算法。它利用堆的特性来实现排序，通常使用最大堆或最小堆来完成。堆排序的基本思想是将待排序的序列转换为一个堆，然后逐步从堆中提取最大或最小值，并调整堆的结构，从而实现排序。
堆排序的基本步骤：
- 构建堆：将待排序的数组构建成一个最大堆（或最小堆）。在最大堆中，每个父节点的值都不小于其子节点的值。在最小堆中，每个父节点的值都不大于其子节点的值。
排序：
- 从堆中提取根节点（最大值或最小值），将其与堆的最后一个元素交换。
- 重新调整堆，使其重新满足堆的性质。
- 重复以上步骤，直到堆为空。
img
public class HeapSort {
// 主方法，用于测试
public static void main(String[] args) {
int[] array = {34, 7, 23, 32, 5, 62, 32, 7, 9};
heapSort(array);
System.out.println("排序后的数组：");
for (int num : array) {
System.out.print(num + " ");
}
}
// 堆排序方法
public static void heapSort(int[] array) {
int n = array.length;
// 构建最大堆
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(array, n, i);
}
// 从堆中提取元素
for (int i = n - 1; i > 0; i--) {
// 将根节点（最大值）交换到数组末尾
swap(array, 0, i);
// 重新调整堆
heapify(array, i, 0);
}
}
// 调整堆的方法，使以 i 为根的子树满足最大堆性质
private static void heapify(int[] array, int n, int i) {
int largest = i; // 初始化最大值为根节点
int left = 2 * i + 1; // 左子节点
int right = 2 * i + 2; // 右子节点
// 如果左子节点更大
if (left < n && array[left] > array[largest]) {
largest = left;
}
// 如果右子节点更大
if (right < n && array[right] > array[largest]) {
largest = right;
}
// 如果最大值不是根节点
if (largest != i) {
swap(array, i, largest);
// 递归调整子树
heapify(array, n, largest);
}
}
// 交换数组中的两个元素
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
计数排序
计数排序是一种线性时间复杂度的排序算法，适用于整数范围有限的场景。它的基本思想是通过统计每个元素出现的次数来确定元素的位置，从而完成排序。以下是计数排序的基本步骤：
- 确定范围：首先确定待排序元素的最大值和最小值。这个范围将决定需要创建的计数数组的大小。
- 创建计数数组：根据元素的范围创建一个计数数组。数组的索引表示待排序元素的值，数组的值表示该值出现的次数。
- 统计元素出现次数：遍历原始数据，将每个元素对应的计数数组位置的值加一。
- 计算累积计数：对计数数组进行累积求和，以确定每个元素的最终位置。
- 生成排序结果：根据累积计数数组中的信息，将元素放入正确的位置，生成排序后的数组。
img
import java.util.Arrays;
public class CountingSort {
public static void countingSort(int[] array) {
if (array == null || array.length == 0) {
return;
}
// 找到数组中的最大值
int max = Arrays.stream(array).max().orElse(Integer.MAX_VALUE);
// 创建计数数组并初始化
int[] count = new int[max + 1];
// 统计每个元素出现的次数
for (int num : array) {
count[num]++;
}
// 将计数数组转换为累积计数数组
for (int i = 1; i < count.length; i++) {
count[i] += count[i - 1];
}
// 根据累积计数数组生成排序后的结果
int[] sortedArray = new int[array.length];
for (int i = array.length - 1; i >= 0; i--) {
sortedArray[count[array[i]] - 1] = array[i];
count[array[i]]--;
}
// 将排序结果复制回原数组
System.arraycopy(sortedArray, 0, array, 0, array.length);
}
public static void main(String[] args) {
int[] array = {4, 2, 2, 8, 3, 3, 1};
System.out.println("原数组: " + Arrays.toString(array));
countingSort(array);
System.out.println("排序后: " + Arrays.toString(array));
}
}
桶排序
桶排序（Bucket Sort）是一种基于分布的排序算法，特别适用于输入数据分布均匀的情况。它将元素分到多个桶中，再对每个桶内的元素进行单独排序，最后将所有桶内的元素按顺序合并，从而完成排序。
桶排序的基本步骤
- 创建桶：根据输入数据的范围和分布情况，创建一定数量的桶。每个桶代表一个区间。
- 分配元素到桶：遍历输入数组，将每个元素根据其值放入相应的桶中。
- 对每个桶内的元素进行排序：选择合适的排序算法（如插入排序或快速排序）对每个桶内的元素进行排序。
- 合并所有桶的排序结果：将每个桶中的元素按顺序拼接起来，形成最终的有序数组。
f9c64c9a4005888a34d6924613556902.gif
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class BucketSort {
public static void bucketSort(float[] array) {
if (array == null || array.length == 0) {
return;
}
// 创建桶
int numberOfBuckets = array.length;
List<Float>[] buckets = new ArrayList[numberOfBuckets];
for (int i = 0; i < numberOfBuckets; i++) {
buckets[i] = new ArrayList<>();
}
// 将元素分配到桶中
for (float num : array) {
int bucketIndex = (int) (num * numberOfBuckets); // 确定桶的位置
buckets[bucketIndex].add(num);
}
// 对每个桶内的元素进行排序
for (List<Float> bucket : buckets) {
Collections.sort(bucket);
}
// 合并所有桶的排序结果
int index = 0;
for (List<Float> bucket : buckets) {
for (float num : bucket) {
array[index++] = num;
}
}
}
public static void main(String[] args) {
float[] array = {0.42f, 0.32f, 0.73f, 0.25f, 0.67f, 0.48f, 0.12f, 0.89f, 0.94f, 0.36f};
System.out.println("原数组: ");
for (float num : array) {
System.out.print(num + " ");
}
System.out.println();
bucketSort(array);
System.out.println("排序后: ");
for (float num : array) {
System.out.print(num + " ");
}
}
}
基数排序
基数排序（Radix Sort）是一种非比较的整数排序算法，适用于对整数或特定长度的字符串进行排序。基数排序按位或按数字的位数进行排序，从最低有效位（LSD，Least Significant Digit）到最高有效位（MSD，Most Significant Digit）进行多轮排序，最终实现整个数组的有序排列。
基数排序的基本思想
基数排序的核心思想是将待排序的数字按位（从低到高或从高到低）进行排序。由于基数排序依赖于对每一位的排序，通常会借助于稳定的排序算法（如计数排序或桶排序）来保证在每一轮排序后，相同位数的元素保持其相对顺序。
基数排序的步骤
- 确定最大值的位数：找到数组中最大元素的位数，这将决定排序的轮数。
- 从最低位开始排序：从最低位开始，对每一位上的数字进行排序。排序时可以使用稳定的排序算法，比如计数排序。
- 重复：依次对更高的每一位进行排序，直到最高位。
- 最终排序结果：完成所有位的排序后，数组就是有序的。
示例
假设要对整数数组 [170, 45, 75, 90, 802, 24, 2, 66] 进行基数排序：
- 确定最大值的位数：最大值
802有 3 位，所以排序需要进行 3 轮。 第一轮（按个位排序）：
- 排序结果：
[170, 90, 802, 2, 24, 45, 75, 66]
- 排序结果：
第二轮（按十位排序）：
- 排序结果：
[802, 2, 24, 45, 66, 170, 75, 90]
- 排序结果：
第三轮（按百位排序）：
- 排序结果：
[2, 24, 45, 66, 75, 90, 170, 802]
- 排序结果：
img
import java.util.*;
public class RadixSortWithHashMap {
// 获取数组中最大值，以确定排序的轮数
private static int getMax(int[] array) {
int max = array[0];
for (int num : array) {
if (num > max) {
max = num;
}
}
return max;
}
// 使用 HashMap 实现计数排序
private static void countingSortWithHashMap(int[] array, int exp) {
// HashMap 用于存储每个位的对应列表
Map<Integer, List<Integer>> countMap = new HashMap<>();
// 初始化 HashMap 的键值对（键为 0-9 的数字，值为对应的列表）
for (int i = 0; i < 10; i++) {
countMap.put(i, new ArrayList<>());
}
// 根据每一位的数字，将元素放入对应的 HashMap 列表中
for (int num : array) {
int digit = (num / exp) % 10;
countMap.get(digit).add(num);
}
// 将 HashMap 中的元素按键的顺序（从 0 到 9）重新写回数组
int index = 0;
for (int i = 0; i < 10; i++) {
for (int num : countMap.get(i)) {
array[index++] = num;
}
}
}
// 主基数排序函数
public static void radixSort(int[] array) {
// 找到最大数以确定轮数
int max = getMax(array);
// 从个位开始对每一位进行计数排序
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSortWithHashMap(array, exp);
}
}
public static void main(String[] args) {
int[] array = {170, 45, 75, 90, 802, 24, 2, 66};
System.out.println("原数组: " + Arrays.toString(array));
radixSort(array);
System.out.println("排序后: " + Arrays.toString(array));
}
}