直播前准备

算法实战课
查找与排序算法

霍格沃兹测试开发

ceshiren.com

目录

• 学习价值
• 知识点梳理
• 成果展示
• 实战练习

学习价值

• 是通过大厂面试的必备硬核能力

  • 算法能力能够准确辨别一个程序员的技术功底是否扎实
  • 算法能力是发掘程序员的学习能力与成长潜力的关键手段
  • 算法能力能够协助判断程序员在面对新问题时，分析并解决问题的能力
  • 算法能力是设计一个高性能系统的必备基础

• 是升职加薪必备的基础能力

• 是成为高阶测试开发工程师的必经之路

招聘需求

• 阿里巴巴招聘需求:

  • 薪资: 20K+
  • 要求: 具备很强的逻辑思维能力和较高的分析、处理问题的能力

• 字节测试开发实习生招聘需求：

  • 具备较强的逻辑思维能力、沟通协作能力和学习能力

知识点梳理

算法学习技巧

成果展示

• 掌握面试常考的查找算法。
  • 顺序查找
  • 二分查找
• 掌握面试常考的排序算法。
  • 冒泡排序

实战一目标

• 掌握顺序查找。
• 掌握二分查找。

相关知识点

顺序查找

顺序查找

课堂练习

第一次刷题

• 统计位数为偶数的数字

• 统计有序矩阵中的负数

【二分查找】

二分查找简介

• 二分查找是一种在有序数组中查找元素的算法。
• 将数组分成两部分，判断目标元素可能在哪一部分。
• 直到找到目标元素或确定目标元素不存在于数组中。

二分查找实现思路

1. 确定查找范围。
2. 获取中间元素。
3. 如果猜的数字小了，就修改最小值。
4. 如果猜的数字大了，就修改最大值。
5. 如果猜中了，则返回下标。
6. 重复以上的过程直到找到目标元素或确定目标元素不存在于数组中。

课堂练习

1. 根据下面函数要求编写单元测试用例。
2. 编写一段函数，要求在一个有序列表中查找目标元素，并返回目标元素的索引值，若不存在返回-1，尽量使用二分查找法实现。
3. 计算这段代码的时间复杂度是多少。

二分查找的实现（Python）

def binary_search(nums, target: int) -> int:
    """
    在有序数组arr中查找目标元素target
    返回目标元素的索引，如果目标元素不存在，则返回-1
    """
    # low 和 high 用于跟踪要在其中查找的列表的部分
    low  = 0
    high = len(nums)-1
    
    while low <= high:
        mid = (low + high) // 2
        guess = nums[mid]
        if guess == target:
            return mid
        # 猜的数字小了。
        elif guess < target:
            low = mid - 1
        # 猜的数字大了。
        else:
            high = mid + 1
    # 没有制定的元素。
    return -1

# 功能和顺序查找一致，但是效率高很多。
def test_binary_search_null():
    assert binary_search([1, 3, 4, 5, 7, 8], "a") == -1
# 存在返回对应数据的索引
def test_binary_search():
    assert binary_search([1, 3, 4, 5, 7, 8], 1) == 0

二分查找的实现（Java）

// 二分查找的实现
public class BinarySearch {
    public int binarySearch(int[] nums, int target) {
        int minIndex = 0;
        int maxIndex = nums.length - 1;
        while (minIndex <= maxIndex) {
            int mid = (minIndex + maxIndex) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                maxIndex = mid - 1;
            } else {
                minIndex = mid + 1;
            }
        }
        return -1;
    }

}

// 测试用例
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.*;
class BinarySearchTest {
    @Test
    void binarySearch() {
        BinarySearch bb = new BinarySearch();

        int[] arr = {11, 22, 33, 44, 55, 66, 77};
        int[] arr2 = {11, 22, 33, 44, 55, 66, 77, 88};
        assert bb.binarySearch(arr, 33) == 2;
        // 不存在的场景
        assert bb.binarySearch(arr, 99) == -1;
        // 边界值
        assert bb.binarySearch(arr, 11) == 0;
        assert bb.binarySearch(arr, 77) == 6;
        assert bb.binarySearch(arr2, 88) == 7;
    }
}

实战二目标

• 掌握常见面试题冒泡排序的实现。
• 掌握常见面试题快速排序的实现。
  • 递归算法。

相关知识点

【冒泡排序】

冒泡排序简介

