朝文分享（57）：畅游算法之海（三）——有序平方

摘要：Share interest, spread happiness, increase knowledge, and leave beautiful.

分享兴趣，传播快乐，增长见闻，留下美好！

亲爱的您，这里是LearningYard新学苑。

今天小编为大家带来“畅游算法之海(三）——有序平方”，欢迎您的访问。

Share interest, spread happiness, increase knowledge, and leave beautiful.

Dear, this is the LearingYard Academy!

Today, Swimming in the Sea of Algorithms (3) - Ordered Squares ，welcome to visit!

一、简介

1. Introduction

有序数组的平方，将有序数组中各元素进行平方，再从小到大依次排序，得到另一组有序数组。主要用于既有负数又有正数的有序数组中。该问题的难点在于负数的平方可能大于正数的平方，所以在平方后，还要进行一次排序。如果排序的方法不对，会导致运行时间很长。对应的力扣题目编号为977。

Squared sorted array, which squares the elements of the sorted array and sorts them from smallest to largest to get another sorted array. Used primarily in sorted arrays that contain both positive and negative numbers. The difficulty is that the square of a negative number can be larger than the square of a positive number, so after squaring, there's another sort to do. If the sorting is done incorrectly, this can lead to very long running times. The corresponding force buckle subject number is 977.

二、原理

2. Principle

符合逻辑的方法就是先对所有元素都平方一遍，再通过从小到大的顺序依次排列，最终返回数组。

The logical way to do this is to square the elements, sort them from smallest to largest, and return the array.

三、实现

3. Implementation

将数组中的所有元素平方需要一次循环。将平方后的数组由大到小进行排序，需要两层循环。排序的方法为冒泡排序法。

Squaring all the elements of an array takes one loop. Sorting the squared array from largest to smallest requires two loops. The sorting method is the bubble sorting method.

由于排序方法本身的复杂程度，让整个方法在运行时间上没有达到很好的效果。

Due to the complexity of the sorting method itself, the whole method does not achieve good results in running time.

四、双指针

4. Double pointer

这个问题也可以通过双指针来解决。之所以能用双指针解决，是因为有一个前提条件，有序数组。

This problem can also be solved with dual Pointers. We can solve it with two Pointers because we have a precondition, a sorted array.

下面有三组有序数组，它们又都一个特点，就是两边的平方大，中间的平方小。也就是整个数组中，平方最大只会出现在数组的两边，且越靠近中间，平方越小。

Here are three sorted arrays, and they all have the same characteristic: the squares on the sides are large and the squares in the middle are small. This means that the square will only appear at most on either side of the array, and the square will get smaller as you get closer to the middle.

抓住这个特点，就可以让该问题的排序更加简便，高效。也就是平方后，通过双指针，实现快速排序。双指针不是说就只有两个指针。这里用到三个指针，其中两个分别从两边依次向中间逼近，还有一个是用于更新数组。接下来就简单模拟一下运行过程。

By grasping this feature, we can make sorting this problem easier and more efficient. That is, after squaring, through the double pointer, to achieve quick sort. Dual Pointers do not mean that there are only two Pointers. Three Pointers are used.Two are used to approach the center from each side, and one is used to update the array. Let's briefly simulate how this works.

首先对所有元素进行平方。I指针从左到右，j指针从右到左。Result为nums的复制，由k指针进行更新。

We start by squaring all elements. The I pointer goes from left to right, and the j pointer goes from right to left. Result is a copy of nums and is updated by the k pointer.

将两端最大的值传入result中。两个指针向中间逼近，直到i大于j停止。这时k刚好更新完数组，返回result。

Pass the maximum value to result. The two Pointers approach towards the middle until i is greater than j and stop. At this point, k has just finished updating the array and returns result.