排序的算法很多，常见的就几个。
以下是我收集和整理的几个排序方法：
1、插入排序
有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。
插入排序的基本思想是：每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
function insertSort($arr){
for($i=1;$i<count($arr);$i++){ $tmp=$arr[$i]; $key=$i-1; while($key>=0&&$tmp<$arr[$key]){
$arr[$key+1]=$arr[$key];
$key--;
}
if(($key+1)!=$i)
$arr[$key+1]=$tmp;
}
return$arr;
}
2、希尔排序
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
function shell_sort(&$arr)
{
if(!is_array($arr)) return;
$n = count($arr);
for($gap = floor($n/2);$gap > 0;$gap = floor($gap/=2))
{
for($i = $gap;$i < $n;++$i) { for($j = $i - $gap;$j >= 0&&$arr[$j + $gap] < $arr[$j];$j -= $gap)
{
$temp = $arr[$j];
$arr[$j] = $arr[$j+$gap];
$arr[$j + $gap] = $temp;
}
}
}
}
3、选择排序
选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法（比如序列[5， 5， 3]第一次就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面）。
function selection_sort($array){
$count=count($array);
for($i=0;$i<$count-1;$i++){ /*findtheminest*/ $min=$i; echo'$min-->'.$array[$min].'-->';
for($j=$i+1;$j<$count;$j++){ //由小到大排列 if($array[$min]>$array[$j]){
//表明当前最小的还比当前的元素大
$min=$j;
//赋值新的最小的
}
}
echo$array[$min].'coco
';
/*swap$array[$i]and$array[$min]即将当前内循环的最小元素放在$i位置上*/
if($min!=$i){
$temp=$array[$min];
$array[$min]=$array[$i];
$array[$i]=$temp;
}
}
return$array;
}
$old_array=array(3,4,5,6,8,2,12);
$new_array=selection_sort($old_array);
print_r($new_array);
4、堆排序
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。
/**
* 使用异或交换2个值，原理：一个值经过同一个值的2次异或后，原值不变
* @param int $a
* @param int $b
*/
function swap(&$a,&$b){
$a = $a^$b;
$b = $a^$b;
$a = $a^$b;
}
/**
* 整理当前树节点（$n），临界点$last之后为已排序好的元素
* @param int $n
* @param int $last
* @param array $arr
*
*/
function adjustNode($n,$last,&$arr){
$l = $n<<1; // 左孩子 if( !isset($arr[$l])||$l>$last ){
return ;
}
$r = $l+1; // 右孩子
// 如果右孩子比左孩子大，则让父节点与右孩子比
if( $r<=$last&&$arr[$r]>$arr[$l] ){
$l = $r;
}
// 如果其中子节点$l比父节点$n大，则与父节点$n交换
if( $arr[$l]>$arr[$n] ){
swap($arr[$l],$arr[$n]);
// 交换之后，父节点($n)的值可能还小于原子节点($l)的子节点的值，所以还需对原子节点($l)的子节点进行调整，用递归实现
adjustNode($l, $last, $arr);
}
}
/**
* 堆排序（最大堆）
* @param array $arr
*/
function heapSort(&$arr){
// 最后一个蒜素位
$last = count($arr);
// 堆排序中常忽略$arr[0]
array_unshift($arr, 0);
// 最后一个非叶子节点
$i = $last>>1;
// 整理成最大堆，最大的数放到最顶，并将最大数和堆尾交换，并在之后的计算中，忽略数组最后端的最大数(last)，直到堆顶（last=堆顶）
while(true){
adjustNode($i, $last, $arr);
if( $i>1 ){
// 移动节点指针，遍历所有节点
$i--;
}
else{
// 临界点$last=1，即所有排序完成
if( $last==1 ){
break;
}
swap($arr[$last],$arr[1]);
$last--;
}
}
// 弹出第一个元素
array_shift($arr);
}
5、冒泡排序
function bubbleSort($numbers) {
$cnt = count($numbers);
for ($i = 0; $i < $cnt; $i++) {
for ($j = 0; $j < $cnt - $i - 1; $j++) { if ($numbers[$j] > $numbers[$j + 1]) {
$temp = $numbers[$j];
$numbers[$j] = $numbers[$j + 1];
$numbers[$j + 1] = $temp;
}
}
}
return $numbers;
}
$num = array(20, 40, 60, 80, 30, 70, 90, 10, 50, 0);
var_dump(bubbleSort($num));
6、快速排序
快速排序（Quicksort）是对冒泡排序的一种改进。
快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
function quickSort(&$arr){
if(count($arr)>1){
$k=$arr[0];
$x=array();
$y=array();
$_size=count($arr);
for($i=1;$i<$_size;$i++){
if($arr[$i]<=$k){ $x[]=$arr[$i]; }elseif($arr[$i]>$k){
$y[]=$arr[$i];
}
}
$x=quickSort($x);
$y=quickSort($y);
return array_merge($x,array($k),$y);
}else{
return$arr;
}
}
7、归并排序
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
归并过程为：比较a[i]和b[j]的大小，若a[i]≤b[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否则将第二个有序表中的元素b[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。
//merge函数将指定的两个有序数组(arr1,arr2)合并并且排序
//我们可以找到第三个数组,然后依次从两个数组的开始取数据哪个数据小就先取哪个的,然后删除掉刚刚取过///的数据
function al_merge($arrA,$arrB)
{
$arrC = array();
while(count($arrA) && count($arrB)){
//这里不断的判断哪个值小,就将小的值给到arrC,但是到最后肯定要剩下几个值,
//不是剩下arrA里面的就是剩下arrB里面的而且这几个有序的值,肯定比arrC里面所有的值都大所以使用
$arrC[] = $arrA['0'] < $arrB['0'] ? array_shift($arrA) : array_shift($arrB);
}
return array_merge($arrC, $arrA, $arrB);
}
//归并排序主程序
function al_merge_sort($arr){
$len = count($arr);
if($len <= 1)
return $arr;//递归结束条件,到达这步的时候,数组就只剩下一个元素了,也就是分离了数组
$mid = intval($len/2);//取数组中间
$left_arr = array_slice($arr, 0, $mid);//拆分数组0-mid这部分给左边left_arr
$right_arr = array_slice($arr, $mid);//拆分数组mid-末尾这部分给右边right_arr
$left_arr = al_merge_sort($left_arr);//左边拆分完后开始递归合并往上走
$right_arr = al_merge_sort($right_arr);//右边拆分完毕开始递归往上走
$arr = al_merge($left_arr, $right_arr);//合并两个数组,继续递归
return $arr;
}
$arr = array(12, 5, 4, 7, 8, 3, 4, 2, 6, 4, 9);
print_r(al_merge_sort($arr));
8、基数排序
基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。
function R_Sort(array &$arr,$loop){
$tempArr = array();
$count = count($arr);
for($i = 0;$i < 10;$i ++){
$tempArr[$i] = array();
}
//求桶的index的除数
//如798个位桶index=(798/1)%10=8
//十位桶index=(798/10)%10=9
//百位桶index=(798/100)%10=7
//$tempNum为上式中的1、10、100
$tempNum = (int)pow(10, $loop - 1);
for($i = 0;$i < $count;$i ++){
//求出某位上的数字
$row_index = ($arr[$i] / $tempNum) % 10;
//入桶
array_push($tempArr[$row_index],$arr[$i]);
}
//还原回原数组中
$k = 0;
for($i = 0;$i < 10;$i ++){ //出桶 while(count($tempArr[$i]) > 0){
$arr[$k ++] = array_shift($tempArr[$i]);
}
}
}
9、外部排序
外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。
转载请注明：永盟博客 » 几个经典排序（php）
