current position:Home>Three sorting algorithms with O(N²) time complexity

Three sorting algorithms with O(N²) time complexity

2022-08-06 20:02:53line barrier

携手创作,共同成长!这是我参与「掘金日新计划 · 8 月更文挑战」的第11天,点击查看活动详情

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

排序是一个非常经典的问题,It takes a certain 顺序 对一个 数组 (或一个 列表 )中的项进行重新排序(can be compared,例如整数,浮点数,字符串等).

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

基于比较的排序算法:

Compare elements of arrays,and decide whether to swap their positions.

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

不基于比较的排序算法:

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

Let's break these sorting algorithms one by one.

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

冒泡排序

假设数组 arr 长度为 N N ,The process of bubble sort is :

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位置.

The whole process moves the largest element to the far right,That is, the largest element floats to the far right,像冒泡一样.

如图所示:

冒泡排序.png

The figure shows the 1趟排序的过程.

A good picture is the one that moves by itself:

冒泡排序.gif

代码实现:

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位置上有序,iStart at the maximum index position of the array,After every match1次,减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 + "Location comparison results:" + Arrays.toString(arr));
        }
    }
}
复制代码

执行结果:

0Compare the results:[15, 13, 17, 6, 18, 15, 9, 20]1Compare the results:[13, 15, 6, 17, 15, 9, 18, 20]2Compare the results:[13, 6, 15, 15, 9, 17, 18, 20]3Compare the results:[6, 13, 15, 9, 15, 17, 18, 20]4Compare the results:[6, 13, 9, 15, 15, 17, 18, 20]5Compare the results:[6, 9, 13, 15, 15, 17, 18, 20]6Compare the results:[6, 9, 13, 15, 15, 17, 18, 20]7Compare the results:[6, 9, 13, 15, 15, 17, 18, 20]
复制代码

时间复杂度的计算:

Compare and swap requires a to 常量 bounded time,我们称之为 c c .

Bubble Sort 中有两个嵌套循环.

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

当 i = 0,(N-1)次迭代(Compare and possibly swap)时.

当 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

计算总时间:

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

选择排序

给定 N N 个元素和 L = 0 的数组,The selection sort process is :

  1. 在 [L ... N-1] Find the smallest item in the range X 的位置,
  2. 用第 L 项交换X,
  3. 将下限 L 增加1并重复步骤1直到 L = N-2.

Hand drawn selection sort process:

选择排序.png

动画演示:

选择排序.gif

代码实现:

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++) {
            //目的:找到最小值的位置,and sum the number at that positioni位置的数交换
            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) + "The index of the minimum value at the position is " + minIndex + ",最小值为:" + arr[minIndex] + ",The result of this sorting:" + Arrays.toString(arr
            ));
        }
    }
}
复制代码

运行结果:

0~7The index of the minimum value at the position is 4,最小值为:18,The result of this sorting:[6, 15, 13, 17, 18, 20, 15, 9]1~7The index of the minimum value at the position is 7,最小值为:15,The result of this sorting:[6, 9, 13, 17, 18, 20, 15, 15]2~7The index of the minimum value at the position is 2,最小值为:13,The result of this sorting:[6, 9, 13, 17, 18, 20, 15, 15]3~7The index of the minimum value at the position is 7,最小值为:17,The result of this sorting:[6, 9, 13, 15, 18, 20, 15, 17]4~7The index of the minimum value at the position is 6,最小值为:18,The result of this sorting:[6, 9, 13, 15, 15, 20, 18, 17]5~7The index of the minimum value at the position is 7,最小值为:20,The result of this sorting:[6, 9, 13, 15, 15, 17, 18, 20]6~7The index of the minimum value at the position is 6,最小值为:18,The result of this sorting:[6, 9, 13, 15, 15, 17, 18, 20]
复制代码

Summarize the process of selection sort:

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 2 ) + b N + c ( a b c 都是常数 ) 总的常数操作数量 = a*(N²) + b*N + c (a、b、c都是常数)

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

插入排序

这个算法比较好理解,Imagine playing poker on a regular basis,It is natural for us to compare a card with the cards in our hand,and insert it in the proper position.

Playing cards insertion sort.png

过程:

  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]这个数不停向左移动,一直移动到左边的数字不再比自己大,停止移动.

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

如果某个算法流程的复杂程度会根据数据状况的不同而不同,Then it must be followed 最差情况 来估计.

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

所以有:

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

So the time complexity of Insertion Sort is O ( N 2 ) 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位置往前看,Until the number on the left is no larger than himself,Stop looking left
        for (int i = 1; i < arr.length; i++) {
            //j=i表示从i位置开始,j--means looking forward
            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 + "位置往前看,直到左边的数不比自己大,this result:" + Arrays.toString(arr));
        }
    }
}
复制代码

运行结果:

1位置往前看,直到左边的数不比自己大,this result:[15, 18, 13, 17, 6, 20, 15, 9]2位置往前看,直到左边的数不比自己大,this result:[13, 15, 18, 17, 6, 20, 15, 9]3位置往前看,直到左边的数不比自己大,this result:[13, 15, 17, 18, 6, 20, 15, 9]4位置往前看,直到左边的数不比自己大,this result:[6, 13, 15, 17, 18, 20, 15, 9]5位置往前看,直到左边的数不比自己大,this result:[6, 13, 15, 17, 18, 20, 15, 9]6位置往前看,直到左边的数不比自己大,this result:[6, 13, 15, 15, 17, 18, 20, 9]7位置往前看,直到左边的数不比自己大,this result:[6, 9, 13, 15, 15, 17, 18, 20]
复制代码

点个赞再走吧~

copyright notice
author[line barrier],Please bring the original link to reprint, thank you.
https://en.cdmana.com/2022/218/202208061959195168.html

Random recommended