Java 数据结构篇——深入了解排序算法（动态图 + 实现七种基本排序算法）
·
排序算法是数据结构和算法中的基础内容之一。在实际编程中，排序算法用于对数据进行排列，以便高效地查找、存储、比较等。常见的排序算法有很多种，每种算法都有其特定的优缺点，并且适用于不同的场景。
在本篇文章中，我们将详细介绍七种经典的排序算法，并通过 Java 代码实现它们。为了帮助大家更好地理解排序的过程，我们还将提供动态图示例来演示这些排序算法是如何一步步进行的。
1. 排序算法概述
排序算法可以分为以下几类：
-
比较排序：通过比较元素之间的大小来确定元素的顺序。
- 冒泡排序
- 选择排序
- 插入排序
- 快速排序
- 归并排序
- 希尔排序
-
非比较排序：不通过直接比较元素来排序。
- 计数排序
- 基数排序
- 桶排序
本文将重点介绍七种常见的比较排序算法：冒泡排序、选择排序、插入排序、快速排序、归并排序、希尔排序和堆排序。
2. 冒泡排序 (Bubble Sort)
冒泡排序是一种简单的排序算法，其基本思想是通过多次遍历待排序的数组，每次比较相邻元素的大小，如果它们的顺序错误就交换它们的位置。每一轮遍历后，最大的元素会被“冒泡”到数组的末端。
2.1 冒泡排序实现
public class BubbleSort {
public static void bubbleSort(int[] arr) {
int n = arr.length;
boolean swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - i - 1; 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 printArray(int[] arr) {
for (int i : arr) {
System.out.print(i + " ");
}
System.out.println();
}
public static void main(String[] args) {
int[] arr = {64, 25, 12, 22, 11};
System.out.println("Unsorted array:");
printArray(arr);
bubbleSort(arr);
System.out.println("Sorted array:");
printArray(arr);
}
}
2.2 复杂度分析
- 时间复杂度：最坏和平均情况为 (O(n^2))，最好情况（数组已经有序）为 (O(n))。
- 空间复杂度：(O(1))，是原地排序算法。
2.3 动态演示
冒泡排序每次将当前最大的元素交换到末尾。可以通过图示来表示这个过程：每一轮，未排序部分逐步减少，最大元素不断被“冒泡”到末尾。
3. 选择排序 (Selection Sort)
选择排序是一种简单的排序算法，基本思想是：每一轮遍历未排序部分，找到最小的元素，并将其放到已排序部分的末尾。
3.1 选择排序实现
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;
}
}
// 交换最小元素和第i个元素
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
public static void printArray(int[] arr) {
for (int i : arr) {
System.out.print(i + " ");
}
System.out.println();
}
public static void main(String[] args) {
int[] arr = {64, 25, 12, 22, 11};
System.out.println("Unsorted array:");
printArray(arr);
selectionSort(arr);
System.out.println("Sorted array:");
printArray(arr);
}
}
3.2 复杂度分析
- 时间复杂度：最坏、最好、平均情况都是 (O(n^2))。
- 空间复杂度：(O(1))，是原地排序算法。
3.3 动态演示
选择排序每次选出最小的元素，并与当前元素交换位置。图示中，每一轮都选择最小值，并把它放到正确的位置。
4. 插入排序 (Insertion Sort)
插入排序是一种简单的排序算法，基本思想是：将当前元素插入到已排序部分的合适位置，直到所有元素都被插入。
4.1 插入排序实现
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;
// 将arr[i]插入到已排序部分的正确位置
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
public static void printArray(int[] arr) {
for (int i : arr) {
System.out.print(i + " ");
}
System.out.println();
}
public static void main(String[] args) {
int[] arr = {64, 25, 12, 22, 11};
System.out.println("Unsorted array:");
printArray(arr);
insertionSort(arr);
System.out.println("Sorted array:");
printArray(arr);
}
}
4.2 复杂度分析
- 时间复杂度：最坏和平均情况为 (O(n^2))，最好情况为 (O(n))（已经有序的情况下）。
- 空间复杂度：(O(1))，是原地排序算法。
4.3 动态演示
插入排序将当前元素插入到已经排序的部分，图示中，每一轮都会在已排序部分插入新元素。
5. 快速排序 (Quick Sort)
快速排序是一种基于分治法的排序算法，其基本思想是：选择一个基准元素，通过一趟排序将数据分成两部分，其中一部分所有元素都比基准元素小，另一部分所有元素都比基准元素大，然后再递归地对这两部分数据进行排序。
5.1 快速排序实现
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high); // 获取分区点
quickSort(arr, low, pi - 1); // 对左部分排序
quickSort(arr, pi + 1, high); // 对右部分排序
}
}
private static int partition(int[] arr, int low, int high) {
int pivot = arr[high]; // 选择最后一个元素作为基准
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
public static void printArray(int[] arr) {
for (int i : arr) {
System.out.print(i + " ");
}
System.out.println();
}
public static void main(String[] args) {
int[] arr = {64, 25, 12, 22, 11};
System.out.println("Unsorted array:");
printArray(arr);
quickSort(arr, 0, arr.length - 1);
System.out.println("Sorted array:");
printArray(arr);
}
}
5.2 复杂度分析
- 时间复杂度：最坏情况为 (O(n^2))，平均情况为 (O(n \log n))。
- 空间复杂度：(O(\log n))，递归栈的空间。
5.3 动态演示
快速排序通过分治的方式，不断将数组分成小的子数组，并对其进行排序。每次选择一个基准元素并将数组分为两部分。
6. 归并排序 (Merge Sort)
归并排序也是基于分治法的排序算法，基本思想是：将数组分成两半，分别排序，然后合并排序结果。
6.1 归并排序实现
public class MergeSort {
public static void mergeSort(int[] arr) {
if (arr.length < 2) return;
int mid = arr.length / 2;
int[] left = new int[mid];
int[] right = new int[arr.length - mid];
System.arraycopy(arr, 0, left, 0, mid);
System.arraycopy(arr, mid, right, 0, arr.length - mid);
mergeSort(left);
mergeSort(right);
merge(arr, left, right);
}
private static void merge(int[] arr, int[] left, int[] right) {
int i = 0, j = 0, k = 0;
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
arr[k++] = left[i++];
} else {
arr[k++] = right[j++];
}
}
while (i < left.length) {
arr[k++] = left[i++];
}
while (j < right.length) {
arr[k++] = right[j++];
}
}
public static void printArray(int[] arr) {
for (int i : arr) {
System.out.print(i + " ");
}
System.out.println();
}
public static void main(String[] args) {
int[] arr = {64, 25, 12, 22, 11};
System.out.println("Unsorted array:");
printArray(arr);
mergeSort(arr);
System.out.println("Sorted array:");
printArray(arr);
}
}
6.2 复杂度分析
- 时间复杂度：最坏、最好、平均情况都是 (O(n \log n))。
- 空间复杂度：(O(n))，需要额外的空间存储左右子数组。
6.3 动态演示
归并排序通过不断分割数组并合并排序后的子数组来实现排序。
7. 希尔排序 (Shell Sort)
希尔排序是一种插入排序的改进版，其基本思想是：通过一定间隔对数组进行分组，并对每组进行插入排序，随着间隔逐步减小，最终变成一个普通的插入排序。
7.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 = i;
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
}
}
public static void printArray(int[] arr) {
for (int i : arr) {
System.out.print(i + " ");
}
System.out.println();
}
public static void main(String[] args) {
int[] arr = {64, 25, 12, 22, 11};
System.out.println("Unsorted array:");
printArray(arr);
shellSort(arr);
System.out.println("Sorted array:");
printArray(arr);
}
}
7.2 复杂度分析
- 时间复杂度：最坏情况下为 (O(n^2))，最好的情况为 (O(n \log n))。
- 空间复杂度：(O(1))，是原地排序算法。
7.3 动态演示
希尔排序每次通过减少间隔来缩小排序范围，最终通过普通插入排序完成排序。
8. 总结
本篇文章深入讲解了七种经典的排序算法，并提供了 Java 实现代码。每种算法都有其独特的优缺点，选择合适的排序算法对于提高程序的性能至关重要。在实际应用中，我们应根据数据的规模、数据的分布等因素选择合适的排序算法。
更多推荐
11
0- 0
已为社区贡献12条内容
所有评论(0)