LINQ

在. net中，LINQ经常用于排序，它提供了比比较函数更好的语法，特别是当对象需要按多个字段排序时。LINQ到PHP有几个端口，包括YaLinqo库*。有了它，数组可以用单行进行排序，而无需编写复杂的比较函数。

$sortedByName         = from($objects)->orderBy('$v->name');
$sortedByCount        = from($objects)->orderBy('$v->count');
$sortedByCountAndName = from($objects)->orderBy('$v->count')->thenBy('$v->name');

比较可以通过传递回调作为第二个参数来进一步定制，例如:

$sortedByFilenameNat  = from($objects)->orderBy('$v->filename', 'strnatcmp');

这里，'$v->count'是函数($v) {return $v->count;}(任何一个都可以使用)。这些方法链返回迭代器，迭代器可以通过在最后添加->toArray()转换为数组。

在内部，orderBy和相关方法调用适当的数组排序函数(uasort、krsort、multisort、usort等)。

LINQ包含了更多受SQL启发的方法:过滤、分组、连接、聚合等。它最适合在不依赖数据库的情况下执行对数组和对象的复杂转换。

*由我开发，请参阅自述文件以了解更多细节和与其他LINQ端口的比较

这个答案是关于多列排序的，其中数组应该在每个一维元素中根据非连续索引的值进行排序。 这与多维排序不同，因为每个元素只由不同的Key=>Value对组成。

function fncCmp( array $ItmOne, array $ItmTwo ) {       ; # callback for sorting items (which are arrays) by values at specific indexes
  $strCmpOne = $ItmOne[ 'ColOne' ] . $ItmOne[ 'ColThr' ]; # build compound values
  $strCmpTwo = $ItmTwo[ 'ColOne' ] . $ItmTwo[ 'ColThr' ]; #   to compare
  return $strCmpOne <=> $strCmpTwo                      ; # pass back comparison-result
} # fncCmp

$arrDat = array(                                                       # define an array of items
  array( 'ColOne' => 'Val2', 'ColTwo' => 'Val8', 'ColThr' => 'Val6' )  #   each of which
 ,array( 'ColOne' => 'Val2', 'ColTwo' => 'Val9', 'ColThr' => 'Val4' )  #   is an
 ,array( 'ColOne' => 'Val1', 'ColTwo' => 'Val7', 'ColThr' => 'Val5' )  #   array of
)                                                                    ; #   fields
var_dump       ( $arrDat           )                                 ; # emit items before sort
$bolSrt = usort( $arrDat, 'fncCmp' )                                 ; # sort the array by comparing elements
var_dump       ( $arrDat           )                                 ; # emit items after  sort

稳定的排序

假设你有一个这样的数组:

['Kale', 'Kaleidoscope', 'Aardvark', 'Apple', 'Leicester', 'Lovely']

现在你只想对第一个字母排序:

usort($array, function($a, $b) {
    return strcmp($a[0], $b[0]);
});

结果是:

['Apple', 'Aardvark', 'Kale', 'Kaleidoscope', 'Lovely', 'Leicester']

那种东西不稳定!

敏锐的观察者可能已经注意到，数组排序算法(快速排序)并没有产生稳定的结果，并且相同首字母的单词之间的原始顺序没有被保留。这种情况很简单，我们应该比较整个字符串，但是让我们假设您的用例更复杂，比如在不同的字段上连续进行两次排序，它们不应该相互抵消。

施瓦兹变换

Schwartzian变换，也称为装饰-排序-不装饰习语，它使用固有的不稳定排序算法来实现稳定排序。

首先，你用另一个数组装饰每个数组元素，这个数组包含一个主键(value)和一个辅助键(它的索引或位置):

array_walk($array, function(&$element, $index) {
    $element = array($element, $index); // decorate
});

这将数组转换为:

[
    ['Kale', 0], ['Kaleidoscope', 1], 
    ['Aardvark', 2], ['Apple', 3], 
    ['Leicester', 4], ['Lovely', 5]
]

现在，我们调整比较步骤;我们再次比较第一个字母，但如果它们相同，则使用次键来保留原来的顺序:

usort($array, function($a, $b) {
    // $a[0] and $b[0] contain the primary sort key
    // $a[1] and $b[1] contain the secondary sort key
    $tmp = strcmp($a[0][0], $b[0][0]);

    if ($tmp != 0) {
        return $tmp; // use primary key comparison results
    }

    return $a[1] - $b[1]; // use secondary key
});

之后，我们进行装饰:

array_walk($array, function(&$element) {
    $element = $element[0];
});

最终结果:

['Aardvark', 'Apple', 'Kale', 'Kaleidoscope', 'Leicester', 'Lovely']

重用呢?

你必须重写比较函数来处理转换后的数组元素;你可能不想编辑你精致的比较函数，所以这里有一个比较函数的包装器:

function stablecmp($fn)
{
    return function($a, $b) use ($fn) {
        if (($tmp = call_user_func($fn, $a[0], $b[0])) != 0) {
            return $tmp;
        } else {
            return $a[1] - $b[1];
        }
    };
}

