算法

快速排序

概念

快速排序基于分治思想来实现。

  1. 分解：数组A[start,end]被划分为两个（可能为空）子数组A[start,postion-1]和A[postion+1,end]中的,使A[start,postion-1]的每一个元素都小于等于A[postion],A[postion+1,end]的每一个元素都大于等于A[postion]。
  2. 解决：通过递归调用快速排序，对子数组A[start,postion-1]和A[postion+1,end]进行排序。
  3. 合并：因为数组是原址排序，因此A[start,end]是有序的。

数组的划分（解决）实现思想图

PHP实现快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
function quickSort(&$array,$start,$end)
{
    if ($start < $end) {
        $postion = partition($array, $start, $end);
        quickSort($array,$start,$postion-1);
        quickSort($array,$postion+1,$end);
    }
}

function partition(&$arr,$start,$end) {
    $flag = $arr[$end];
    $i = $start-1;
    for ( $j=$start; $j<= $end-1; $j++) {
        if($arr[$j] <= $flag) {
            $i = $i+1;
            swap($arr,$i,$j);
        }
    }
    swap($arr,$i+1,$end);

    return $i+1;
}

function swap (&$arr,$exist,$replace) {
    $temp = $arr[$exist];
    $arr[$exist] = $arr[$replace];
    $arr[$replace] = $temp;
}

$array = array(1,6,5,4);
quickSort($array,0,3);
var_dump($array);