算法 - Java版 - 《算法（第4版）学习》 - 补充中2022

文章目录

前言一、程序所带来的运算复杂度

时间复杂度

*O*(1)*O*(log*N*)*O*(*N*)*O*(*N* log *N*)*O*(*N*²)*O*(2^*N*)*O*(*N*!)总结 空间复杂度 二、排序

1 工具类sort方法2 冒泡排序3 选择排序4 希尔排序5 归并排序6 快速排序7 优先队列8 堆排序 三、查找四、图五、字符串六、待定总结

前言

本人的算法菜到扣脚了，因为写LeeCode写不下去了，所以来学学算法基础

文章目录
《算法（第4版）—— Java》

放上一个查看运行时间的万能算法模板先

public class DemoApplication {
    public static void main(String[] args) {
        // 开始时间
        long startTime = System.currentTimeMillis();

        // ...go go go

        // 结束时间
        long endTime = System.currentTimeMillis();
        long runTime = (endTime - startTime) / 1000;
        System.out.println("程序运行时长 = " + runTime + "秒");
    }
}

一、程序所带来的运算复杂度

我认为主要是讲述在某些场景下的数据结构的一个效率问题，主要是从时间/空间复杂度展开，一般分为最好、最坏以及平均情况

以下摘录LeeCode《图解算法数据结构》—— Krahets

时间复杂度

根据从小到大排列，常见的算法时间复杂度主要有

O(1) < O(logN) < O(N) < O(NlogN) < O(N2) < O(2N) < O(N!)

简单来说，使用算法进行问题解决的时候，输入的数据量恒定为 N，我们要操作 y 次才能得到我们最终想要的结果

最佳情况 Ω(1) ： nums = [7, a, b, c, …] ，即当数组首个数字为 77 时，无论 nums 有多少元素，线性查找的循环次数都为 11 次；最差情况 O(N) ： nums = [a, b, c, …] 且 nums 中所有数字都不为 77 ，此时线性查找会遍历整个数组，循环 NN 次；平均情况 Θ ： 需要考虑输入数据的分布情况，计算所有数据情况下的平均时间复杂度；例如本题目，需要考虑数组长度、数组元素的取值范围等； O(1)

常数阶，无论变量是多大，程序产生结果的运行时间都跟输入的变量没有关系

public static int compute(int x){
    int i = 1;
    // ...各种霹雳帕拉的操作
    return i;
}

O(logN)

对数阶，对数阶与指数阶相反，对数阶是 “每轮排除一半的情况” 。对数阶常出现于「二分法」、「分治」等算法中

O(N)

线性阶，循环的次数跟输入的变量成线性正比，输入的数据越大，程序运行的时间越久

public static int compute(int x) {
    int count = 0;
    for (int i = 0; i < x; i++) {
        count++;
    }
    return count;
}

O(N log N)

线性对数，代码中出现两层循环相互独立，第一层和第二层时间复杂度分别为O(logN) 和O(N) ，则总体时间复杂度为O(N log N) 。

O(N²)

平方阶，两层嵌套循环，输入的数据将导致结果运行时间是平方时

public static int compute(int x) {
    int count = 0;
    for (int i = 0; i < x; i++) {
        for (int j = 0; j < x; j++) {
            count++;
        }
    }
    return count;
}

O(2^N)

指数阶，常见于递归

public static int compute(int x) {
    // 实际执行的计算操作
    x += 10;
    // 递归条件判断
    if (x < 100) {
        return compute(x);
    } else {
        return x;
    }
}

O(N!)

阶乘阶，也是递归，对应数学上常见的 “全排列”，即给定 NN 个互不重复的元素，求其所有可能的排列方案

总结

空间复杂度

空间复杂度涉及的空间类型有

输入空间： 存储输入数据所需的空间大小；初始数据大小暂存空间： 算法运行过程中，存储所有中间变量和对象等数据所需的空间大小；数据计算时占用空间输出空间： 算法运行返回时，存储输出数据所需的空间大小；最终结果大小

根据从小到大排列，常见的算法空间复杂度有

O(1) < O(logN) < O(N) < O(N2) < O(2N)

​ 但是目前我们都是考虑以空间换取时间，因为目前的存储技术来说存储空间是非常充裕的，当然也是因为少不了各种压缩算法的横空出世。

二、排序 1 工具类sort方法

​ 最简单粗暴的一种，数据之间的直接比较排序，如果是对象数据类型则需要通过实现 Comparable 或 Comparator 接口完成数据间的比较，实现后可以通过数组工具类或者集合工具类中的sort方法进行排序。