让我们使用这个函数来编写排序步骤:

usort($array, stablecmp(function($a, $b) {
    return strcmp($a[0], $b[0]);
}));

瞧!您的原始比较代码回来了。

最简单的方法是使用usort函数对数组进行排序，而不需要任何循环: 下面是一个例子:

   $array_compare= array("0" =>4,"1"=>2,"2"=>500,"3"=>100);

这将按降序排序:

usort($array_compare, function($a, $b) {
        return ($b['x1'] - $a['x1']) > 0 ? 1 :-1;
    });

这将按发送顺序排序:

usort($array_compare, function($a, $b) {
        return ($b['x1'] - $a['x1']) < 0 ? 1 :-1;
    });

大多数基本的方法都已经讲过了，我会试着看看其他类型的排序

用SPL排序

碎片堆

class SimpleHeapSort extends SplHeap {
    public function compare($a, $b) {
        return strcmp($a, $b);
    }
}

// Let's populate our heap here (data of 2009)
$heap = new SimpleHeapSort();
$heap->insert("a");
$heap->insert("b");
$heap->insert("c");

echo implode(PHP_EOL, iterator_to_array($heap));

输出

c
b
a

SplMaxHeap

SplMaxHeap类提供堆的主要功能，将最大值保持在顶部。

$heap = new SplMaxHeap();
$heap->insert(1);
$heap->insert(2);
$heap->insert(3);

SplMinHeap

SplMinHeap类提供了堆的主要功能，将最小值保持在顶部。

$heap = new SplMinHeap ();
$heap->insert(3);
$heap->insert(1);
$heap->insert(2);

其他类型的排序

冒泡排序

摘自维基百科关于冒泡排序的文章:

Bubble sort, sometimes incorrectly referred to as sinking sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name from the way smaller elements "bubble" to the top of the list. Because it only uses comparisons to operate on elements, it is a comparison sort. Although the algorithm is simple, most of the other sorting algorithms are more efficient for large lists.

function bubbleSort(array $array) {
    $array_size = count($array);
    for($i = 0; $i < $array_size; $i ++) {
        for($j = 0; $j < $array_size; $j ++) {
            if ($array[$i] < $array[$j]) {
                $tem = $array[$i];
                $array[$i] = $array[$j];
                $array[$j] = $tem;
            }
        }
    }
    return $array;
}

选择排序

摘自维基百科关于选择排序的文章:

在计算机科学中，选择排序是一种排序算法，特别是就地比较排序。它有O(n2)的时间复杂度，使得它在大型列表上效率低下，并且通常比类似的插入排序执行得更差。选择排序以其简单性而闻名，并且在某些情况下，特别是在辅助内存有限的情况下，它比更复杂的算法具有性能优势。

function selectionSort(array $array) {
    $length = count($array);
    for($i = 0; $i < $length; $i ++) {
        $min = $i;
        for($j = $i + 1; $j < $length; $j ++) {
            if ($array[$j] < $array[$min]) {
                $min = $j;
            }
        }
        $tmp = $array[$min];
        $array[$min] = $array[$i];
        $array[$i] = $tmp;
    }
    return $array;
}

插入排序

来自维基百科关于插入排序的文章:

插入排序是一种简单的排序算法，每次构建一个最终排序的数组(或列表)。在大型列表上，它的效率远远低于更高级的算法，如快速排序、堆排序或归并排序。然而，插入排序提供了几个优点:

function insertionSort(array $array) {
    $count = count($array);
    for($i = 1; $i < $count; $i ++) {

        $j = $i - 1;
        // second element of the array
        $element = $array[$i];
        while ( $j >= 0 && $array[$j] > $element ) {
            $array[$j + 1] = $array[$j];
            $array[$j] = $element;
            $j = $j - 1;
        }
    }
    return $array;
}

Shellsort

来自维基百科关于Shellsort的文章:

Shellsort，也称为Shell排序或Shell的方法，是一种就地比较排序。它泛化了交换排序，例如插入排序或冒泡排序，方法是先与相距很远的元素比较和交换元素，然后再与相邻的元素完成比较和交换。

function shellSort(array $array) {
    $gaps = array(
            1,
            2,
            3,
            4,
            6
    );
    $gap = array_pop($gaps);
    $length = count($array);
    while ( $gap > 0 ) {
        for($i = $gap; $i < $length; $i ++) {
            $tmp = $array[$i];
            $j = $i;
            while ( $j >= $gap && $array[$j - $gap] > $tmp ) {
                $array[$j] = $array[$j - $gap];
                $j -= $gap;
            }
            $array[$j] = $tmp;
        }
        $gap = array_pop($gaps);
    }
    return $array;
}

梳子排序

摘自维基百科关于梳状排序的文章:

梳状排序是由Wlodzimierz Dobosiewicz在1980年设计的一种相对简单的排序算法。后来，它在1991年被斯蒂芬·莱西和理查德·博克斯重新发现。梳状排序改进了冒泡排序。

