java冒泡排序和选择排序详解

Java冒泡排序和选择排序详解

冒泡排序

冒泡排序是最简单的排序算法之一，也是入门学习排序算法的基础。该算法的主要思路是从最后一个元素开始，与前面一个元素比较并交换，直到最终将最小元素移动到第一个位置。

1. 冒泡排序实现原理

冒泡排序算法每一轮比较都会将相邻元素中较大或较小的一个元素“冒泡”到待排序序列的最后一个位置。类似于鸡尾酒中的冒泡，所以也叫做“鸡尾酒排序”。

1. 算法伪代码

冒泡排序

foreach i in n-1..1
    foreach j in 0..i-1
        if arr[j] > arr[j+1]
            swap arr[j] and arr[j+1]

3.示例说明

以数组{4, 3, 5, 1, 2}为例，我们通过冒泡排序来将数组中的元素按照从小到大的顺序排列。

首先，我们比较 3 和 4，由于 3 比 4 小，因此将它们交换位置，数组变为 {3, 4, 5, 1, 2}。

接着，比较 4 和 5，由于它们已经是有序的，所以不需要交换。

接下来是 5 和 1 的比较，由于 1 比 5 小，因此将它们交换位置，数组变为 {3, 4, 1, 5, 2}。

再比较 5 和 2，由于 2 比 5 小，因此将它们交换位置，数组变为 {3, 4, 1, 2, 5}。

现在得到了序列中的最小值 2，然后重复以上过程，不断地将最小元素移动到第一个位置。

在第一次比较中，我们需要比较4次，如果n为数组长度，那么我们需要进行n -1轮比较。

选择排序

选择排序是一种简单但效率较低的排序算法。它的主要思路是在未排序的序列中找到最小或最大的元素，然后将其放到排序序列的起始位置，直到排序完毕。

1. 选择排序实现原理

选择排序算法每一轮都会在未排序区间中找到最小（或最大）的元素，然后将其交换放到当前未排序序列的起始位置，这样就完成了一次排序。

1. 算法伪代码

选择排序

foreach i in 0..n-2
    min_index = i
    foreach j in i+1..n-1
        if arr[j] < arr[min_index]
            min_index = j
    if min_index != i
        swap arr[i] and arr[min_index]

1. 示例说明

以数组{4, 3, 5, 1, 2}为例，我们通过选择排序来将数组中的元素按从小到大的顺序排列。

首先，我们将当前的最小值设置为数组第一个元素，即 4，然后在数组的剩余元素 {3, 5, 1, 2} 中找到最小元素 1，并与当前最小元素 4 交换位置，得到 {1, 5, 3, 4, 2}。

然后，在 {5, 3, 4, 2} 中找到最小值 2，并与当前最小元素 1交换位置，得到 {1, 2, 4, 3, 5}。

接下来是 {4, 3, 5}中的最小元素 3，与4交换位置，得到 {1, 2, 3, 4, 5}。

最后，进行最后一轮比较，得到有序数组{1, 2, 3, 4, 5}。

选择排序的时间复杂度为 $O(n^2)$，与冒泡排序相同。