Comparable - 在数据对象中实现该接口，可在排序时通过该接口方法逻辑进行排序。

import lombok.AllArgsConstructor;
import lombok.Data;
import java.util.ArrayList;
import java.util.Collections;
import java.util.function.Consumer;


public class DemoApplication {
    public static void main(String[] args) {
        // 开始时间
        long startTime = System.currentTimeMillis();
        go();
        // 结束时间
        long endTime = System.currentTimeMillis();
        long runTime = (endTime - startTime) / 1000;
        System.out.println("程序运行时长 = " + runTime + "秒");
    }

    public static void go() {
        // 基本数据
        ArrayList arrayList = new ArrayList();
        arrayList.add(new Person("1", 11));
        arrayList.add(new Person("4", 14));
        arrayList.add(new Person("5", 15));
        arrayList.add(new Person("2", 12));
        arrayList.add(new Person("6", 16));
        arrayList.add(new Person("3", 13));
        // 排序
        Collections.sort(arrayList);
        // 遍历
        arrayList.forEach(new Consumer() {
            @Override
            public void accept(Person person) {
                System.out.println(person);
            }
        });
    }
}

@Data
@AllArgsConstructor
class Person implements Comparable {
    private String name;
    private Integer age;

    @Override
    public int compareTo(Person o) {
        if (this.age.equals(o.age)) {
            return 0;
        } else if (this.age > o.age) {
            return 1;
        } else if (this.age < o.age) {
            return -1;
        }
        return 0;
    }
}

Comparator - 如果在数据对象中没有实现上述接口，且需要使用集合进行排序的情况下，则需要在sort方法中作为形参实现。

import lombok.AllArgsConstructor;
import lombok.Data;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.function.Consumer;


public class DemoApplication {
    public static void main(String[] args) {
        // 开始时间
        long startTime = System.currentTimeMillis();
        go();
        // 结束时间
        long endTime = System.currentTimeMillis();
        long runTime = (endTime - startTime) / 1000;
        System.out.println("程序运行时长 = " + runTime + "秒");
    }

    public static void go() {
        // 基本数据
        ArrayList arrayList = new ArrayList();
        arrayList.add(new Person("1", 11));
        arrayList.add(new Person("4", 14));
        arrayList.add(new Person("5", 15));
        arrayList.add(new Person("2", 12));
        arrayList.add(new Person("6", 16));
        arrayList.add(new Person("3", 13));
        // 排序
        Collections.sort(arrayList, new Comparator() {
            @Override
            public int compare(Person o1, Person o2) {
                if (o2.getAge().equals(o1.getAge())) {
                    return 0;
                } else if (o2.getAge() > o1.getAge()) {
                    return 1;
                } else if (o2.getAge() < o1.getAge()) {
                    return -1;
                }
                return 0;
            }
        });
        // 遍历
        arrayList.forEach(new Consumer() {
            @Override
            public void accept(Person person) {
                System.out.println(person);
            }
        });
    }
}

@Data
@AllArgsConstructor
class Person {
    private String name;
    private Integer age;
}

2 冒泡排序

数据循环过程中依次比较两个相邻的数据，数据小的一方放在左边，大的一方放在右边，代码如下

