当前位置：首页 > article >正文

常见排序算法总结 (一) - 三种基本排序

article 2024/11/26 9:11:14

排序算法的稳定性

稳定性是指，在算法思想不改变的前提下，能否给出一种实现，保证对任意待排序列中值相同的两个元素，在排序之后保持相对位置不变。因此稳定性是和可以和具体实现无关的，对于某一种算法，只要有不改变相对顺序的实现方案存在，它就具有稳定性。
强调值相同，是因为在数值排序中讨论稳定性其实是没有意义的。但是运用算法的过程中，我们常常会遇到结构或是对象的排序。这时候，当二者的键相同时是否改变相对位置可能就有区别了。

选择排序

算法思想

根据数组长度进行相应次数的操作，每一轮在数组的无序序列上找到最小值，并将它放到有序序列的最后一个位置。
假设数组长度为 $n$ ，当前轮次为 $i$ 。这一轮需要做的就是，在 $[i, n - 1]$ 的范围内找到最小值的下标 $min I n d e x$ ，将它与下标 $i$ 处的元素进行交换。下一轮将 $i$ 滚动到 $i + 1$ ，重复上述操作。

稳定性分析

选择排序是不稳定的，问题出在最小值和当前元素交换的过程中，它可能会修改当前元素与值相等的元素之间的相对位置。

具体实现

// 交换数组中的两个元素
private void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

public void selectionSort(int[] arr) {
    // minIndex 表示当前轮次最小值的位置下标
    // 单个元素天然有序，可以少进行一轮操作
    for (int minIndex, i = 0; i < arr.length - 1; i++) {
        minIndex = i; // 每次选择之前要进行初始化
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        swap(arr, i, minIndex);
    }
}

冒泡排序

算法思想

根据数组长度进行相应次数的操作，每一轮依次比较相邻元素的大小关系并交换相邻的逆序对，将待排序列的最大值放到最后一个位置上。
假设数组长度为 $n$ ，当前轮次为 $i$ ，当前比较的元素下标为 $j$ 。这一轮需要做的就是，在 $[0, n - i - 1]$ 的范围内依次比较 $j$ 与 $j + 1$ 的大小关系并交换逆序。下一轮将 $i$ 滚动到 $i + 1$ ，重复上述操作。

冒泡排序还有一个优化，如果某一次操作中没有发生交换，说明排序已经完成，可以结束循环。

稳定性分析

冒泡排序是稳定的，只要在实现的时候保证相等的相邻元素不交换即可。

具体实现

// 交换数组中的两个元素
private void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

public void bubbleSort(int[] arr) {
    // 单个元素天然有序，可以少进行一轮操作
    for (int i = 0; i < arr.length - 1; i++) {
        // 在 0 到 (n - i - 1) 的范围内依次比较相邻元素并交换逆序
        for (int j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1);
            }
        }
    }
}

插入排序

算法思想

根据数组长度进行相应次数的操作，每一轮后移大于待处理元素的其他元素，再将当前元素插入到合适的位置。
假设数组长度为 $n$ ，当前待处理元素下标为 $i$ 。这一轮需要做的就是，后移 $[0, i - 1]$ 范围内所有大于当前元素 $a rr [i]$ 的元素，再将它插入到挪出来的位置 $in d e x + 1$ 。

稳定性分析

冒泡排序是稳定的，只要在实现的时候保证相等的元素不后移即可。

具体实现

public void insertionSort(int[] arr) {
    // 第一个元素天然有序，不做任何处理
    for (int i = 1; i < arr.length; i++) {
        // 后移时当前元素会被覆盖掉，先暂存一下
        int temp = arr[i];
        int index = i - 1;
        // 后移所有 0 到 (i - 1) 范围内大于当前元素的元素
        while (index >= 0 && arr[index] > temp) {
            arr[index + 1] = arr[index];
            index--;
        }
        // 将当前元素插入到合适的位置
        arr[index + 1] = temp;
    }
}