Java数据结构和算法之冒泡、选择和插入排序算法

冒泡排序算法

算法思路

冒泡排序是一种基础的排序算法，它通过比较相邻元素的大小并交换位置，将最大（或最小）的元素逐步“冒泡”到序列的最后，从而完成排序。

具体地，冒泡排序的过程如下：

1. 从序列的第一个元素开始，依次比较相邻的两个元素，如果前面的元素大于后面的元素，则交换它们的位置。
2. 继续依次比较相邻的元素，直到序列的倒数第二个元素为止。
3. 重复执行步骤 1、2，直到序列全部排序完成。

示例说明

下面是一组示例数据：

int[] arr = {4, 2, 8, 3, 1};

使用冒泡排序算法对其进行排序，可得到如下过程：

// 第 1 轮
arr[0] 和 arr[1] 比较，arr[0] < arr[1]，不交换位置
arr[1] 和 arr[2] 比较，arr[1] > arr[2]，交换位置，arr 变成 {4, 8, 2, 3, 1}
arr[2] 和 arr[3] 比较，arr[2] < arr[3]，不交换位置
arr[3] 和 arr[4] 比较，arr[3] > arr[4]，交换位置，arr 变成 {4, 8, 2, 1, 3}

// 第 2 轮
arr[0] 和 arr[1] 比较，arr[0] < arr[1]，不交换位置
arr[1] 和 arr[2] 比较，arr[1] < arr[2]，不交换位置
arr[2] 和 arr[3] 比较，arr[2] > arr[3]，交换位置，arr 变成 {4, 2, 1, 8, 3}
arr[3] 和 arr[4] 比较，arr[3] < arr[4]，不交换位置

// 第 3 轮
arr[0] 和 arr[1] 比较，arr[0] > arr[1]，交换位置，arr 变成 {2, 4, 1, 8, 3}
arr[1] 和 arr[2] 比较，arr[1] < arr[2]，不交换位置
arr[2] 和 arr[3] 比较，arr[2] > arr[3]，交换位置，arr 变成 {2, 1, 4, 8, 3}
arr[3] 和 arr[4] 比较，arr[3] > arr[4]，交换位置，arr 变成 {2, 1, 4, 3, 8}

// 第 4 轮
arr[0] 和 arr[1] 比较，arr[0] > arr[1]，交换位置，arr 变成 {1, 2, 4, 3, 8}
arr[1] 和 arr[2] 比较，arr[1] < arr[2]，不交换位置
arr[2] 和 arr[3] 比较，arr[2] > arr[3]，交换位置，arr 变成 {1, 2, 3, 4, 8}

// 第 5 轮
arr[0] 和 arr[1] 比较，arr[0] < arr[1]，不交换位置
arr[1] 和 arr[2] 比较，arr[1] < arr[2]，不交换位置
arr[2] 和 arr[3] 比较，arr[2] < arr[3]，不交换位置
arr[3] 和 arr[4] 比较，arr[3] < arr[4]，不交换位置

可见，经过 5 轮排序，序列被正确排序。在最坏情况下，即原序列为逆序排列时，冒泡排序算法的时间复杂度为 O(n^2)。

选择排序算法

算法思路

选择排序算法也是一种基础的排序算法，它通过和冒泡排序不同的思路进行排序。选择排序过程中，依次遍历整个序列，每次找到未排序部分中的最小值（或最大值），并将其放置在已排序部分的末尾。

具体地，选择排序的过程如下：

1. 设置一个变量 minIndex，初始值和第一个未排序元素的下标相同。
2. 依次遍历未排序部分的每个元素，将其与 minIndex 指向的元素进行比较，如果找到一个更小（或更大）的元素，则将 minIndex 更新为该元素的下标。
3. 遍历到序列末尾后，将找到的最小值（或最大值）直接与未排序部分的第一个元素进行交换，从而将其放置在已排序部分的末尾。
4. 重复执行步骤 2、3，直到整个序列全部排序完成。

示例说明

下面是一组示例数据：

int[] arr = {4, 2, 8, 3, 1};

使用选择排序算法对其进行排序，可得到如下过程：

// 第 1 轮
从 arr[0] 开始遍历，找到 arr[4] 最小，将 arr[0] 和 arr[4] 交换，arr 变成 {1, 2, 8, 3, 4}

// 第 2 轮
从 arr[1] 开始遍历，找到 arr[3] 最小，将 arr[1] 和 arr[3] 交换，arr 变成 {1, 2, 8, 3, 4}

// 第 3 轮
从 arr[2] 开始遍历，找到 arr[3] 最小，将 arr[2] 和 arr[3] 交换，arr 变成 {1, 2, 3, 8, 4}

// 第 4 轮
从 arr[3] 开始遍历，找到 arr[4] 最小，将 arr[3] 和 arr[4] 交换，arr 变成 {1, 2, 3, 4, 8}

// 第 5 轮
遍历完成，整个序列已全部排序完成。

可见，经过 5 轮排序，序列被正确排序。与冒泡排序算法相同，选择排序算法的时间复杂度也为 O(n^2)。

插入排序算法

算法思路

插入排序算法是一种较为高效的排序算法，尤其适用于对有序或基本有序的数据进行排序。插入排序算法的基本思路是将未排序部分中的元素逐个插入到已排序部分中相应的位置。

具体地，插入排序的过程如下：

1. 将序列分为已排序部分和未排序部分，初始时已排序部分只包含第一个元素，未排序部分包含剩余所有元素。
2. 遍历未排序部分的每个元素，将其依次插入到已排序部分中相应的位置。具体地，从序列的第二个元素开始，将其与已排序部分的元素依次比较，直到找到第一个比其大（或小）的元素，然后将该元素插入其前面，从而保证已排序部分仍然有序。
3. 重复执行步骤 2，直到未排序部分全部加入已排序部分为止。

示例说明

下面是一组示例数据：

int[] arr = {4, 2, 8, 3, 1};

使用插入排序算法对其进行排序，可得到如下过程：

// 第 1 轮
已排序部分只包含 arr[0]，未排序部分包含 arr[1] 到 arr[4]。取出 arr[1]，将其与 arr[0] 比较，发现 arr[1] 较小，将其插入 arr[0] 前面，此时已排序部分为 {2, 4}，未排序部分为 {8, 3, 1}。
取出 arr[2]，将其依次与已排序部分的元素比较，发现它应该插入到 arr[1] 后面，此时已排序部分为 {2, 4, 8}，未排序部分为 {3, 1}。
取出 arr[3]，将其依次与已排序部分的元素比较，发现它应该插入到 arr[1] 前面，此时已排序部分为 {2, 3, 4, 8}，未排序部分为 {1}。
取出 arr[4]，将其依次与已排序部分的元素比较，发现它应该插入到 arr[0] 前面，此时已排序部分为 {1, 2, 3, 4, 8}，未排序部分为空。

// 第 2 轮
整个序列已全部排序完成。

可见，经过 2 轮排序，序列被正确排序。相比冒泡排序和选择排序，插入排序的时间复杂度较低，最好情况下为 O(n)，平均情况下为 O(n^2)。