PHP

常用的排序算法

2016-12-06  本文已影响20人  零一间

1 冒泡排序

冒泡排序(Bubble Sort)也是一种简单直观的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

算法步骤:
1)比较相邻的元素。如果第一个比第二个大,就交换他们两个。
2)对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
3)针对所有的元素重复以上的步骤,除了最后一个。
4)持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

function bubble_sort($arr = []) {
    
    $count = count ( $arr );
    
    for($i = 0; $i < $count - 1; $i ++) {
        
        for($j = 1; $j < $count - $i - 1; $j ++) {
            
            if ($arr [$j] > $arr [$j + 1]) {
                list ( $arr [$j], $arr [$j + 1] ) = [ 
                        $arr [$j + 1],
                        $arr [$j] 
                ];
            }
        }
    }
    return $arr;
}

2 插入排序

插入排序是一种最简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

算法步骤:
1)将第一待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。
2)从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面。)

function insert_sort($arr = []) {
    
    $count = count ( $arr );
    
    for($i = 1; $i < $count - 1; $i ++) {
        
        $temp = $arr [$i];
        
        for($j = $i - 1; $j >= 0; $j --) {
            
            if ($temp < $arr [$j]) {
                
                list ( $arr [$j], $arr [$j + 1] ) = [ 
                        $arr [$j + 1],
                        $arr [$j] 
                ];
            }
        }
    }
    
    return $arr;
}

3 快速排序

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。
快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。

算法步骤:
1 从数列中挑出一个元素,称为 “基准”(pivot),
2 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
3 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。

function quick_sort($arr = []) {
    
    $count = count ( $arr );
    
    if ($count <= 1)
        return $arr;
    
    $baseNum = $arr [0];
    $leftArr = [ ];
    $rightArr = [ ];
    
    for($i = 1; $i < $count; $i ++) {
        
        if ($arr [$i] < $baseNum) {
            $leftArr [] = $arr [$i];
        } else {
            $rightArr [] = $arr [$i];
        }
    }
    
    $leftArr = quick_sort ( $leftArr );
    $rightArr = quick_sort ( $rightArr );
    return array_merge ( $leftArr, [  $baseNum  ], $rightArr );
}

4 选择排序

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。

算法步骤:
1)首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置
2)再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。
3)重复第二步,直到所有元素均排序完毕。

function select_sort($arr=[]){
    
    $count=count($arr);
    
    for($i=0;$i<$count;$i++){
        
        $minIndex=$i;
        for ($j=$i+1;$j<$count;$j++){
            
            if($arr[$minIndex] >= $arr[$j]){
                $minIndex=$j;
            }
        }
        
        if($i != $minIndex){
            list($arr[$i],$arr[$minIndex])=[$arr[$minIndex],$arr[$i]];
        }
    }

    return  $arr;
    
}

归并排序

function Merge(&$arr, $left, $mid, $right) {
  $i = $left;
  $j = $mid + 1;
  $k = 0;
  $temp = array();
  while ($i <= $mid && $j <= $right)
  {
    if ($arr[$i] <= $arr[$j])
      $temp[$k++] = $arr[$i++];
    else
      $temp[$k++] = $arr[$j++];
  }
  while ($i <= $mid)
    $temp[$k++] = $arr[$i++];
  while ($j <= $right)
    $temp[$k++] = $arr[$j++];
  for ($i = $left, $j = 0; $i <= $right; $i++, $j++)
    $arr[$i] = $temp[$j];
}
 
function MergeSort(&$arr, $left, $right)
{
  if ($left < $right)
  {
    $mid = floor(($left + $right) / 2);
    MergeSort($arr, $left, $mid);
    MergeSort($arr, $mid + 1, $right);
    Merge($arr, $left, $mid, $right);
  }
}

二分查找-递归

function bin_search($arr,$low,$high,$value) {
    if($low>$high)
        return false;
    else {
        $mid=floor(($low+$high)/2);
        if($value==$arr[$mid])
            return $mid;
        elseif($value<$arr[$mid])
            return bin_search($arr,$low,$mid-1,$value);
        else
            return bin_search($arr,$mid+1,$high,$value);
    }
}


二分查找-非递归

function bin_search($arr,$low,$high,$value) {
    while($low<=$high) {
        $mid=floor(($low+$high)/2);
        if($value==$arr[$mid])
            return $mid;
        elseif($value<$arr[$mid])
            $high=$mid-1;
        else
            $low=$mid+1;
    }
    return false;
}

上一篇下一篇

猜你喜欢

热点阅读