# homework_algorithm

**Repository Path**: flyinglkp/homework_algorithm

## Basic Information

- **Project Name**: homework_algorithm
- **Description**: 算法小分队，算法大作业地址
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2022-11-20
- **Last Updated**: 2022-11-24

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

## 1.多线程排序

### 1.1 排序图

![img.png](images/多线程排序.png)
>说明：将数组分为第一层的多个数据区间，利用多线程对每个区间内的数据进行排序，可使用任意排序算法；区间之间，因为已经是有序的数组，所以可以使用归并排序。

把每一个区内有序的数据结点入队，利用多线程对同层的两个相邻结点进行合并
![img.png](images/队列.png)

某一时刻优先级queue中结点，以及对应的线程池任务
![img_1.png](images/某一时刻队列和线程池任务.png)

### 1.2 数据区间结点对应的实体类和其关键字段
```java
class Node{
    // 层数
    int level;
    // 数据区间编号
    int id;
    // 数据区间最小索引
    int low;
    // 数据区间最大索引
    int high;
    // 待排序数组
    int[] array;
    // 与待排序数组等长的数组
    int[] aux;
}
```

### 1.3 流程
1. 对于一个数据个数超过100万的数组array，将数组划分成多个数据区间，区间个数满足2的次幂，对每个区间的id从1开始编号，设置层数level为1；
2. 利用多线程分别对第一层（level=1）每个区间内部的数据进行排序，可以选择任意排序算法，这里选择快速排序；
3. 排序后将所有数据区间node放入一个优先级阻塞队列queue，首先level越小优先级越高，其次id越小优先级越高；
4. 主线程每次从queue中取出2个或者3个结点，如果找到2个相邻结点继续使用多线程对它们进行归并排序，例如，在同一层中，对id=1和id=2的数据区间进行归并排序，对id=3和id=4的数据区间进行归并排序。同层且相邻的两个结点需要满足条件：① a.level = b.level ② a.id是奇数时，则a.id+1=b.id 或者 a.id是偶数时，则a.id-1=b.id
5. 每两个结点合并后产生一个新的数据区间结点，需要将level加1，id设置为排序结点中较大id的1/2；
6. 从queue中取出的数据结点满足low=0且high=array.length-1时，数组排序完毕。
说明：
> 使用优先级阻塞队列可充分利用CPU，无需等待上一层排序结束再开始本层的数据处理；

区间个数划分具体逻辑：
1. 数组个数没有达到100万的数组不进行数据区间，即只用一个数据区间；
2. 对数组按每个数据区间个数为100万进行划分，得到数据区间个数segmentCount；
3. 取CPU和segmentCount的较大值作为segmentCount；
4. 最终取大于segmentCount的最小2次幂作为segmentCount，例如原来是5取8，原来是10则取16。

