算法总结

时间复杂度：一个算法执行所耗费的时间。
空间复杂度：运行完一个程序所需内存的大小。

排序算法 平均时间复杂度 平均空间复杂度
冒泡排序 O(n2) O(1)
选择排序 O(n2) O(1)
插入排序 O(n2) O(1)
希尔排序 O(nlog2n) O(1)
归并排序 O(nlog2n) O(n)
快速排序 O(nlog2n) O(log2n)
堆排序 O(nlog2n) O(1)
桶排序 O(n+k) O(n+k)

下面排序，1～n个元素，默认从小到大排列。

冒泡排序（Bubble Sort）

算法描述

  1. 比较第1个、第2个元素，如果第1个比较大，则交换2个元素的位置；
  2. 比较第2个、第3个元素，3、4，4、5，以此类推，最后得到第n个元素为最大值；
  3. 对1～n－1的剩余元素，重复1、2步骤的操作，以此类推，每一次循环后，最大的元素在右边，直到排序完成。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
<?php

function swap(&$arr, $intI, $intJ) {
    $intTmp = $arr[$intI];
    $arr[$intI] = $arr[$intJ];
    $arr[$intJ] = $intTmp;
}

function bubbleSort($arr) {
    $intN = count($arr);
    for ($intI = 0; $intI < $intN; $intI++) {
        for ($intJ = 0; $intJ < $intN - $intI - 1; $intJ++) {
            if ($arr[$intJ] > $arr[$intJ + 1]) {
                swap($arr, $intJ, $intJ + 1);
            }
        }
    }
    return $arr;
}

$arr = array(2, 5, 6, 3, 1, 4, 3);
$arr = bubbleSort($arr);
var_export($arr);

选择排序（Selection Sort）

算法描述

  1. 从1～n里面，取第1个元素依次去跟其它元素比较；
  2. 如果遇到比他大的，则记录较大的元素下标i，用元素i继续去比较；
  3. 最后把i跟n交换位置，第n个元素为最大值；
  4. 从1～n－1里面，重复步骤1～3的操作，直到排序完成。

代码实现

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
<?php

function swap(&$arr, $intI, $intJ) {
    $intTmp = $arr[$intI];
    $arr[$intI] = $arr[$intJ];
    $arr[$intJ] = $intTmp;
}

function selectionSort($arr) {
    $intN = count($arr);
    for ($intI = 0; $intI < $intN; $intI++) {
        $intM = 0;
        for ($intJ = 0; $intJ < $intN - $intI - 1; $intJ++) {
            if ($arr[$intM] < $arr[$intJ + 1]) {
                $intM = $intJ + 1;
            }
        }
        swap($arr, $intM, $intJ);
    }
    return $arr;
}

$arr = array(2, 5, 6, 3, 1, 4, 3);
$arr = selectionSort($arr);
var_export($arr);

插入排序（Insertion Sort）

算法描述

  1. 取第1个元素，默认为已排序；
  2. 从右边未排序的元素中，取第一个元素，跟已排序的元素做比较（从后往前）；
  3. 如果遇到比他大的，则交换位置，遇到比他小的或到头了，则停止；
  4. 重复1～3操作，直到排序完成。

代码实现

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
<?php

function swap(&$arr, $intI, $intJ) {
    $intTmp = $arr[$intI];
    $arr[$intI] = $arr[$intJ];
    $arr[$intJ] = $intTmp;
}

function insertionSort($arr) {
    $intN = count($arr);
    for ($intJ = 1; $intJ < $intN; $intJ++) {
        $intI = $intJ - 1;
        $intT = $intJ;
        while ($intI >= 0 && $arr[$intT] < $arr[$intI]) {
            swap($arr, $intI, $intT);
            $intI--;
            $intT--;
        }
    }
    return $arr;
}

$arr = array(2, 5, 6, 3, 1, 4, 3);
$arr = insertionSort($arr);
var_export($arr);

快速排序（Quick Sort）

算法描述

  1. 取基准：取第1个元素作为基准；
  2. 划分区：用基准元素跟其它比较，比他小的放在他左边，比他大的放在他右边；
  3. 递归：把左、右两边的元素分别递归重复步骤1、2，最后把结果合并。

代码实现

方法1：

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
<?php

