数据结构第19节 排序算法（1）

冒泡排序是一种简单的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

冒泡排序步骤详解

假设我们有以下数组：

int[] arr = {64, 34, 25, 12, 22, 11, 90};

第一轮冒泡排序

第一轮结束后，最大的元素90已经到达了正确的位置。

第二轮冒泡排序

第二轮结束后，次大的元素64已经到达了正确的位置。

在冒泡排序的过程中，每一轮都会把当前未排序部分的最大值“浮”到正确的位置。在前两轮之后，我们已经有了最大值90和次大值64在正确的位置。接下来，我们展示第三轮冒泡排序的详细过程。

假设我们有以下数组：

int[] arr = {34, 25, 12, 22, 11, 64, 90};

第三轮冒泡排序

在这一轮结束时，数组的状态如下：

arr = {25, 12, 22, 11, 34, 64, 90};

可以看到，经过第三轮的冒泡，数组中的第三大的值34已经移动到了它的正确位置，即数组的倒数第三位。

第四轮冒泡排序

在这一轮结束时，数组的状态如下：

arr = {12, 22, 11, 25, 34, 64, 90};

第五轮冒泡排序

在这一轮结束时，数组的状态如下：

arr = {11, 12, 22, 25, 34, 64, 90};

此时，数组已经完全排序，所有元素都在它们应该在的位置上。

需要注意的是，冒泡排序的优化版本会在一轮遍历中如果没有发生任何交换则停止排序，这意味着数组已经是有序的。在这个例子中，第五轮排序完成后，数组已经是升序排列，所以后续的遍历将不会发生任何变化。

最终的排序结果应该是：

arr = {11, 12, 22, 25, 34, 64, 90};

冒泡排序的Java代码实现

下面是使用Java实现冒泡排序的代码：

public class BubbleSortExample {
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};

        bubbleSort(arr);

        System.out.println("Sorted array : ");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    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]) {
                    // Swap arr[j+1] and arr[j]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }
            // 如果在某次遍历中没有发生任何交换，说明数组已经排序完成
            if (!swapped)
                break;
        }
    }
}

在这段代码中，我们使用了两层循环。外层循环控制排序的轮数，内层循环负责比较和交换相邻的元素。如果在某次遍历中没有发生任何交换，说明数组已经排序完成，此时可以提前终止排序，以节省不必要的比较。这是冒泡排序的一个优化点。

选择排序（Selection Sort）是一种简单直观的比较排序算法。它的工作原理是遍历数组，每次从未排序的部分找出最小（或最大）的元素，存放到排序序列的起始位置，直到所有元素均排序完毕。

选择排序步骤详解

假设我们有以下数组：

int[] arr = {64, 34, 25, 12, 22, 11, 90};

第一轮选择排序

第二轮选择排序

第三轮选择排序

依此类推，直到整个数组排序完成

选择排序的Java代码实现

下面是使用Java实现选择排序的代码：

public class SelectionSortExample {
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        
        selectionSort(arr);
        
        System.out.println("Sorted array : ");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

    static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            // Find the minimum element in unsorted array
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[minIndex] > arr[j]) {
                    minIndex = j;
                }
            }
            // Swap the found minimum element with the first element
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }
}

在这段代码中，我们使用了两层循环。外层循环迭代整个数组，而内层循环则用于找到剩余未排序部分的最小元素。一旦找到了最小元素，我们就将其与未排序部分的第一个元素交换。这样，每一次外层循环的迭代都会将未排序部分的最小元素放置到正确的位置上。

性能分析

选择排序的时间复杂度为O(n^2)，无论在最好、最坏还是平均情况下都是如此。这是因为对于n个元素的数组，需要进行n次查找最小值的操作，每次查找都需要遍历剩下的元素，所以总的操作次数大约是n*(n-1)/2。尽管其实现简单，但在大数据量的情况下，选择排序的效率较低。

插入排序（Insertion Sort）是一种简单直观的排序算法，其工作原理类似于人们手动排序扑克牌的方式。在插入排序中，数组被分为已排序和未排序两部分。初始时，已排序部分只包含第一个元素，未排序部分包含剩余的所有元素。算法通过从未排序部分取出一个元素，并在已排序部分找到正确的位置将其插入，逐步扩大已排序部分的范围，直至整个数组排序完成。

插入排序步骤详解

假设我们有以下数组：

int[] arr = {64, 34, 25, 12, 22, 11, 90};

第一轮插入排序

第二轮插入排序

第三轮插入排序

依此类推，直到整个数组排序完成

插入排序的Java代码实现

下面是使用Java实现插入排序的代码：

public class InsertionSortExample {
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        
        insertionSort(arr);
        
        System.out.println("Sorted array : ");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

    static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; ++i) {
            int key = arr[i];
            int j = i - 1;
            
            /* Move elements of arr[0..i-1], that are greater than key,
               to one position ahead of their current position */
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
}

在这段代码中，我们使用了一个循环来迭代数组中的每个元素，除了第一个元素外（因为单个元素自动认为是已排序的）。对于每个元素，我们将其保存在一个变量key中，然后在已排序的部分中找到它的正确位置，并将所有比key大的元素向右移动一位，为key腾出空间，最后将key插入到正确的位置。

性能分析

插入排序的时间复杂度在最好情况（数组已经是排序的）下为O(n)，在最坏情况（数组是逆序的）和平均情况下为O(n^2)。尽管对于大规模数据而言效率较低，但对于小规模数据或部分已排序的数据，插入排序的性能仍然相当不错。