### 1.4 简易代码
```
// 获取cpu个数
private final static int CPU_COUNT = Runtime.getRuntime().availableProcessors();
static ThreadPoolExecutor executor = new ThreadPoolExecutor(CPU_COUNT, CPU_COUNT,
        0L, TimeUnit.MILLISECONDS,
        new LinkedBlockingQueue<Runnable>());
private final static PriorityBlockingQueue<Node> priorityBlockQueue = new PriorityBlockingQueue<>();

/**
 * 多线程排序
 * @param array 待排序数组
 */
public static void multiThreadSort(int[] array) {

        int length = array.length;
        // 数据区间数
        int segment;

        // 初始设置每个数据区间的数据个数为100万
        int segmentNumberCount = 1000000;
        if (length < segmentNumberCount) {
           // 数组长度小于100万不进行分区
           segment = 1;
        } else {
            // 先按每个数据区间100万个数据来对原数组进行划分
            if (length % segmentNumberCount == 0) {
                segment = length / segmentNumberCount;
            } else {
                segment = length / segmentNumberCount + 1;
            }

            // 最终segment取CPU核数和segment较大的值
            segment = Math.max(segment, CPU_COUNT);
            // 取小于分区数的最大的2的次幂, 保证分区块是2的次幂. 比如输入10返回16
            segment = ceil2Power(segment);
            // segment = floor2Power(CPU_COUNT);
        }

        // 最终根据分区数设置区间内的数据个数
        segmentNumberCount = length/segment;
        System.out.println("数据分区数: " + segment);

        // 与原始数组同长度的额外数据, 两个数据区间的排序用.
        int[] aux = new int[length];
        // 数据区间编号
        int id = 1;
        int beginIndex = 0;
        // 前segment-1个区间加入到线程池排序
        for (int i = 0; i < segment-1; i++) {
            // 构造第一层的排序结点node
            Node node = new Node(1, id++, beginIndex,beginIndex + segmentNumberCount - 1, array, aux);
            executor.execute(new LevelOneSortWorker(node, priorityBlockQueue));
            beginIndex += segmentNumberCount;
        }

        // 最后一个数据进入线程池排序, 因为最后一个区间可能会大于设定的数据长度
        Node node = new Node(1, id, beginIndex,length - 1, array, aux);
        executor.execute(new LevelOneSortWorker(node, priorityBlockQueue));

        while (true) {
            try {
                Node a = priorityBlockQueue.take();
                // 判断数组排序是否结束
                if (a.low == 0 && a.high == length - 1) {
                    // 排序结束销毁线程池
                    executor.shutdown();
                    break;
                }
                Node b = priorityBlockQueue.take();

                // 同层之间排序
                // id为1和2进行合并, 3和4合并, 5和6合并...
                if (canMerge(a, b)) {
                    executor.submit(new MergeSortWorker(a, b, priorityBlockQueue));
                } else {
                    // 这里再取一个进行判断, 避免总是取到同一对无法合并的a和b
                    Node c = priorityBlockQueue.take();
                    if (canMerge(a, c)) {
                        executor.submit(new MergeSortWorker(a, c, priorityBlockQueue));
                        priorityBlockQueue.offer(b);
                    } else if (canMerge(b, c)) {
                        executor.submit(new MergeSortWorker(b, c, priorityBlockQueue));
                        priorityBlockQueue.offer(a);
                    } else {
                        priorityBlockQueue.offer(a);
                        priorityBlockQueue.offer(b);
                        priorityBlockQueue.offer(c);
                    }
                }
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }

```

### 1.5 多线程排序效果对比
电脑配置
1. Intel(R) Core(TM) i7-7500U CPU @ 2.70GHz   2.90 GHz
2. 内存：32.0 GB 
3. CPU：基准速度2.90GHZ、内核2个、逻辑处理器4个、虚拟化己启用、L1缓存128KB、L2缓存512KB、L3缓存4.0MB
4. Jdk：1.8.0_211

多线程排序方式：区间内快排，区间之间归并排序。

| 排序              | 数据量：100万<br/>数据区间：[-10000000, 10000000] | 数据量：200万<br/>数据区间：[-20000000, 20000000] | 数据量：500万<br/>数据区间：[-50000000, 50000000] | 数据量：1000万<br/>数据区间：[-100000000, 100000000] | 数据量：2000万<br/>数据区间：[-200000000, 200000000] | 数据量：5000万<br/>数据区间：[-500000000, 500000000] | 数据量：1亿<br/>数据区间：[-1000000000, 1000000000] |
|------------------|-----------------------------------------|-----------------------------------------|-----------------------------------------|--------------------------------------------|--------------------------------------------|--------------------------------------------|-------------------------------------------|
| 多线程排序        | 0.127s                                  | 0.198s                                  | 0.328s                                  | 0.664s | 1.667s                                     | 3.031s                                     | 6.508s                                    |
| 单线程快速排序    | 0.136s                                  | 0.261s                                  | 0.577s                                  | 1.199s | 2.519s                                     | 6.522s | 16.061s                                   |
| 单线程归并排序 | 0.166s                                  | 0.283s                                  | 0.733s                                  | 1.484s | 3.083s                                     | 8.89s |  17.228s                                         |

> 结论：区间内快排，区间之间归并排序，在这种多线程排序方式下，数据量在100万左右时，单线程和多线程排序的效率几乎无差别，当数据量达到1000万时，差距开始明显。

1亿条数据排序对比结果截图
<img src="images/多线程排序耗时对比.png" style="zoom:50%;" />