• 冒泡排序是一种基础的排序算法。
• 名称由来：越大的元素会不断地往上“冒泡”，就像水底的气泡逐渐向上冒。
• 基本思想：比较相邻元素的大小，将最大值逐个移动到最上边，即序列的末尾。同时不断缩小序列的范围。

冒泡排序的优点

• 冒泡排序是最经典、最基础的排序算法之一。
• 逻辑简单。
• 空间复杂度低，运行稳定。

冒泡排序的应用场景

冒泡排序虽然简单，但其具有一定的应用场景。对于小规模的序列，冒泡排序可以快速地实现排序，并且由于其基本操作是交换相邻元素，因此它也是一种稳定的排序算法。此外，冒泡排序也有助于理解排序算法的基本原理和思想，是学习排序算法的入门内容。

冒泡排序的实现思路

1. 比较相邻的两个元素。如果第一个比第二个大，就交换它们的位置。
2. 对每一对相邻的元素做同样的操作，从开始的第一对到结尾的最后一对。这一步结束后，最后的元素应该是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 重复步骤 1~3，直到排序完成。

课堂练习

1. 画出冒泡排序的实现过程。
2. 根据下面的函数要求编写单元测试用例。
3. 给定一个无序列表。通过冒泡排序的方式，将其从小到大，升序排列。

冒泡排序的实现(Python)

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        print(f"第{i}轮遍历")
        for j in range(n - i - 1):
            print(f"===第{j}轮比较排序===")  
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

def test_bubble_sort():
    assert bubble_sort([5,1,3,2,6]) == [1,2,3,5,6]

冒泡排序的实现(Java)

// 冒泡排序的实现
public class Sort {

    public int[] bubbleSort(int[] originList) {
        for (int j = 0; j < originList.length - 1; j++) {
            for (int i = 0; i < originList.length - 1; i++) {
                if (originList[i] > originList[i + 1]) {
                    int tmp = originList[i];
                    originList[i] = originList[i + 1];
                    originList[i + 1] = tmp;
                }
            }
        }
        System.out.println(Arrays.toString(originList));
        return originList;
    }

}

// 测试用例
import org.junit.jupiter.api.BeforeAll;
import org.junit.jupiter.api.Test;
import java.util.Arrays;
import static org.junit.jupiter.api.Assertions.*;

class SortTest {
    static Sort sort;
    @BeforeAll
    static void setUp(){
        sort = new Sort();
    }
    @Test
    void bubbleSort() {
        int[] arr = {5, 2, 9, 8, 1, 3, 6};
        int[] arr2 = {5, 2, 9, 8, 1, 3, 6};
        Arrays.sort(arr2);
        sort.bubbleSort(arr);
        assertEquals(Arrays.toString(arr), Arrays.toString(arr2));
    }
}

【递归算法】

思考

• 实现一个一个正整数的阶乘（n!=1×2×3×…×(n-1)×n）。
• 看起来代码和数学公式并没有一个清晰的对应关系，是否有看起来过程更清晰的表达方式？

# Python 版本
def factorial_iterative(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

// Java版本
public class Recursion {

    public int factorial(int n) {
        int result = 1;
        for (int i = 1; i <= n; i++) {
            result = result * i;
        }
        return result;
    }

}

什么是递归算法

• 递归算法是一种解决问题的方法，通过将问题分解为规模更小的子问题，再逐个解决子问题，最终达到解决整个问题的目的。

什么情况可以使用递归 ？

1. 一个问题可以拆分成子问题。
2. 这些问题求解思路相同，数据规模不同。
3. 拥有明确的终止条件。

• 数学公式：求阶乘、斐波那契数列。
• 二分查找。
• 快速排序。
• 二叉树的遍历。

递归算法组成部分

• 基线条件：函数不再调用自己。
• 递归条件：函数调用自己。

递归题目-求阶乘

一个正整数的阶乘（factorial）是所有小于及等于该数的正整数的积，并且0的阶乘为1。自然数n的阶乘写作n!。即为n!=1×2×3×...×(n-1)×n。

解题思路

• 递归条件：n*(n-1)
• 基线条件：n<=1

# Python 版本的实现
def factorial_recursive(n):
    if n == 0 or n == 1:
        return 1
    else:
        return n * factorial_recursive(n - 1)

// Java版本的实现
public class Recursion {
    public int factorial_recursive(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }
        return n * factorial_recursive(n - 1);
    }
}

分而治之（D&C）

1. 找出基线条件。
2. 不断将问题分解，直到符合基线条件。

分治法-解决数组元素相加

