常见算法3、快速排序 Quick sort

一、简介

快速排序是一种使用分而治之（divide and cinquer，D&C）的排序算法，是最快的排序算法之一，也是C&C典范。

快速排序的原理：随机找出一个数（通常就拿数组的第一个数就行），把它插入一个位置，使得它左边的数都比它小，右边的数都比它大，这样就将一个数组分成了两个子数组，然后在按照同样的方法把子数组分成更小的子数组，直到不能分解为止。用比较通俗的话：挖坑填数+分而治之。

二、原理图：

三、代码实现：

1、Python 3 ：

#使用递归实现快速排序
def quick_sort(arr):
    if len(arr) < 2:
        return arr
    else:
        pivot = arr[0]
        less = [i for i in arr[1:] if i <= pivot ]
        greater = [i for i in arr[1:] if i > pivot ]
        return quick_sort(less) + [pivot] + quick_sort(greater)

myarr = [5,7,12,1,6,88,9,0]
print(quick_sort(myarr))

=============== 运行结果：===============
[0, 1, 5, 6, 7, 9, 12, 88]

2、PHP：

//使用递归实现快速排序
//方法1：
function quicksort(array $array) {
    if (count($array) < 2) {
        // base case, arrays with 0 or 1 element are already "sorted"
        return $array;
    } else {
        // recursive case
        $pivot = $array[0];
        //var_dump($array);

        $less = array_filter(array_slice($array, 1), function($i) use ($pivot) { 
            return $i <= $pivot; 
            });

        $greater = array_filter(array_slice($array, 1), function($j) use ($pivot) { 
            return $j > $pivot; 
            });
        return array_merge(quicksort($less), [$pivot], quicksort($greater));
  }
}

$myarr = [10, 5, 2, 3, 9];
print_r(quicksort($myarr)); 

=============== 运行结果：===============
Array ( [0] => 2 [1] => 3 [2] => 5 [3] => 9 [4] => 10 )

//方法2：
public function quickSort($data)
{
    $size = count($data);
    if($size>1) {
        $key = $data[0];
        $l = $r = [];
        for ($i = 1; $i < $size; $i++) {
            if ($data[$i] >= $key)
                $r[] = $data[$i];
            else
                $l[] = $data[$i];
        }
        $l_re = quickSort($l);
        $r_re = quickSort($r);

        return array_merge($l_re, [$key], $r_re);
    }
    else
        return $data;
}

参考

1、《算法图解》https://www.manning.com/books/grokking-algorithms