更详细的数据统计见echarts图：[排序耗时对比图.html](./line-stack.html)

排序耗时对比图
![img.png](images/排序耗时对比图.png)

### 1.6 时间复杂度分析
假设cpu核数是c，分区数是s，其中$s=ceil2\left(max\left(c, \frac{n}{1000000}\right)\right)$，ceil2指向上取最小的2的幂数；

因为有s个分区，并行度是c，理想情况下一次性可以执行c个分区的任务，所以第一层区间内排序的最好时间复杂度为$\frac{s}{c}O(\frac{n}{s}\log_{}{\frac{n}{s}} )$，最坏情况每个分区串行执行，共需要$sO\left(\frac{n}{s}\log_{}{\frac{n}{s}}\right)$；

虽然不同层的任务是可以并行执行的，但每一层区间合并的任务完全结束都必须依赖上一层的任务完全结束，所有层合并任务的总时间复杂度至少是$O\left(n\right)+O\left(\frac{n}{2}\right)+O\left(\frac{n}{4}\right)+...+O\left (\frac{n}{s/2}\right)$，最坏是$\log_{}{s}\times O(n)$；

综上时间总的时间复杂度依旧是$O\left(n\log_{}{n}\right)$。



<img src="images/排序level图.png" style="zoom: 25%;" />


### 1.7 文件说明

| 文件                   | 说明     |
|----------------------|--------|
| SortMain.java        | 排序执行主类 |
| SortUtils.java       | 排序工具类  |
| MultiThreadSort.java | 多线程排序  |

SortUtils.java排序工具类说明

| 主要方法               | 参数                                                 | 说明                    |
|--------------------|----------------------------------------------------|-----------------------|
| initArray          | (int min, int max, int num)                        | 生成[min, max]范围内的随机数数组 |
| swap               | (int[] array, int a, int b)                        | 交换数组下标为a和b的元素         |
| isEqual            | (int[] array, int[] dest)                          | 比较两个数组的元素是否完全相同       |
| quickSort          | (int[] array)                                      | 快速排序                  |
| quickSort          | (int[] array, int lowPtr, int highPtr)             | 数据区间的快速排序             |
| randomizedQuickSort | (int[] arrays)                                     | 随机快速排序                |
| isSorted           | (int[] arrays)                                     | 判断数组是否从小到大有序          |
| mergeSort          | (int[] arrays)                                     | 归并排序                  |
| mergeArray         | (int[] arr, int low, int mid, int high, int[] aux) | 合并两个有序数组区间            |
| selectSort         | (int[] arrays)                                     | 选择排序                  |
| display            |(int[] array)| 打印数组                  |
| radixSort            |(int[] array)| 基数排序                  |
| radixSort            |(int[] array, int low, int high)| 基数数组                  |
| shellSort            |(int[] array)| 希尔排序                  |

SortMain.java

| 主要方法                     | 说明                          |
|--------------------------|-----------------------------|
| main                     | 多线程排序、单线程快速排序和单线程归并排序单次排序速度比较 |
| test                     | 快速排序、归并排序、基数排序、希尔排序和选择排序速度比较 |
| compareQuickSortAndRadix | 单独比较快速排序和基数排序               |
| showMultiThreadSortTime  | 多线程排序、单线程快速排序和单线程归并排序单次排序速度比较 |

## 2.大数排序

由于需要对数值的范围在[-10^100,10^100]的数组排序排序，因此采用字符串数组存储数值。

两个大数字符串大小比较算法：
```
/**
 * 比较s[i]与目标k的大小
 * @param s 数组
 * @param i 索引i
 * @param k 目标字符换数字
 * @return true表示s[i] > k; false表示s[i]<k
 */

bool compare(string s[], int i, string k) {
    //s[i]>k,return true
    int a = s[i].length(), b = k.length();

    if (k[0] == '-' && s[i][0] != '-') {
        return true;
    } else if (s[i][0] != '-' && k[0] != '-') {
        if ((a > b) || (a == b && s[i] > k)) {
            return true;
        }
    } else if (s[i][0] == '-' && k[0] == '-') {
        if ((a < b) || (a == b && s[i] < k)) {
            return true;
        }
    }
    return false;
}
```

