likes
comments
collection

三种时间复杂度为O(N²)的排序算法

作者站长头像
站长
· 阅读数 13

数据结构和算法这个东西,如果你不去学,可能真的这辈子都用不到,也感受不到它的好。但是一旦掌握,你就会常常被它的强大威力所折服。之前你可能需要费很大劲儿来优化的代码,需要花很多心思来设计的架构,用了数据结构和算法之后,很容易就可以解决了。

排序是一个非常经典的问题,它以一定的 顺序 对一个 数组 (或一个 列表 )中的项进行重新排序(可以进行比较的,例如整数,浮点数,字符串等)。

有许多不同的 排序算法 ,每个都有其自身的优点和局限性。

基于比较的排序算法:

比较数组的元素,并决定是否交换它们的位置。

  • BUB - 冒泡排序
  • SEL - 选择排序
  • INS - 插入排序
  • MER - 归并排序 (递归实现)
  • QUI - 快速排序 (递归实现)
  • R-Q - 随机快速排序 (递归实现)

不基于比较的排序算法:

  • COU - 计数排序
  • RAD - 基数排序

我们来逐一破解这些排序算法。

本文分析 冒泡排序选择排序插入排序

冒泡排序

假设数组 arr 长度为 NNN ,冒泡排序的过程为:

arr[0~N-1] 范围上:

arr[0] 和 arr[1],谁大谁来到1位置;

arr[1]和arr[2],谁大谁来到2位置;

[N-2]和arr[N-1],谁大谁来到N-1位置;

在arr[0~N-2]范围上,重复上面的过程,但最后一步是arr[N-3]和arr[N-2],谁大谁来到N-2位置;

在arr[0~N-3]范围上,重复上面的过程,但最后一步是arr[N-4]和arr[N-3],谁大谁来到N-3位置;

最后在arr[0~1]范围上,重复上面的过程,但最后一步是arr[0]和arr[1],谁大谁来到1位置。

整个过程将最大的元素移动到最右侧,也就是最大的元素浮动到最右边,像冒泡一样。

如图所示:

三种时间复杂度为O(N²)的排序算法

如图展示了第1趟排序的过程。

自己会动的才是好图:

三种时间复杂度为O(N²)的排序算法

代码实现:

public class BubbleSort {

    public static void main(String[] args) {
        int[] arr = {18, 15, 13, 17, 6, 20, 15, 9};
        sort(arr);
    }

    public static void sort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        //想要让0~i位置上有序,i一开始在数组的最大索引位置上,每比完1次,减1
        for (int i = arr.length - 1; i > 0; i--) {
            //0~i
            //0~(i-1)
            //0~(i-2)...
            //0~1
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
            System.out.println("0~" + i + "位置比较结果:" + Arrays.toString(arr));
        }
    }
}

执行结果:

0趟比较结果:[15, 13, 17, 6, 18, 15, 9, 20]1趟比较结果:[13, 15, 6, 17, 15, 9, 18, 20]2趟比较结果:[13, 6, 15, 15, 9, 17, 18, 20]3趟比较结果:[6, 13, 15, 9, 15, 17, 18, 20]4趟比较结果:[6, 13, 9, 15, 15, 17, 18, 20]5趟比较结果:[6, 9, 13, 15, 15, 17, 18, 20]6趟比较结果:[6, 9, 13, 15, 15, 17, 18, 20]7趟比较结果:[6, 9, 13, 15, 15, 17, 18, 20]

时间复杂度的计算:

比较和交换需要一个以 常量 为界的时间,我们称之为 ccc

Bubble Sort 中有两个嵌套循环。

外循环正好运行 NNN 次迭代。但内部循环运行变得越来越短:

当 i = 0,(N-1)次迭代(比较和可能交换)时。

当 i = 1,(N-2)次迭代时,...

当 i =(N-2)时,1次迭代,

当 i=(N-1),0迭代.

因此:

总迭代次数=(N−1)+(N−2)+...+1+0=N×(N−1)/2总迭代次数=(N-1)+(N-2)+ ... + 1 + 0 = N ×(N-1)/ 2=N1+N2+...+1+0=N×N1/2

计算总时间:

总时间=c×N×(N−1)/2=O(N²)总时间= c × N ×(N-1)/ 2 = O(N²)=c×N×N1/2=ON²

选择排序

给定 NNN 个元素和 L = 0 的数组,选择排序过程为:

  1. 在 [L ... N-1] 范围内找出最小项 X 的位置,
  2. 用第 L 项交换X,
  3. 将下限 L 增加1并重复步骤1直到 L = N-2。

手绘选择排序过程:

三种时间复杂度为O(N²)的排序算法

动画演示:

三种时间复杂度为O(N²)的排序算法

代码实现:

public class SelectionSort {

    public static void main(String[] args) {
        int[] arr = {18, 15, 13, 17, 6, 20, 15, 9};
        sort(arr);
    }

    public static void sort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            //目的:找到最小值的位置,并将该位置的数与i位置的数交换
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                minIndex = arr[j] > arr[minIndex] ? minIndex : j;
            }
            //找到最小值后,与i位置的数交换
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
            System.out.println("第" + i + "~" + (arr.length - 1) + "位置上的最小值索引为" + minIndex + ",最小值为:" + arr[minIndex] + ",本次排序结果:" + Arrays.toString(arr
            ));
        }
    }
}