function combSort(array $array) {
    $gap = count($array);
    $swap = true;
    while ( $gap > 1 || $swap ) {
        if ($gap > 1)
            $gap /= 1.25;
        $swap = false;
        $i = 0;
        while ( $i + $gap < count($array) ) {
            if ($array[$i] > $array[$i + $gap]) {
                // swapping the elements.
                list($array[$i], $array[$i + $gap]) = array(
                        $array[$i + $gap],
                        $array[$i]
                );
                $swap = true;
            }
            $i ++;
        }
    }
    return $array;
}

去排序

摘自维基百科关于归并排序的文章:

在计算机科学中，归并排序(也通常拼写为mergesort)是一种O(n log n)基于比较的排序算法。大多数实现都会产生稳定的排序，这意味着实现会保留排序输出中相等元素的输入顺序

function mergeSort(array $array) {
    if (count($array) <= 1)
        return $array;

    $left = mergeSort(array_splice($array, floor(count($array) / 2)));
    $right = mergeSort($array);

    $result = array();

    while ( count($left) > 0 && count($right) > 0 ) {
        if ($left[0] <= $right[0]) {
            array_push($result, array_shift($left));
        } else {
            array_push($result, array_shift($right));
        }
    }
    while ( count($left) > 0 )
        array_push($result, array_shift($left));

    while ( count($right) > 0 )
        array_push($result, array_shift($right));

    return $result;
}

快速排序

维基百科上关于快速排序的文章:

快速排序，或分区交换排序，是由Tony Hoare开发的一种排序算法，平均而言，对n个项目进行O(n log n)次比较。在最坏的情况下，它进行O(n2)比较，尽管这种行为很少见。

function quickSort(array $array) {
    if (count($array) == 0) {
        return $array;
    }
    $pivot = $array[0];
    $left = $right = array();
    for($i = 1; $i < count($array); $i ++) {
        if ($array[$i] < $pivot) {
            $left[] = $array[$i];
        } else {
            $right[] = $array[$i];
        }
    }
    return array_merge(quickSort($left), array(
            $pivot
    ), quickSort($right));
}

排列排序

来自维基百科关于排列排序的文章:

排列排序，通过生成输入数组/列表的可能排列，直到发现已排序的数组/列表。

function permutationSort($items, $perms = array()) {
    if (empty($items)) {
        if (inOrder($perms)) {
            return $perms;
        }
    } else {
        for($i = count($items) - 1; $i >= 0; -- $i) {
            $newitems = $items;
            $newperms = $perms;
            list($foo) = array_splice($newitems, $i, 1);
            array_unshift($newperms, $foo);
            $res = permutationSort($newitems, $newperms);
            if ($res) {
                return $res;
            }
        }
    }
}

function inOrder($array) {
    for($i = 0; $i < count($array); $i ++) {
        if (isset($array[$i + 1])) {
            if ($array[$i] > $array[$i + 1]) {
                return False;
            }
        }
    }
    return True;
}

基数排序

来自维基百科关于Radix排序的文章:

在计算机科学中，基数排序是一种非比较整数排序算法，它通过将键按具有相同重要位置和值的单个数字分组，对具有整数键的数据进行排序。

// Radix Sort for 0 to 256
function radixSort($array) {
    $n = count($array);
    $partition = array();

    for($slot = 0; $slot < 256; ++ $slot) {
        $partition[] = array();
    }

    for($i = 0; $i < $n; ++ $i) {
        $partition[$array[$i]->age & 0xFF][] = &$array[$i];
    }

    $i = 0;

    for($slot = 0; $slot < 256; ++ $slot) {
        for($j = 0, $n = count($partition[$slot]); $j < $n; ++ $j) {
            $array[$i ++] = &$partition[$slot][$j];
        }
    }
    return $array;
}

按键值进行多维排序

按键值对多维数组进行自然排序，并保持原始顺序(不打乱主键):

function multisortByKeyValue( $k, $arr ) {
    $ids   = array();
    $index = 1;

    foreach ( $arr as $key => $row ) {
        $ids[ $key ] = intval( $row[ $k ] ) . '-' . $index . '-' . $key;
        $index ++;
    }

    natsort( $ids );

    $arr = array_merge( $ids, $arr );

    return $arr;
}

测试用例:

$arr = array(
    'id1' => array(
        'label'    => 'ID 1',
        'priority' => 30,
    ),
    'id2' => array(
        'label'    => 'ID 2',
        'priority' => 70,
    ),
    'id3' => array(
        'label'    => 'ID 3',
        'priority' => 20,
    ),
    'id4' => array(
        'label'    => 'ID 4',
        'priority' => 30,
    ),
);

$sorted = multisortByKeyValue( 'priority', $arr );

// $sorted equals to:
/*
array (
  'id3' => array (
    'label' => 'ID 3',
    'priority' => 20,
  ),
  'id1' => array (
    'label' => 'ID 1',
    'priority' => 30,
  ),
  'id4' => array (
    'label' => 'ID 4',
    'priority' => 30,
  ),
  'id2' => array (
    'label' => 'ID 2',
    'priority' => 70,
  ),
)
*/