### 2.1 选择排序

#### 2.1.1排序原理

它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，继续放在起始位置直到未排序元素个数为0。

选择排序的实现步骤：

```
1>首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
2>再从剩余未排序元素中继续寻找最小（大）元素，然后放到未排序序列的起始位置。
3>重复第二步，直到所有元素均排序完毕。
```

#### 2.1.2简易代码

```
**
 * 选择排序
 * @param p 待排序数组
 * @param n 数组长度
 */

void selectSort(string p[], int n) {
    int i, j;
    // 记录最小数的索引
    int minIndex = 0;
    for (i = 0; i < n - 1; i++)//排序次数
    {
        minIndex = i;
        for (j = i + 1; j < n; j++) {
            if (compare(p, minIndex, p[j])) {
                minIndex = j;
            }
        }

        if (i != minIndex) {
            change(p[i], p[minIndex]);
        }
    }
}
```

### 2.2 归并排序

#### 2.2.1排序原理

它的工作原理是：该算法采用经典的分治策略，将问题分成一些小的问题然后递归求解将已有序的子序列合并，得到完全有序的序列。即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

归并排序的实现步骤：

```
1>将已有数列不断分离成两段长度基本相同（当已有数列长度是奇数时，则一半长一半短），直到分离成长度为 1 的 n 个数列（其实就是 n 个数）。
2>将数列两两合并，每次合并时进行比较和排序。
3>重复第二步，直到所有元素均排序完毕。
```

#### 2.2.2简易代码

```
// 合并

void merge(string arr[], string tempArr[], int left, int mid, int right) {
    // 标记左半区第一个未排序的元素
    int l_pos = left;
    // 标记右半区第一个未排序的元素
    int r_pos = mid + 1;
    // 临时数组元素的下标
    int pos = left;

    // 合并
    while (l_pos <= mid && r_pos <= right) {
        //if (arr[l_pos] < arr[r_pos])  // 左半区第一个剩余元素更小
        if (compare(arr, r_pos, arr[l_pos]))//s[i]>k
            // tempArr[pos++] = arr[l_pos++];
            tempArr[pos++].assign(arr[l_pos++]);
        else  // 右半区第一个剩余元素更小
            // tempArr[pos++] = arr[r_pos++];
            tempArr[pos++].assign(arr[r_pos++]);
    }

    // 合并左半区剩余的元素
    while (l_pos <= mid)
        //tempArr[pos++] = arr[l_pos++];
        tempArr[pos++].assign(arr[l_pos++]);

    // 合并右半区剩余的元素
    while (r_pos <= right)
        //tempArr[pos++] = arr[r_pos++];
        tempArr[pos++].assign(arr[r_pos++]);

    // 把临时数组中合并后的元素复制回原来的数组
    while (left <= right) {
        //arr[left] = tempArr[left];
        arr[left].assign(tempArr[left]);
        left++;
    }
}

// 归并排序

void msort(string arr[], string tempArr[], int left, int right) {
    // 如果只有一个元素，那么不需要继续划分
    // 只有一个元素的区域，本生就是有序的，只需要被归并即可
    if (left < right) {
        // 找中间点
        int mid = (left + right) >> 1;
        // 递归划分左半区
        msort(arr, tempArr, left, mid);
        // 递归划分右半区
        msort(arr, tempArr, mid + 1, right);
        // 合并已经排序的部分
        merge(arr, tempArr, left, mid, right);
    }
}

// 归并排序入口

void mergeSort(string arr[], int n) {

    // 分配一个辅助数组
    string *tempArr = new string[n];
    // 调用实际的归并排序
    msort(arr, tempArr, 0, n - 1);
}
```

### 2.3 快速排序

#### 2.3.1排序原理

它的工作原理是：每趟排序时选出一个基准值，然后将所有元素与该基准值比较，并按大小分成左右两堆，然后递归执行该过程，直到所有元素都完成排序。

快速排序的实现步骤：

```
1>先从数列中取出一个数作为基准数。
2>分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3>再对左右区间重复第二步，直到各区间只有一个数。
```

#### 2.3.2简易代码

