选择排序、冒泡排序、插入排序

在计算机科学中，排序是处理数据的基本操作之一。本文将详细介绍三种经典的排序算法：选择排序、冒泡排序和插入排序，并结合Java代码进行分析。 ### 1. 选择排序（Selection Sort） 选择排序的主要思想是每次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。其具体步骤如下： 1. 遍历数组，找到当前未排序部分的最小元素。 2. 将最小元素与未排序部分的第一个元素交换位置。 3. 重复以上步骤，直至整个数组排序完成。 **Java实现**： ```java public static void selectionSort(int[] ary) { for (int i = 0; i < ary.length - 1; i++) { // 寻找未排序部分的最小元素 int minIndex = i; for (int j = i + 1; j < ary.length; j++) { if (ary[j] < ary[minIndex]) { minIndex = j; } } // 将最小元素与未排序部分的第一个元素交换 int temp = ary[i]; ary[i] = ary[minIndex]; ary[minIndex] = temp; } } ``` ### 2. 冒泡排序（Bubble Sort） 冒泡排序通过重复遍历待排序的列表，比较每对相邻元素，如果顺序错误则交换它们，从而使得每一轮遍历都将最大的元素“冒”到末尾。其主要步骤如下： 1. 逐个比较相邻元素，如果前面的元素大于后面的元素，则交换位置。 2. 每轮遍历结束后，最大元素会“冒”到末尾。 3. 重复此过程，直到所有元素排序完成。 **Java实现**： ```java public static void bubbleSort(int[] ary) { for (int i = 0; i < ary.length - 1; i++) { // 控制每轮遍历的次数，每次少一个比较 for (int j = 0; j < ary.length - i - 1; j++) { if (ary[j] > ary[j + 1]) { int temp = ary[j]; ary[j] = ary[j + 1]; ary[j + 1] = temp; } } } } ``` ### 3. 插入排序（Insertion Sort） 插入排序将数组分为已排序部分和未排序部分，每次从未排序部分取出一个元素，插入到已排序部分的正确位置。其主要步骤如下： 1. 从未排序部分取出第一个元素，与已排序部分的元素逐个比较，找到合适的位置插入。 2. 重复此过程，直到所有元素插入到已排序部分。 **Java实现**： ```java public static void insertSort(int[] arr) { for (int i = 1; i < arr.length; i++) { // 已排序部分的最后一个元素 int cur = arr[i]; int j = i - 1; // 查找插入位置 while (j >= 0 && arr[j] > cur) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = cur; } } ``` 这三种排序算法各有优缺点。选择排序每次选择最小元素，时间复杂度为O(n^2)，但交换次数较少；冒泡排序适用于小规模数据，稳定但效率较低；插入排序在部分有序的数据中表现优秀，时间复杂度可以达到O(n)。理解这些基本排序算法对于编程初学者来说至关重要，因为它们为理解和分析更复杂的排序算法奠定了基础。