快速排序算法(2)

快速排序算法

快速排序算法

是一种不太稳定的算法 ,也是对冒泡算法的一种改进

算法基本原理

1. 对一个数组内的所有元素进行排列 ,选取其中的一个元素作为基准元素,将所有小于基准元素的元素都放在一边,比基准元素大的元素都放在另一边
2. 将依据基准元素分成两列的元素,使用上述的排序方法进行排列(递归调用)
3. 直到一层层递归都符合递归调用的结束条件,结束递归调用
4. 最终完成快速排序

代码示例

<?php
/**
 * 快速排序算法
 *
 * @param array $arr
 * @return array
 */
function quick_sort(array $arr)
{
    // 1.获取数组的长度
    $len = count($arr);
    // 2.结束条件
    if($len <= 1)
    {
        return $arr ;
    }
    // 3.设置一个中间数据作为基准数,这个数可以是数组中的任意一个元素,我们通常取第一个
    $middle = $arr[0];
    // 4.定义两个空数组,后面分别存放比基数元素大的元素和比基数元素小的元素
    $left = $right = [] ;
    for($i = 1;$i<$len;$i++)
    {
        // 5.各个元素与基准数元素作比较,比基准数小的放在左边(前面),比基准数大的元素放在右边(后面)
        if($arr[$i] < $middle)
        {
            $left[] = $arr[$i];
        }else{
            $right[] = $arr[$i];
        }
    }
    //注意此处的递归调用(此处是关键)

    // 将左边的元素递归调用, 最终递归调用的终止条件成立,而退出递归调用
    $left = quick_sort($left); // 最终退出递归时 [13,27,38]
    $right = quick_sort($right); // right数组情况同上 最终退出递归时 [49,65,76,97]
    return array_merge($left,[$middle],$right);
}
$arr = [49,38,65,97,76,13,27,49];
var_dump(quick_sort($arr));
/*
  array (size=8)
  0 => int 13
  1 => int 27
  2 => int 38
  3 => int 49
  4 => int 49
  5 => int 65
  6 => int 76
  7 => int 97
*/

图例

quick_sort.jpg

动态图

quick_sort.gif