```
/**
 * 快速排序
 * @param a 待排序数组
 * @param start 数据区间的最小索引
 * @param end 数据区间的最大索引
 */

void quickSortArray(string a[], int start, int end) {
    if (start >= end)
        return;
    int i = start, j = end;
    string k = a[start];
    while (i != j) {
        while (i < j && compare(a, j, k))
            j--;
        change(a[i], a[j]);
        while (i < j && !compare(a, i, k))
            i++;
        change(a[i], a[j]);
    }
    quickSortArray(a, start, i);
    quickSortArray(a, i + 1, end);
}


/**
 * 快速排序
 * @param a 待排序数组
 * @param length 数组长度
 */

void quickSort(string a[], int length) {
    quickSortArray(a, 0, length - 1);
}
```

### 2.4 希尔排序

#### 2.4.1排序原理

它的工作原理是：设待排序元素序列有n个元素，首先取一个整数step （小于序列元素总数）作为间隔，所有距离为step 的元素放在同一个逻辑数组中，在每一个逻辑数组中分别实行直接插入排序。然后缩小间隔step ，重复上述逻辑数组划分和排序工作。直到最后取step =1，将所有元素放在同一个数组中排序为止。

希尔排序的实现步骤：

```
1>选step ，划分逻辑分组，组内进行直接插入排序。
2>不断缩小step ，继续组内进行插入排序。
3>直到step =1，在包含所有元素的序列内进行直接插入排序。
```

#### 2.4.2简易代码

```
/**
 * 希尔排序
 * @param p 待排序数组
 * @param n 数组长度
 */
void shellSort(string p[], int n) {
    int step = 0;//步长
    string temp;//用来保存第二段数据
    int i, j;

    for (step = n / 2; step > 0; step /= 2) {
        for (i = step; i < n; i++) {

            temp.assign(p[i]);
            for (j = i - step; j >= 0 && compare(p, j, temp); j -= step) {
                //当满足条件时第一次j+step = i;后面的j+step = 上一次j的值
                p[j + step].assign(p[j]);
            }
            p[j + step].assign(temp);
        }
    }
}

```

### 2.5 基数排序

#### 2.5.1排序原理

它的工作原理是：​ 基数排序需要根据数组中所有元素的具体情况构建一个桶，并不断地重复将数组中元素放入桶中并不断拿出来的这个过程，根据其内部相关机制，最后这个数组就会变得有序。

希尔排序的实现步骤：

```
基数排序就是设置10个桶表示0~9，将要排序的元素先根据所有数的个位数分发到10个桶，然后按顺序重新返回数组，继续根据十位数分发。。。不断的分发到桶，然后顺序放回原来的数组，当所有位数都分发过了，数据就有序了
1>用20个桶解决负数问题，依次保存-9，-8，-7...负数的0, 正数的0, 1, 2, ... 9。
2>将要排序的元素先根据所有数的个位数分发到20个桶，按顺序重新返回数组。
3>继续根据十位数、百位数、千位数分发...，不断的分发到桶，然后顺序放回原来的数组，直到所有位数都分发过完成排序。
```

#### 2.5.2简易代码

```
/**
 * 基数排序
 * @param a 待排序数组
 * @param length 数组长度
 * @param m 最大位数
 */

void radixSort(string a[], int length, int m) {
    int size = 20;// 桶的个数 考虑正负号和每个数字是0-9,所以有20个桶, 依次存放-9,-8...,-1,负数的0,整数的0,1,2,3..9
    // 桶容器
    vector<vector<string>> vec;
    for (int i = 0; i < size; ++i) {
        vector<string> v;
        vec.push_back(v);
    }

    // d表示第几位开始比较, 1表示个位, 2表示十位...
    int d = 1;

    // 进行m轮循环
    // 依次对个位 十位.. 进行排序, 如果当前位不存在数字用0代替
    for (int i = 0; i < m; ++i) {
        // 用0初始化b
        for (int i = 0; i < vec.size(); ++i) {
            vec[i].clear();
        }
        for (int j = 0; j < length; ++j) {
            // 如果位数不够, 正数放入第11个桶(存储正数的0),负数放入第10个桶(存储负数的0)
            int x = 10;
            if (a[j][0] != '-') {
                // 正数的情况
                if (a[j].length() >= d) {
                    // 取出d位的char, 并转成数字.
                    x = 10 + a[j][a[j].length() - d] - 48;
                } else {
                    x = 10;
                }
            } else {
                // 负数的情况
                if (a[j].length() - 1 >= d) {
                    // 取出d位的char, 并转成数字.
                    x = 9 - (a[j][a[j].length() - d] - 48);
                } else {
                    x = 9;
                }
            }

            // 添加到桶中
            vec[x].push_back(a[j]);
        }

        // 排序, 依次把桶中的数据放回原数组
        int num = 0;
        for (int j = 0; j < vec.size(); ++j) {
            for (int k = 0; k < vec[j].size(); ++k) {
                a[num++].assign(vec[j][k]);
            }
        }
        // 准备进行下一位比较
        d++;
    }
}
```