运行结果:

0~7位置上的最小值索引为4,最小值为:18,本次排序结果:[6, 15, 13, 17, 18, 20, 15, 9]1~7位置上的最小值索引为7,最小值为:15,本次排序结果:[6, 9, 13, 17, 18, 20, 15, 15]2~7位置上的最小值索引为2,最小值为:13,本次排序结果:[6, 9, 13, 17, 18, 20, 15, 15]3~7位置上的最小值索引为7,最小值为:17,本次排序结果:[6, 9, 13, 15, 18, 20, 15, 17]4~7位置上的最小值索引为6,最小值为:18,本次排序结果:[6, 9, 13, 15, 15, 20, 18, 17]5~7位置上的最小值索引为7,最小值为:20,本次排序结果:[6, 9, 13, 15, 15, 17, 18, 20]6~7位置上的最小值索引为6,最小值为:18,本次排序结果:[6, 9, 13, 15, 15, 17, 18, 20]

总结一下选择排序的过程:

arr[0~N-1]范围上,找到最小值所在的位置,然后把最小值交换到0位置。

arr[1~N-1]范围上,找到最小值所在的位置,然后把最小值交换到1位置。

arr[2~N-1]范围上,找到最小值所在的位置,然后把最小值交换到2位置。

arr[N-1~N-1]范围上,找到最小值位置,然后把最小值交换到N-1位置。

估算: 很明显,如果 arr 长度为 N ,每一步常数操作的数量,如等差数列一般,所以有:

总的常数操作数量=a∗(N²)+b∗N+c(a、b、c都是常数)总的常数操作数量 = a*(N²) + b*N + c (a、b、c都是常数)=a(N²)+bN+c(abc)

所以选择排序的时间复杂度为 O(N²)O(N²)O(N²)

插入排序

这个算法比较好理解,想像一下平时打扑克牌,我们很自然的就会把一张牌和手里的牌挨个比较一下,并把它插入到合适的位置。

三种时间复杂度为O(N²)的排序算法

过程:

  1. 想让arr[0~0]上有序,这个范围只有一个数,当然是有序的;
  2. 想让arr[0~1]上有序,所以从arr[1]开始往前看,如果 arr[1] < arr[0] ,就交换。否则什么也不做;

  1. 想让arr[0~i]上有序,所以从arr[i]开始往前看,arr[i]这个数不停向左移动,一直移动到左边的数字不再比自己大,停止移动;
  2. 最后一步,想让arr[0~N-1]上有序,arr[N-1]这个数不停向左移动,一直移动到左边的数字不再比自己大,停止移动。

估算时发现这个算法流程的复杂程度,会因为数据状况的不同而不同。

如果某个算法流程的复杂程度会根据数据状况的不同而不同,那么必须要按照 最差情况 来估计。

很明显,在最差情况下,如果 arr 长度为 N ,插入排序的每一步常数操作的数量,还是如等差数列一般。

所以有:

总的常数操作数量=a∗(N²)+b∗N+c(a、b、c都是常数)总的常数操作数量 = a*(N²) + b*N + c (a、b、c都是常数)=a(N²)+bN+c(abc)

因此插入排序排序的时间复杂度为 O(N²)O(N²)O(N²)

代码实现:

public class InsertionSort {
    public static void main(String[] args) {
        int[] arr = {18, 15, 13, 17, 6, 20, 15, 9};
        sort(arr);
    }

    public static void sort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        //想让0~i位置上有序,从i位置往前看,一直到左边的数不比自己大了,停止往左看
        for (int i = 1; i < arr.length; i++) {
            //j=i表示从i位置开始,j--表示往前看
            for (int j = i; j > 0; j--) {
                if (arr[j] < arr[j - 1]) {
                    int temp = arr[j - 1];
                    arr[j - 1] = arr[j];
                    arr[j] = temp;
                }
            }
            System.out.println("从" + i + "位置往前看,直到左边的数不比自己大,本次结果:" + Arrays.toString(arr));
        }
    }
}

运行结果:

1位置往前看,直到左边的数不比自己大,本次结果:[15, 18, 13, 17, 6, 20, 15, 9]2位置往前看,直到左边的数不比自己大,本次结果:[13, 15, 18, 17, 6, 20, 15, 9]3位置往前看,直到左边的数不比自己大,本次结果:[13, 15, 17, 18, 6, 20, 15, 9]4位置往前看,直到左边的数不比自己大,本次结果:[6, 13, 15, 17, 18, 20, 15, 9]5位置往前看,直到左边的数不比自己大,本次结果:[6, 13, 15, 17, 18, 20, 15, 9]6位置往前看,直到左边的数不比自己大,本次结果:[6, 13, 15, 15, 17, 18, 20, 9]7位置往前看,直到左边的数不比自己大,本次结果:[6, 9, 13, 15, 15, 17, 18, 20]

三种时间复杂度为O(N²)的排序算法

点个赞再走吧~