• 使用递归解决数组相加的问题：
  1. 找出基线条件：数组为一个空数组，或只有一个元素。
  2. 不断将问题分解，直到符合基线条件：将数组不停地减小，直到符合基线条件为止。

课堂练习

1. 编写一个递归函数来计算列表包含的元素数。
2. 通过递归找到列表中最大的数字。
3. 通过递归的方式实现二分查找算法。

答案(Java)

public class Recursion {
//    通过递归找到列表中最大的数字。
    public int getSum(int [] nums, int sum, int currentIndex){
        if (currentIndex==nums.length){
            return sum;
        }
        sum += nums[currentIndex];
        currentIndex += 1;
        return getSum(nums, sum, currentIndex);
    }
//    通过递归找到列表中最大的数字。
    public int getMax(int [] nums, int maxData, int currentIndex){
        if (currentIndex==nums.length){
            return maxData;
        }
        if (nums[currentIndex] > maxData){
            maxData = nums[currentIndex];
        }
        currentIndex += 1;
        return getMax(nums, maxData, currentIndex);
    }
    // 递归版本的二分查找
    public int recurisonBinarySearch(int [] nums, int target ,int minIndex , int maxIndex, int mid){
        mid = (minIndex+maxIndex)/2;
        if (nums[mid] == target){
            return mid;
        }
        if (minIndex>maxIndex){
            return -1;
        }
        if (nums[mid]>target) {
            maxIndex = mid - 1;
        }else {
            minIndex = mid + 1;
        }
        return recurisonBinarySearch(nums, target, minIndex, maxIndex, mid);
    }
}

// 测试用例
class RecursionTest {
    static Recursion recursion;
    @BeforeAll
    static void setupClass(){
        recursion = new Recursion();
    }

    @Test
    void getSum() {
        int [] xx = {1,2,3,4,5};
        int [] xx2 = {1,2,3,4,5,6,7};
        assertEquals(recursion.getSum(xx, 0, 0) , 15);
        assertEquals(recursion.getSum(xx2, 0, 0) , 28);
    }

    @Test
    void getMax() {
        int [] xx = {1,2,3,4,5};
        int [] xx2 = {1,2,3,4,5,6,7};
        assertEquals(recursion.getMax(xx, xx[0], 0) , 5);
        assertEquals(recursion.getMax(xx2, xx2[0], 0) , 7);
    }

    @Test
    void recurisonBinarySearch() {

        int[] arr = {11, 22, 33, 44, 55, 66, 77};
        int[] arr2 = {11, 22, 33, 44, 55, 66, 77, 88};
        assert recursion.recurisonBinarySearch(arr, 33, 0, arr.length - 1, 0) == 2;
        // 不存在的场景
        assert recursion.recurisonBinarySearch(arr, 99, 0, arr.length- 1, 0) == -1;
        // 边界值
        assert recursion.recurisonBinarySearch(arr, 11, 0, arr.length- 1, 0) == 0;
        assert recursion.recurisonBinarySearch(arr, 77, 0, arr.length- 1, 0) == 6;
        assert recursion.recurisonBinarySearch(arr2, 88, 0, arr2.length- 1, 0) == 7;
    }
}

答案(Python)

# 1. 编写一个递归函数来计算列表包含的元素数。
def count_item(data_list, count):
    if data_list == []:
        return count
    data_list.pop(0)
    count += 1
    # 递归条件
    return count_item(data_list, count)



def test_count_item():
    assert count_item([1,2,3,4,5], 0) == 5

# 1. 通过递归找到列表中最大的数字。
def find_max_number(data_list, max_data):
    # 基线条件
    if data_list == []:
        return max_data
    delete_item = data_list.pop(0)
    if max_data < delete_item:
        max_data = delete_item
    # 递归条件
    return find_max_number(data_list, max_data)

def test_find_max_number():
    data_list = [1,2,3,4,5]
    assert find_max_number(data_list, data_list[0]) == 5

# 1. 通过递归的方式实现二分查找算法。
def binary_search(data_list, low, high, target):
    # 基线条件：函数不再调用自己。
    if low>high:
        return -1
    # 基线条件：获取到中间元素，停止递归，返回中间值索引
    mid = (low+high)//2
    if data_list[mid] == target:
        return mid
    # 递归条件：目标值> 中间值
    if target> data_list[mid]:
        low = mid +1
    # 递归条件：目标值< 中间值
    else:
        high= mid -1
    return binary_search(data_list, low, high, target)