### 2.6 运行结果

![输入图片说明](images/%E8%BF%90%E8%A1%8C%E7%BB%93%E6%9E%9C.png)

### 2.7 文件说明


| 文件                   | 说明     |
|----------------------|--------|
| bigdata_sort.cpp     | 大数排序 |


bigdata_sort.cpp大数排序函数说明

| 方法名      | 说明            |
|----------|---------------|
| void radixSort(string a[], int length, int m)                        | 基数排序          |
| bool compare(string s[], int i, string k)                        | 比较s[i]与目标k的大小 |
| void change(string &a, string &b);                          | 交换两个字符串       |
| string isSorted(string p[], int n)                                      | 判断数组p是否有序     |
| void shellSort(string p[], int n)             | 希尔排序          |
| void quickSortArray(string a[], int start, int end)                     | 快速排序实现        |
| void quickSort(string a[], int length)                                     | 快速排序          |
| void merge(string arr[], string tempArr[], int left, int mid, int right)                         | 归并排序          |
| void msort(string arr[], string tempArr[], int left, int right) | 划分过程          |
|void mergeSort(string arr[], int n)                                     | 归并排序入口        |
|void selectSort(string p[], int n)| 选择排序          |

## 3.五种排序算法排序时间对比
电脑配置
1. Intel(R) Core(TM) i7-7500U CPU @ 2.70GHz   2.90 GHz
2. 内存：32.0 GB
3. CPU：基准速度2.90GHZ、内核2个、逻辑处理器4个、虚拟化己启用、L1缓存128KB、L2缓存512KB、L3缓存4.0MB
4. Jdk：1.8.0_211


| 排序   | 数据量：1万<br/>数据区间：[-100000, 100000] | 数据量：5万<br/>数据区间：[-500000, 500000] | 数据量：10万<br/>数据区间：[-1000000, 1000000] | 数据量：50万<br/>数据区间：[-5000000, 5000000] |
|------|-----------------------------------|-----------------------------------|--------------------------------------|-----------------------------------------|
| 快速排序 | 0.003s                            | 0.016s                            | 0.015s                               | 0.078s                               |
| 归并排序 | 0.003s                            | 0.014s                            | 0.017s                             | 0.115s                               |
| 基数排序 | 0.01s                             | 0.014s                            | 0.034s | 0.104s |
| 希尔排序 | 0.003s                            | 0.02s                             | 0.019s                            | 0.136s                               |
| 选择排序 | 0.061s                            | 1.648s                            | 5.338s                              | 158.886s                            |

单独比较快速排序和基数排序

| 排序     | 数据量：100万<br/>数据区间：[-10000000, 10000000] | 数据量：1000万<br/>数据区间：[-100000000, 100000000] | 数据量：5000万<br/>数据区间：[-500000000, 500000000] |
| -------- | ------------------------------------------------- | ---------------------------------------------------- | ---------------------------------------------------- |
| 快速排序 | 0.1s                                              | 1.79s                                                | 6.238s                                               |
| 基数排序 | 0.126s                                            | 1.271s                                               | 5.958s                                               |

达到一定数据量后，基数排序的优势也会逐渐显示出来。但是当数据量很少，数据位数很多时，基数排序效果不如快速排序。

## 4.其他

代码仓库地址：https://gitee.com/flyinglkp/homework_algorithm