排序算法学习(1)-简单排序

选择排序

选择排序(Selection Sort)是一种非常简单明了的排序算法,其基本思路是:假设一个数组有 n 个数,从第一个数开始,遍历一遍找到最小的一个数的下标,将最小的数与第一个数交换位置,这样第一个数的位置就排好了,接下来从第二个数开始遍历找到从 2 到 n 中最小的数与第二个数做交换,如此反复,知道第 n-1 个数也排好序了,整个数组排序就结束了。

示意图

SelectionSort_1.png

代码示例:

public class SelectionSort {
    public static void sort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int mini = i;
            for (int j = i+1; j < arr.length; j++) {
                if(arr[j] < arr[mini]) {
                    mini = j;
                }
            }
            swap(arr, i, mini);
        }
    }
}

时间复杂度和空间复杂度

算法第一次循环执行 n-1 次,第二次循环执行 n-2 次,以此类推,直到排序完成大约执行了 (n-1) + (n-2) + ... + 2 + 1,这是一个等差数列,根据等差数列公式可以得出执行了 $\frac{n^2}{2} - \frac{n}{2}$ 次,忽略常数项和低次项得到时间复杂度 $O(n^2)$

根据算法的计算过程,可以知道不论是什么数组都要执行 $\frac{n^2}{2} - \frac{n}{2}$ ,其最好和最差的情况下时间复杂度都是 $O(n^2)$

算法除开一些临时变量并没有使用一些额外空间,因此空间复杂度是 $O(1)$

稳定性

由于算法是直接将数组中找到的最后一个最小的数与第一个数交换,因此相等的两个数的顺序会在交换之后改变,所以选择排序是一个不稳定的排序算法

SelectionSort_2.png

优化

在一次循环遍历中同时找到最大和最小值,分别与最后一位和第一位数进行交换,减少循环的次数。尽管如此,其时间复杂度任然是 $O(n^2)$

SelectionSort_3.png

代码示例:

public static void sort(int[] arr) {
     int len = arr.length;
     for (int i = 0; i < len/2; i++) {
        int mini = i;
        int maxi = i;
        for (int j = i + 1; j < len-i; j++) {
            if (arr[j] < arr[mini]) {
                mini = j;
            }
            if (arr[j] > arr[maxi]) {
                maxi = j;
            }
        }
        swap(arr, i, mini);
        // 注意在最大值交换前有可能已经被最小值交换
        if (maxi == i) {
            maxi = mini;
        }
        swap(arr, len-1 - i, maxi);
    }
}

冒泡排序

冒泡排序也是简单排序的一种,其算法思路是:假设一个数组的长度为 n ,比较第一个数和第二个数,若第一个数大于第二个数,交换两个数,再比较第二个数与第三个数的大小,大于则交换,同样地比较剩下的数,最后,最大的数将会到数组末尾,第 n 个数已经排好序了,再对 1 ~ n-1 的数做相同操作,1 ~ n-1 中最大的数会到 n-1 的位置,n-1 ~ n 是排好序的,重复这个 "冒泡" 过程,直到排序(若一次循环中未发生过一次交换可以提前结束排序)。

示意图

BubbleSort_1.png

如上图所示,5 8 排好序之后,剩下的 1 3 4 进行排序,同样的一次循环后将不会发生交换,说明剩下部分已经有序,此时可以提前结束排序。

代码示例

public class BubbleSort {
    public static void sort(int[] arr) {
        for (int i = arr.length; i > 1; i--) {
            boolean flag = true;
            for (int j = 1; j < i; j++) {
                if (arr[j-1] > arr[j]) {
                    swap(arr, j-1, j);
                    flag = false;
                }
            }
            if (flag) {
                break;
            }
        }
    }
}

时间复杂度和空间复杂度

冒泡排序在一般情况下,需要进行两层嵌套循环,第一次循环执行 n-1 次,第二次执行 n-2 次...,直到最后大约执行了 (n-1) + (n-2) + ... + 2 + 1 ,同样是等差数列,因此时间复杂度为 $O(n^2)$ 。最差情况下其时间复杂度为 $O(n^2)$ ,而如果程序中做了优化,在未发生交换时提前结束排序,则只需执行一次循环,所以最好情况的时间复杂度是 $O(n)$ 。

由于除了部分临时变量外,没有用到其他额外空间,所以其空间复杂度为 $O(1)$ 。

稳定性

在冒泡排序算法中,相邻两个数进行比较时,相等的数将不会进行交换,因此可以保证相等的数在排序后的顺序不变,是一种稳定的排序算法。

插入排序

插入排序是简单排序中的最后一种,插入排序顾名思义,类似于持有一手乱序的扑克牌,每次从无序的牌中取出一张插入有序的牌中,随着无序的牌组减少,整副牌趋于有序。其基本思路是:假设数组长度为 n ,从第二个数开始,同前一个数进行比较,若小于前一个数则交换,否则停止插入,再从第三个数开始往前面已经有序的部分插入,重复这个步骤,直到最后一个数插入完成,数组有序。

示意图

InsertSort_1.png

代码示例

public class InsertSort {
    public static void sort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0 && arr[j] < arr[j-1]; j--) {
                swap(arr, j, j-1);
            }
        }
    }
}

上面的代码需要每次进行交换,可以稍加改进:

public class InsertSort {
    public static void sort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int j = i;
            int temp = arr[j];
            while (j > 0 && temp < arr[j-1]) {
                arr[j] = arr[j-1];
                j--;
            }
            arr[j] = temp;
        }
    }
}

时间复杂度和空间复杂度

插入排序算法同样的使用到了嵌套循环,一般情况下整个算法大约执行了 1 + 2 + ... + (n-2) + (n-1) ,同样的时间复杂度是 $O(n^2)$ ,但是插入排序要比冒泡排序少了许多比较和交换的过程,会快得多,而且在比较有序的情况下,所用的时间会比较少,最好的情况下只需循环一次,因此最好时间复杂度为 $O(n)$ 。

同样的插入排序的空间复杂度为 $O(1)$ 。

稳定性

插入排序通过比较相邻元素的大小进行交换,因此同样是稳定的。

总结

三种简单排序算法的时间复杂度都是 $O(n^2)$ ,空间复杂度是 $O(1)$ ,冒泡排序和插入排序和插入排序的最好时间复杂度是 $O(n)$ ,是稳定排序,选择排序的最好时间复杂度是 $O(n^2)$ ,是不稳定排序,同时插入排序要比冒泡排序快一些,因此在数据量小时可以使用简单排序,优先使用插入排序。

评论

暂无评论