我有一个简单的数组。数组长度总是有一个整数的平方根。所以 16、25、36 等等。
$array = array('1', '2', '3', '4' ... '25');
我所做的是用 HTML 排列数组，使其看起来像一个具有均匀边的块。
我想做的是对元素进行排序，这样当我将 JSON 编码的数组传递给 jQuery 时，它将迭代数组，淡入当前块，因此我会得到一种波浪动画。所以我想像这样对数组进行排序
所以我的排序数组看起来像
$sorted = array('1', '6', '2', '3', '7', '11', '16, '12' .. '25');
有没有办法这样做？..谢谢
很酷的问题。这是一个分析和一个算法。
使用此算法的一个关键优势是它全部使用简单的整数计算完成；它没有“if”语句，因此没有分支，这意味着如果它被编译，即使对于非常大的 n 值，它也会非常快速地执行。这也意味着它可以很容易地并行化以将工作分配到多个处理器上以获得非常大的 n 值。
考虑一个 8x8 网格（这里，输入在技术上是 n = 64，但为了简单起见，我将在下面的公式中使用 n = 8）遵循这个 zigzag 模式，就像这样（使用 0 索引的行和列轴）：
[ 0] [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7]
[ 0] 1 3 4 10 11 21 22 36
[ 1] 2 5 9 12 20 23 35 37
[ 2] 6 8 13 19 24 34 38 49
[ 3] 7 14 18 25 33 39 48 50
[ 4] 15 17 26 32 40 47 51 58
[ 5] 16 27 31 41 46 52 57 59
[ 6] 28 30 42 45 53 56 60 63
[ 7] 29 43 44 54 55 61 62 64
首先注意从左下角 (0,7) 到右上角 (7,0) 的对角线将网格划分为两个近乎镜像的分量：
[ 0] [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7]
[ 0] 1 3 4 10 11 21 22 36
[ 1] 2 5 9 12 20 23 35
[ 2] 6 8 13 19 24 34
[ 3] 7 14 18 25 33
[ 4] 15 17 26 32
[ 5] 16 27 31
[ 6] 28 30
[ 7] 29
和
[ 0] [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7]
[ 0] 36
[ 1] 35 37
[ 2] 34 38 49
[ 3] 33 39 48 50
[ 4] 32 40 47 51 58
[ 5] 31 41 46 52 57 59
[ 6] 30 42 45 53 56 60 63
[ 7] 29 43 44 54 55 61 62 64
您可以看到右下角只是左上角的镜像，并从平方加上 1（在本例中为 65）减去。
如果我们可以计算左上部分，那么右下部分可以很容易地计算，只需将平方加 1 ( n * n + 1) 并减去反坐标 ( value(n - x - 1, n - y - 1)) 处的值。
例如，考虑右下角的任意一对坐标，例如 (6,3)，其值为 48。按照这个公式，可以得到(8 * 8 + 1) - value(8 - 6 - 1, 8 - 3 - 1)，简化为65 - value(1, 4)。查看左上角，(1,4) 处的值为 17 65 - 17 == 48。
但是我们仍然需要计算左上角的部分。请注意，这也可以进一步细分为两个重叠的组件，其中一个组件的数字会随着您向右上方的增加而增加：
[ 0] [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7]
[ 0] 3 10 21 36
[ 1] 2 9 20 35
[ 2] 8 19 34
[ 3] 7 18 33
[ 4] 17 32
[ 5] 16 31
[ 6] 30
[ 7] 29
当您向左下方移动时，其中一个组件的数字会增加：
[ 0] [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7]
[ 0] 1 4 11 22
[ 1] 5 12 23
[ 2] 6 13 24
[ 3] 14 25
[ 4] 15 26
[ 5] 27
[ 6] 28
[ 7]
前者也可以定义为坐标x + y和为奇数的数，后者定义为坐标和为偶数的数。
现在，这里的关键见解是我们在这里绘制三角形，所以毫不奇怪，三角形数在这里扮演着重要的角色。三角形数序为：1、3、6、10、15、21、28、36、...
如您所见，在奇和分量中，每隔一个以 3 开头的三角形数出现在第一行（3、10、21、36）中，而在偶数分量中，每隔一个以 1 开头的三角形数出现在第一列 (1, 6, 15, 28)。
具体来说，对于给定的坐标对 (x,0) 或 (0,y)，对应的三角形数是 triangle(x + 1) 或 triangle(y + 1)。
图形的其余部分可以通过从这些三角形数中向上或向下递增地减去对角线来计算，这相当于减去给定的行数或列数。
请注意，对角线可以正式定义为具有给定坐标和的所有单元格的集合。例如，坐标和为 3 的对角线具有坐标 (0,3)、(1,2)、(2,1) 和 (3,0)。因此，单个数字定义了每个对角线，并且该数字也用于确定起始三角形数。
所以从简单的检查来看，计算奇和分量的公式很简单：
triangle(x + y + 1) - y
计算偶和分量的公式很简单：
triangle(x + y + 1) - x
众所周知的三角形数公式也很简单：
triangle(n) = (n * (n + 1)) / 2
所以，算法是：
value[x, y] = triangle(x + y + 1) - x.value[x, y] = triangle(x + y + 1) - y.n * n + 1如本文第一部分所述，通过简单的减法计算右下部分的索引。这可以通过两个向后计数的嵌套循环来完成（并将内部循环限制在外部循环上以仅获得右下部分）。value[x, y] = (n * n + 1) - value[n - x - 1, n - y - 1].这是我的。
function waveSort(array $array) {
$dimension = pow(count($array),0.5);
if((int)$dimension != $dimension) {
throw new InvalidArgumentException();
}
$tempArray = array();
for($i = 0; $i < $dimension; $i++) {
$tempArray[] = array_slice($array,$i*$dimension,$dimension);
}
$returnArray = array();
for($i = 0; $i < $dimension * 2 -1; $i++) {
$diagonal = array();
foreach($tempArray as $x => $innerArray) {
if($i - $x >= 0 && $i - $x < $dimension) {
$diagonal[] = $innerArray[$i - $x];
}
}
if($i % 2 == 1) {
krsort($diagonal);
}
$returnArray = array_merge($returnArray,$diagonal);
}
return $returnArray;
}
用法：
<?php
$a = range(1,25);
var_dump(waveSort($a));
输出
array(25) {
[0]=>
int(1)
[1]=>
int(6)
[2]=>
int(2)
[3]=>
int(3)
[4]=>
int(7)
[5]=>
int(11)
[6]=>
int(16)
[7]=>
int(12)
[8]=>
int(8)
[9]=>
int(4)
[10]=>
int(5)
[11]=>
int(9)
[12]=>
int(13)
[13]=>
int(17)
[14]=>
int(21)
[15]=>
int(22)
[16]=>
int(18)
[17]=>
int(14)
[18]=>
int(10)
[19]=>
int(15)
[20]=>
int(19)
[21]=>
int(23)
[22]=>
int(24)
[23]=>
int(20)
[24]=>
int(25)
}
尽管这个问题已经有很多解决方案，但这是我的：
将其与其他解决方案区分开来的主要特点：
来源：
<?php
function zigzag($input)
{
$output = array();
$inc = -1;
$i = $j = 0;
$steps = 0;
$bounds = sqrt(sizeof($input));
if(fmod($bounds, 1) != 0)
{
die('Matrix must be square');
}
while($steps < sizeof($input))
{
if($i >= $bounds) // bottom edge
{
$i--;
$j++;
$j++;
$inc = 1;
}
if($j >= $bounds) // right edge
{
$i++;
$i++;
$j--;
$inc = -1;
}
if($j < 0) // left edge
{
$j++;
$inc = 1;
}
if($i < 0) // top edge
{
$i++;
$inc = -1;
}
$output[] = $input[$bounds * $i + $j];
$i = $i - $inc;
$j = $j + $inc;
$steps++;
}
return $output;
}
$a = range(1,25);
var_dump(zigzag($a));
顺便说一下，这种算法被称为“zig zag 扫描”，并被大量用于 JPEG 和 MPEG 编码。
使用单个循环并利用 simetry 并且没有排序：
function waveSort(array $array) {
$n2=count($array);
$n=sqrt($n2);
if((int)$n != $n) throw new InvalidArgumentException();
$x=0; $y=0; $dir = -1;
$Result = array_fill(0, $n2, null);
for ($i=0; $i < $n2/2; $i++) {
$p=$y * $n +$x;
$Result[$i]=$array[$p];
$Result[$n2-1-$i]=$array[$n2-1-$p];
if (($dir==1)&&($y==0)) {
$x++;
$dir *= -1;
} else if (($dir==-1)&&($x==0)) {
$y++;
$dir *= -1;
} else {
$x += $dir;
$y -= $dir;
}
}
return $Result;
}
$a = range(1,25);
var_dump(waveSort($a));
我用 C# 编写了它，所以没有在 PHP 中编译/解析它，但是这个逻辑应该可以工作：
List<long> newList = new List<long>();
double i = 1;
double root = Math.Sqrt(oldList.Count);
bool direction = true;
while (newList.Count < oldList.Count)
{
newList.Add(oldList[(int)i - 1]);
if (direction)
{
if (i + root > root * root)
{
i++;
direction = false;
}
else if (i % root == 1)
{
i += 5;
direction = false;
}
else
{
i += root - 1;
}
}
else
{
if (i - root <= 0)
{
direction = true;
if (i % root == 0)
{
i += root;
}
else
{
i++;
}
direction = true;
}
else if (i % root == 0)
{
direction = true;
i += root;
}
else
{
i += 1 - root;
}
}
}
PHP 版本看起来像这样：
$oldList = ...
$newList = [];
$i = 1;
$root = sqrt(Count($oldList);
$direction = true;
while (count($newList) < count($oldList)
{
$newList[] = $oldList[$i - 1];
if ($direction)
{
if ($i + $root > $root * $root)
{
$i++;
$direction = false;
}
else if ($i % $root == 1)
{
$i += 5;
$direction = false;
}
else
{
$i += $root - 1;
}
}
else
{
if ($i - $root <= 0)
{
$direction = true;
if ($i % $root == 0)
{
$i += $root;
}
else
{
i++;
}
direction = true;
}
else if ($i % $root == 0)
{
$direction = true;
$i += $root;
}
else
{
$i += 1 - $root;
}
}
}
示例 Python 实现：
def wave(size):
curX = 0
curY = 0
direction = "down"
positions = []
positions.append((curX, curY))
while not (curX == size-1 and curY == size-1):
if direction == "down":
if curY == size-1: #can't move down any more; move right instead
curX += 1
else:
curY += 1
positions.append((curX, curY))
#move diagonally up and right
while curX < size-1 and curY > 0:
curX += 1
curY -= 1
positions.append((curX, curY))
direction = "right"
continue
else: #direction == "right"
if curX == size-1: #can't move right any more; move down instead
curY += 1
else:
curX += 1
positions.append((curX, curY))
#move diagonally down and left
while curY < size-1 and curX > 0:
curX -= 1
curY += 1
positions.append((curX, curY))
direction = "down"
continue
return positions
size = 5
for x, y in wave(size):
index = 1 + x + (y*size)
print index, x, y
输出：
1 0 0
6 0 1
2 1 0
3 2 0
7 1 1
11 0 2
16 0 3
12 1 2
8 2 1
4 3 0
5 4 0
9 3 1
13 2 2
17 1 3
21 0 4
22 1 4
18 2 3
14 3 2
10 4 1
15 4 2
19 3 3
23 2 4
24 3 4
20 4 3
25 4 4
喜剧单行实现：
def wave(size):
return [1+x+size*y for x,y in filter(lambda (x,y): x >=0 and x < size and y >= 0 and y < size, reduce(lambda x, y: x+y, [r if i==0 else list(reversed(r)) for i, r in enumerate([(x-delta, delta) for delta in range(size)] for x in range(size*2))], []))]
print wave(5)
输出：
[1, 6, 2, 11, 7, 3, 16, 12, 8, 4, 21, 17, 13, 9, 5, 22, 18, 14, 10, 23, 19, 15, 24, 20, 25]
另一种 PHP 解决方案，仅使用forand if，仅遍历数组一次
function waveSort(array $array) {
$elem = sqrt(count($array));
for($i = 0; $i < $elem; $i++) {
$multi[] = array_slice($array, $i*$elem , $elem);
}
$new = array();
$rotation = false;
for($i = 0; $i <= $elem-1; $i++) {
$k = $i;
for($j = 0; $j <= $i; $j++) {
if($rotation)
$new[] = $multi[$k][$j];
else
$new[] = $multi[$j][$k];
$k--;
}
$rotation = !$rotation;
}
for($i = $elem-1; $i > 0; $i--) {
$k = $elem - $i;
for($j = $elem-1; $j >= $elem - $i; $j--) {
if(!$rotation)
$new[] = $multi[$k][$j];
else
$new[] = $multi[$j][$k];
$k++;
}
$rotation = !$rotation;
}
return $new;
}
$array = range(1, 25);
$result = waveSort($array);
print_r($result);
$array = range(1, 36);
$result = waveSort($array);
print_r($result);
这是我的看法。与qiuntus的回复类似，但更简洁。
function wave($base) {
$i = 1;
$a = $base;
$square = $base*$base;
$out = array(1);
while ($i < $square) {
if ($i > ($square - $base)) { // hit the bottom
$i++;
$out[] = $i;
$a = 1 - $base;
} elseif ($i % $base == 0) { // hit the right
$i += $base;
$out[] = $i;
$a = $base - 1;
} elseif (($i - 1) % $base == 0) { // hit the left
$i += $base;
$out[] = $i;
$a = 1 - $base;
} elseif ($i <= $base) { // hit the top
$i++;
$out[] = $i;
$a = $base - 1;
}
if ($i < $square) {
$i += $a;
$out[] = $i;
}
}
return $out;
}