function quickSort($arr) {
    if (!isset($arr[1])) {
        return $arr;
    }
    $intPivot = $arr[0];
    $arrL = array();
    $arrR = array();
    for ($intI = 1; $intI < count($arr); $intI++) {
        if ($arr[$intI] < $intPivot) {
            $arrL[] = $arr[$intI];
        }
        else {
            $arrR[] = $arr[$intI];
        }
    }
    $arrL = quickSort($arrL);
    $arrL[] = $intPivot;
    $arrR = quickSort($arrR);
    return array_merge($arrL, $arrR);
}

$arr = array(2, 5, 6, 3, 1, 4, 3);
$arr = quickSort($arr);
var_export($arr);

方法2：

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
34
35
36
37
38
<?php

function _quickSort(&$arr, $intL, $intR) {
    if ($intL >= $intR) {
        return;
    }
    
    $intI = $intL;
    $intJ = $intR;
    $intPivot = $arr[$intI];
    
    while ($intI < $intJ) {
        while ($intI < $intJ && $intPivot <= $arr[$intJ]) {
            $intJ--;
        }
        $arr[$intI] = $arr[$intJ];
        while ($intI < $intJ && $intPivot > $arr[$intI]) {
            $intI++;
        }
        $arr[$intJ] = $arr[$intI];
    }
    
    $arr[$intI] = $intPivot;
    _quickSort($arr, $intL, $intI - 1);
    _quickSort($arr, $intI + 1, $intR);
}

function quickSort($arr) {
    if (!isset($arr[1])) {
        return $arr;
    }
    _quickSort($arr, 0, count($arr) - 1);
    return $arr;
}

$arr = array(2, 5, 6, 3, 1, 4, 3);
$arr = quickSort($arr);
var_export($arr);

堆排序（Heap Sort）

算法描述

  1. 将待排序元素，构成大顶堆（二叉树结构，顶部为最大值），此堆为初始无序区；
  2. 将堆顶第一个元素与最后一个n元素交换，得到新的无序区和有序区。
  3. 重复步骤1~2，直到无序区没有元素。

代码实现

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
34
35
36
37
38
39
40
41
42
<?php

function swap(&$arr, $intI, $intJ) {
    $intTmp = $arr[$intI];
    $arr[$intI] = $arr[$intJ];
    $arr[$intJ] = $intTmp;
}

function heapify(&$arr, $intI, $intJ) {
    $intL = $intI * 2 + 1;
    $intR = $intL + 1;
    $intMax = $intI;
    if ($intL <= $intJ && $arr[$intL] > $arr[$intMax]) {
        $intMax = $intL;
    }
    if ($intR <= $intJ && $arr[$intR] > $arr[$intMax]) {
        $intMax = $intR;
    }
    if ($intI != $intMax) {
        swap($arr, $intI, $intMax);
        heapify($arr, $intMax, $intJ);
    }
}

function heapSort($arr) {
    $intJ = count($arr) - 1;
    if ($intJ <= 0) {
        return $arr;
    }
    for ($intI = $intJ / 2 - 1; $intI >= 0; $intI--) {
        heapify($arr, $intI, $intJ);
    }
    for ($intI = $intJ; $intI >= 1; $intI--) {
        swap($arr, 0, $intI);
        heapify($arr, 0, $intI - 1);
    }
    return $arr;
}

$arr = array(2, 5, 6, 3, 1, 4, 3);
$arr = heapSort($arr);
var_export($arr);

桶排序（Bucket Sort）

算法描述

  1. 假设待排序的一组元素分布在一个范围内，并将这一范围划分为N个子范围，也就是桶；
  2. 将待排序的一组元素，分档放入这些桶，并将桶中的元素进行排序；
  3. 将每个桶中的数据有序地合并起来。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
<?php

function bucketSort($arr, $intMax) {
    $arrBucket = array_fill(0, $intMax + 1, 0);

    for ($intI = 0; $intI < count($arr); $intI++) {
        $arrBucket[$arr[$intI]]++;
    }

    $arrSort = array();
    for ($intI = 0; $intI <= $intMax; $intI++) {
        for ($intJ = 1; $intJ <= $arrBucket[$intI]; $intJ++) {
            $arrSort[] = $intI;
        }
    }
    return $arrSort;
}

$arr = array(2, 5, 6, 3, 1, 4, 3);
$arr = bucketSort($arr, 6);
var_export($arr);