public static void bubbleSort(int arr[]) {
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

但是基本用不上，因为时间复杂度太高了

3 选择排序

大概的流程是

找到数组中最小的元素把这个元素和数组的第一个元素换位重复上面的过程，直到完成整个数组的排序

大概代码如下

public class DemoApplication {
    public static void main(String[] args) {
        // 开始时间
        long startTime = System.currentTimeMillis();
        go();
        // 结束时间
        long endTime = System.currentTimeMillis();
        long runTime = (endTime - startTime) / 1000;
        System.out.println("程序运行时长 = " + runTime + "秒");
    }

    public static void go() {
        int[] arr = new int[]{3, 5, 1, 4, 7, 9, 2};
        for (int i : comp(arr)) {
            System.out.println(i);
        }
    }

    public static int[] comp(int[] arr) {
        // 循环
        for (int i = 0; i < arr.length; i++) {
            // 嵌套循环 在每次循环的数组中找到最小元素
            for (int j = i; j < arr.length; j++) {
                // 进行比较交换
                if (arr[i] > arr[j]) {
                    int tempNum = arr[i];
                    arr[i] = arr[j];
                    arr[j] = tempNum;
                }
            }
        }
        return arr;
    }
}

4 希尔排序

引用文章
希尔排序 | 菜鸟教程 (runoob.com)

第一步：将数组内数据间隔对半，两两数据为一组，提前进行组内排序

第二步：以此类推，第二次将间隔再次减半，再次进行一次组内排序，直到最终间隔为1时停止

public class DemoApplication {
    public static void main(String[] args) {
        // 开始时间
        long startTime = System.currentTimeMillis();
        go();
        // 结束时间
        long endTime = System.currentTimeMillis();
        long runTime = (endTime - startTime) / 1000;
        System.out.println("程序运行时长 = " + runTime + "秒");
    }

    
    public static void go() {
        int[] array = {49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 1};
        System.out.println("排序之前：");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        // 希尔排序
        int size = array.length;
        while (true) {
            // 增量每次减半
            size /= 2;
            for (int i = 0; i < size; i++) {
                // 这个循环里其实就是一个插入排序
                for (int j = i + size; j < array.length; j += size) {
                    int k = j - size;
                    while (k >= 0 && array[k] > array[k + size]) {
                        int temp = array[k];
                        array[k] = array[k + size];
                        array[k + size] = temp;
                        k -= size;
                    }
                }
            }
            if (size == 1) {
                break;
            }
        }
        System.out.println();
        System.out.println("排序之后：");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
}

5 归并排序

引用文章
图解排序算法(四)之归并排序 - dreamcatcher-cx - 博客园 (cnblogs.com)

​ 简单来说需求就是，将两个有序的数组合并成一个更大的有序数组，所以叫它归并排序，其核心是采用分治策略，下面这幅图是将两个有序的子数组先合并为一个，利用双指针进行比较排序。

但是我想试试另外一种玩法，不合并的前提下进行比较，但是实际原理上都差不多

public class DemoApplication {
    public static void main(String[] args) {
        // 开始时间
        long startTime = System.currentTimeMillis();
        go();
        // 结束时间
        long endTime = System.currentTimeMillis();
        long runTime = (endTime - startTime) / 1000;
        System.out.println("程序运行时长 = " + runTime + "秒");
    }

    public static void go() {
        // 两个有序的原数组
        int[] arrA = new int[]{1, 3, 5, 7, 9, 12, 14, 16};
        int[] arrB = new int[]{2, 4, 6, 8, 10, 11, 13, 15, 17, 18};
        // length
        int sizeA = arrA.length;
        int sizeB = arrB.length;
        int[] arrC = new int[sizeA + sizeB];

        // 比较两个数组的长度
        int max = 0;
        int min = 0;
        if (sizeA > sizeB) {
            max = sizeA;
            min = sizeB;
        }
        if (sizeA < sizeB) {
            max = sizeB;
            min = sizeA;
        }

        // 指针指向
        int arrA_pointer = 0;
        int arrB_pointer = 0;

        // 开始排序
        for (int i = 0; i < max + min; i++) {

            if (arrA_pointer == min) {
                // 最小的那个数组已经达到边界了 把剩下的元素扔过去
                arrC[i] = arrB[arrB_pointer];
                arrB_pointer++;
                continue;
            }

            // 元素比较 暂不考虑相等的情况
            if (arrA[arrA_pointer] > arrB[arrB_pointer]) {
                arrC[i] = arrB[arrB_pointer];
                arrB_pointer++;
            } else if (arrA[arrA_pointer] < arrB[arrB_pointer]) {
                arrC[i] = arrA[arrA_pointer];
                arrA_pointer++;
            }

        }

        // 遍历查看结果
        for (int i : arrC) {
            System.out.print(i + " ");
        }
        System.out.println("________");
    }
}

6 快速排序

​ 快速排序是C. A. R. Hoare在1962年提出的一种排序算法，它的核心思想就是分治处理，实际上，它与归并排序是一个互补的关系，通过两个有序的子序列进行合并排序，后面经过后人的不断改进也衍生了很多种不同类的快速排序，下面写一个最具代表性的三向切分的快速排序。

​ 我先把JVM的内存提升一下…刚才十亿数据差点把我给炸没了

-Xms4240m -Xmx12288m

首先整一点数据出来

import java.util.Random;

public class DeadData {

    
    public static int[] memoryData(int size, int rangeSize) {
        int x = 0;
        int[] resultArrays = new int[size];
        while (x < size) {
            int tempNum = new Random().nextInt(rangeSize) + 1;
            resultArrays[x] = tempNum;
            x++;
        }
        System.out.println("resultArrays.length = " + resultArrays.length);
        return resultArrays;
    }
}

快速排序的核心代码

public class QuickSort {

    
    public static void sorted(int[] data, int leftPoint, int rightPoint) {
        // 如果左下标翻过了右下标 则退出递归
        if (leftPoint >= rightPoint) {
            return;
        }

        // 数据定义
        int value = data[leftPoint];
        int leftIndex = leftPoint;
        int rightIndex = rightPoint;
        int moveIndex = leftPoint + 1;

        // 循环条件：如果左边移动的指针没有越过右边移动的指针
        while (moveIndex <= rightIndex) {
            if (data[moveIndex] < value) {
                swap(data, moveIndex++, leftIndex++);
            } else if (data[moveIndex] > value) {
                swap(data, moveIndex, rightIndex--);
            } else {
                moveIndex++;
            }
        }

        // 递归
        sorted(data, leftPoint, leftIndex - 1);
        sorted(data, rightIndex + 1, rightPoint);
    }

    
    public static void swap(int[] data, int pointA, int pointB) {
        int tempNum = data[pointA];
        data[pointA] = data[pointB];
        data[pointB] = tempNum;
    }
}

接下来跑起来测试一下

import java.util.Arrays;

public class RunSortsDemo {
    public static void main(String[] args) {
        int[] intS1 = DeadData.memoryData(500000000, 1000000000);
        int[] intS2 = intS1.clone();
        B(intS2);
        A(intS1);
    }

    public static void A(int[] intS) {
        // 开始时间
        long startTime = System.currentTimeMillis();
        go(intS);
        // 结束时间
        long endTime = System.currentTimeMillis();
        long runTime = (endTime - startTime) / 1000;
        System.out.println("自己写的算法 执行时长 = " + runTime + "秒");
    }

    public static void B(int[] intS) {
        // 开始时间
        long startTime = System.currentTimeMillis();
        Arrays.sort(intS);
        // 结束时间
        long endTime = System.currentTimeMillis();
        long runTime = (endTime - startTime) / 1000;
        System.out.println("Arrays.sort 执行时长 = " + runTime + "秒");
    }

    
    public static void go(int[] arr) {
        QuickSort.sorted(arr, 0, arr.length - 1);
    }
}

我只能说，完败

resultArrays.length = 500000000
Arrays.sort 执行时长 = 38秒
自己写的算法 执行时长 = 56秒

本想挑战一下Arrays工具类的排序，万万是没想到啊

文章目录
快速排序算法_哔哩哔哩_bilibili

over

7 优先队列

文章目录
优先队列 PriorityQueue， 堆Heap「数据结构和算法8」 – TuringPlanet

​ 普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。通常采用堆数据结构来实现。

​ 优先级队列必须至少支持以下操作

push：插入一个新的元素pop：将优先级最高的元素弹出（删除）peek：查看优先级最高的值

​ 在优先队列中，由于元素被赋予了优先级，我们获取或者删除最大优先级的元素的时候时间复杂度仅仅需要O(1)，但是在插入元素的效率上，就跟链表一样需要不断迭代找到合适的位置，所以这个时间O(n)上就变慢了。

public class PriorityQueue {
    
    Node head = null;

    static class Node {
        
        int value;
        
        int priority;
        
        Node next;

        public Node(int value, int priority) {
            this.value = value;
            this.priority = priority;
        }
    }

    
    public void push(int value, int priority) {
        // 如果头节点为空 则用这个新来的元素暂当头子
        if (head == null) {
            head = new Node(value, priority);
            return;
        }

        // 两个对象引出：头节点和新的节点
        Node cur = head;
        Node newNode = new Node(value, priority);

        // 比较头节点和新节点的优先级
        if (head.priority < priority) {
            newNode.next = head;
            this.head = newNode;
        } else {
            while (cur.next != null && cur.next.priority > priority) {
                cur = cur.next;
            }
            newNode.next = cur.next;
            cur.next = newNode;
        }
    }

    
    public Node peek() {
        return head;
    }

    
    public Node pop() {
        if (head == null) {
            return null;
        }
        Node temp = head;
        head = head.next;
        return temp;
    }

    
    public boolean isEmpty() {
        return head == null;
    }
}

复杂度分析

push: O(n)pop: O(1)peek: O(1) 8 堆排序

​ 一种利用堆这种数据结构来排序的算法，非常的二叉树结构，也是优先队列后的一种衍生。

1

补充中

三、查找

1

1

1

四、图

1

五、字符串

1

1

六、待定

1

1

总结

提示：这里对文章进行总结：
例如：以上就是今天要讲的内容。