def test_binary_search():
    assert binary_search([1,2,3,4,5,6,7,8], 5) == 4
    assert binary_search([1,2,3,4,5], 1) == 0
    assert binary_search([1,2,3,4,5], 9) == -1

【快速排序】

什么是快速排序

无论是选择排序还是冒泡排序，其时间复杂度都达到了 O(n²)。不适合处理大量数据的排序。

• 优雅高效的排序算法——快速排序，可以解决这个问题。
• 快速排序的实现采用了分治的思想。

快速排序的优点

1. 时间复杂度低：O(nlogn)的时间内完成对序列的排序，适用于处理大规模数据。
2. 快速排序还是许多其他排序算法的基础，例如归并排序和堆排序等。

快速排序的应用场景

• 许多内置排序算法基于快排实现快改良。
  1. C++的std::sort函数: 快速排序的改进版本。
  2. Java的Arrays.sort方法: 快速排序的改进版本。
  3. JavaScript的Array.prototype.sort方法。
• 排序算法教学必学基础知识。
• 数据库排序：快速排序常被用于数据库中的排序操作。

快速排序的实现思路

• 找出快排的基线条件。
• 不断将问题分解，直到符合基线条件。
  1. 从数组选一个元素，通常这个元素为基准值。
  2. 找到比基准值大的元素和比基准值小的元素，进行分区。
  3. 对子数组进行排序。

找出快排的基线条件

• 当数组为空，或者只包含一个元素的时候，递归结束。

if len(array)<2:
    return array

不断将问题分解，直到符合基线条件

1. 找基准：从数组选一个元素，通常这个元素为基准值。
2. 分区：找到比基准值大的元素和比基准值小的元素，进行分区。
3. 递归：此时两个子数组是一个无序状态，如何对子数组进行排序呢？重复以上的操作即可。

课堂练习

1. 画出快速排序的实现过程。
2. 根据下面的函数要求编写单元测试用例。
3. 给定一个无序列表。通过快速排序的方式，将其从小到大，升序排列。

快速排序的实现(Java)

import java.util.Arrays;
public class Sort {
    // 交换逻辑
    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
  // 分区
    private int partition(int[] arr, int low, int high) {
        // 基准值
        int pivot = arr[low];
        // 初始化分区左边界的指针
        int i = low;
        // 在子数组中进行划分
        for (int j = low+1; j <= high; j++) {
            // 如果当前元素小于或等于基准元素，则将其交换到较小元素的位置
            if (arr[j] <= pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        // 将基准元素交换到较小元素的右边
        swap(arr, i , low);
        // 返回基准元素的索引
        return i;
    }
    public void quickSort(int[] arr, int low, int high) {
        if (arr == null || arr.length == 0) {
            return;
        }
        if (low < high) {
            // 选择一个基准元素并对数组进行划分
            int pivotIndex = partition(arr, low, high);
            // 对基准元素左边的子数组进行递归排序
            quickSort(arr, low, pivotIndex - 1);
            // 对基准元素右边的子数组进行递归排序
            quickSort(arr, pivotIndex + 1, high);
        }
    }

}

// 测试用例
import org.junit.jupiter.api.BeforeAll;
import org.junit.jupiter.api.Test;

import java.util.Arrays;
import java.util.List;

import static org.junit.jupiter.api.Assertions.*;

class SortTest {
    static Sort sort;

    @BeforeAll
    static void setUp(){
        sort = new Sort();
    }

    @Test
    void quickSort() {
        int[] arr = {5, 2, 9, 8, 1, 3, 6};
        int[] arr2 = {5, 2, 9, 8, 1, 3, 6};
        Arrays.sort(arr2);
        sort.quickSort(arr, 0 ,arr.length-1);
        assertEquals(Arrays.toString(arr), Arrays.toString(arr2));
    }

}

快速排序的实现(Python)

def quick_sort(origin_list):
    # 基准条件： 长度为1 或者 长度为0
    if len(origin_list) == 1 or len(origin_list) == 0:
        return origin_list
    left = []
    right = []
    # 1. 遍历数组，比它大的往右边放，比它小的，往左边放。
    pivot = origin_list[0]
    for i in range(1, len(origin_list)):
        if origin_list[i] > pivot:
            right.append(origin_list[i])
        elif origin_list[i]< pivot:
            left.append(origin_list[i])
    # 2. 递归处理左、 右数组，最后拼接。
    return quick_sort(left) +[pivot]+ quick_sort(right)

def test_quick_sort():
    assert quick_sort([5,4,3,2,1]) == [1,2,3,4,5]

总结