# SortingAlgorithm

**Repository Path**: paultest/SortingAlgorithm

## Basic Information

- **Project Name**: SortingAlgorithm
- **Description**: PHP中的排序算法
- **Primary Language**: PHP
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2018-03-27
- **Last Updated**: 2021-06-20

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# SortingAlgorithm
PHP中的排序算法

**（1）排序的定义：对一序列对象根据某个关键字进行排序；**

输入：n个数：a1,a2,a3,...,an

输出：n个数的排列:a1',a2',a3',...,an'，使得a1'<=a2'<=a3'<=...<=an'。

再讲的形象点就是排排坐，调座位，高的站在后面，矮的站在前面咯。


**（3）对于评述算法优劣术语的说明**

**稳定**：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；

**不稳定**：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；

**内排序**：所有排序操作都在内存中完成；

**外排序**：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；

**时间复杂度**: 一个算法执行所耗费的时间。

**空间复杂度**: 运行完一个程序所需内存的大小。

关于时间空间复杂度的更多了解请戳[这里](http://blog.csdn.net/booirror/article/details/7707551/)，或是看书程杰大大编写的《大话数据结构》还是很赞的，通俗易懂。

**（4）排序算法图片总结(图片来源于网络):**

排序对比：

![这里写图片描述](http://img.blog.csdn.net/20160916153212716)

**图片名词解释：**

n: 数据规模

k:“桶”的个数

In-place: 占用常数内存，不占用额外内存

Out-place: 占用额外内存

排序分类：

![这里写图片描述](http://img.blog.csdn.net/20160916154036887)

## 1. 冒泡排序
### 原理
依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。

冒泡排序的基本思想：每次比较两个相邻的元素，如果它们的顺序错误就把它们交换过来

核心部分：双重嵌套循环

时间复杂度：O(N^2)

由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序。

用二重循环实现，外循环变量设为i，内循环变量设为j。外循环重复9次，内循环依次重复9，8，...，1次。每次进行比较的两个元素都是与内循环j有关的，它们可以分别用a[j]和a[j+1]标识，i的值依次为1,2,...,9，对于每一个i,j的值依次为1,2,...10-i

注意：只要是涉及到数组排序的，最好是使用PHP内置的sort、rsort、asort、ksort、arsort、krsort函数即可实现数组排序

### 代码
1_BubbleSort_v1.php
```
<?php

// 需要排序的数组
$array = [10, 8, 7, 5, 2, 5, 10, 7, 5, 13, 10];

$res = BubbleSort($array);
print_r($res);

/**
 * 冒泡排序
 * @param $array array
 * @return array
 */
function BubbleSort($array)
{
    $num = count($array);

    for ($i = 1; $i < $num; $i++) {
        for ($j = 0; $j < $num - $i; $j++) {
            if ($array[$j] < $array[$j + 1]) {
                $temp = $array[$j];
                $array[$j] = $array[$j + 1];
                $array[$j + 1] = $temp;
            }
        }
    }

    return $array;
}

```

上面的代码可以做进一步的优化

设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可


### 代码
1_BubbleSort_v2.php
```
<?php

// 需要排序的数组
$array = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];

$res = BubbleSort($array);
print_r($res);

/**
 * 冒泡排序
 * @param $array array
 * @return array
 */
function BubbleSort($array)
{
    $i = count($array) - 1;

    while ($i > 0) {
        // 记录交换的位置，每趟开始时,无记录交换
        $pos = 0;
        for ($j = 0; $j < $i; $j++) {
            if ($array[$j] < $array[$j + 1]) {
                // 记录交换的位置
                $pos = $j;

                // 交换位置
                $temp = $array[$j];
                $array[$j] = $array[$j + 1];
                $array[$j + 1] = $temp;
            }
        }
        // 为下一趟排序作准备
        $i = $pos;
    }

    return $array;
}

```
## 2. 选择排序

### 基本思想
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完

### 原理
n个数的直接选择排序可经过n-1趟直接选择排序得到有序结果：

①初始状态：无序区为R[1..n]，有序区为空。

②第1趟排序，在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

……

③第i趟排序，第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n)。该趟排序从当前无序区中选出关键字最小的记录R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

这样，n个数的直接选择排序可经过n-1趟直接选择排序得到有序结果。
 
选择排序是不稳定的排序方法。时间复杂度 O(n^2)

注意：只要是涉及到数组排序的，最好是使用PHP内置的sort、rsort、asort、ksort、arsort、krsort函数即可实现数组排序

### 代码
2_SelectionSort.php
```
<?php

$array = [5, 8, 9, 3, 4, 7, 2, 4, 1];
var_dump(SelectionSort($array));

/**
 * 选择排序
 * @param $array
 * @return mixed
 */
function SelectionSort($array)
{
    $count = count($array);

    // 双重循环完成，外层控制轮数，当前的最小值，内层控制比较次数
    for ($i = 0; $i < $count; $i++) {
        // 假设最小值的位置
        $min = $i;

        // 使用假设的最小值和其他值比较，找到当前的最小值并保存到$min中
        for ($j = $i + 1; $j < $count; $j++) {
            // 判断当前循环值和已知最小值的比较，当发现更小的值时记录下键，并进行下一次比较
            if ($array[$j] < $array[$min]) {
                $min = $j;
            }
        }

        // 判断 $min 中的键和假设的最小值的键不一致则将其互换
        if ($min !== $i) {
            $temp = $array[$min];
            $array[$min] = $array[$i];
            $array[$i] = $temp;
        }
    }
    return $array;
}
```

## 3. 快速排序
### 原理
快速排序是基于二分的思想,快速排序（Quicksort）是对冒泡排序的一种改进。基本思想是：通过一趟排序将待排记录分割成独立的两部分，其中一部分的所有数据均比另一部分的所有数据都要小，则可分别对这两部分记录继续进行快速排序，整个排序过程可以递归进行，以达到整个序列有序的目的

快速排序之所以比较快，是因为相比冒泡排序，每次交换都是跳跃式的。每次排序的时候设置一个基准点(一般是第一个数字)，将小于基准点的数全部放到基准点的左边，将大于基准点的数全部放到基准点的右边，这样在每次交换的时候就不会像冒泡排序一样只能在相邻的数之间进行交换，交换的距离要大得多，因此总的比较和交换次数就少了。当然最坏的情况下仍可能是相邻的两个数进行交换

最差时间复杂度：O(N^2)

平均时间复杂度：O(NlogN)
 
注意：只要是涉及到数组排序的，最好是使用PHP内置的sort、rsort、asort、ksort、arsort、krsort函数即可实现数组排序
 
### 代码
3_QuickSort_v1.php
```
<?php

// 需要排序的数组
$array = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8];

QuickSort($array);
var_dump($array);

/**
 * 快速排序
 * @param array $arr
 */
function QuickSort(array &$arr)
{
    $left = 0;
    $right = count($arr) - 1;
    QSort($arr, $left, $right);
}

/**
 * @param $array
 * @param $left
 * @param $right
 */
function QSort(array &$array, $left, $right)
{
    if ($left >= $right) {
        return;
    }

    // 将$array一分为二，获取基准数的位置并回归
    $pivot = Partition($array, $left, $right);

    // 对基准数的左边进行递归排序
    QSort($array, $left, $pivot - 1);

    // 对基准数的右边进行递归排序
    QSort($array, $pivot + 1, $right);
}

/**
 * 选取数组当中的一个关键字作为基准数，使得它处于数组某个位置时，左边的值比它小，右边的值比它大，该关键字叫做枢轴/基准数，使枢轴/基准数记录到位，并返回其所在位置
 * @param array $array
 * @param $left int 左边第一个元素下标
 * @param $right int 右边（最后）第一个元素下标
 * @return int
 */
function Partition(array &$array, $left, $right)
{
    // 选取子数组第一个元素作为枢轴/基准数
    $pivot = $array[$left];

    // 记录第一个元素的下标
    $first = $left;

    while ($left < $right) {
        // $j从最右边往左边开始找，大于基准数$temp的话则继续往左边走
        while ($left < $right && $array[$right] >= $pivot) {
            $right--;
        }

        // $i从左边往右边找，小于基准数$temp的话则继续往右边走
        while ($left < $right && $array[$left] <= $pivot) {
            $left++;
        }

        // 当$i和$j没有相遇的时候则交换两者的位置
        if ($left < $right) {
            $t = $array[$left];
            $array[$left] = $array[$right];
            $array[$right] = $t;
        }
    }

    // 将基准数归位
    $array[$first] = $array[$left];
    $array[$left] = $pivot;

    // 返回$right也行，毕竟最后$left和$right都是停留在pivot下标处
    return $left;
}
```

上面的代码可以进行简化：

3_QuickSort_v2.php
```
<?php
/**
 * 快速排序
 *
 * 思想：主要采用了递归和分治的思想。选择标尺后，进行遍历数组，将大于标尺的放到一个数组，将小于标尺的放置到一个数组。再递归调用本函数并记录结果。
 *
 * 最差时间复杂度：O(N^2)
 * 平均时间复杂度：O(NlogN)
 */

// 需要排序的数组
$array = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8];

$res = QuickSort($array);
print_r($res);

/**
 * 快速排序
 * @param array $arr
 * @return array
 */
function QuickSort($arr)
{
    // 先判断是否需要继续进行
    $length = count($arr);
    if ($length <= 1) {
        return $arr;
    }

    // 选择一个标尺,通常选择第一个元素
    $base_num = $arr[0];

    // 小于标尺的
    $left = [];

    // 大于标尺的
    $right = [];

    for ($i = 1; $i < $length; $i++) {
        if ($base_num > $arr[$i]) {
            $left[] = $arr[$i];
        } else {
            $right[] = $arr[$i];
        }
    }

    // 递归调用并记录
    $left = QuickSort($left);
    $right = QuickSort($right);

    // 合并
    return array_merge($left, [$base_num], $right);
}

```

## 4. 桶排序
### 原理
原理是将数组分到有限数量的桶子里

假设待排序的数组array中共有N个整数，并且已知数组array中数据的范围[0, MAX)。在桶排序时，创建容量为MAX的桶数组bucket，并将桶数组元素都初始化为0；将容量为MAX的桶数组中的每一个单元都看作一个"桶"。
在排序时，逐个遍历数组a，将数组a的值，作为"桶数组r"的下标。当array中数据被读取时，就将桶的值加1。

例如，读取到数组array[3]=5，则将bucket[5]的值+1

时间复杂度：O(MAX+N)
空间复杂度：MAX

注意：只要是涉及到数组排序的，最好是使用PHP内置的sort、rsort、asort、ksort、arsort、krsort函数即可实现数组排序

### 代码
4_BucketSort.php
```
<?php

// 需要排序的数组
$array = [10, 8, 7, 5, 2, 5, 10, 7, 5, 13, 10];

// 数组的最大值
$max = max($array);

// 设置一个桶数组，长度为需要排序数组的最大值，并且初始化都为0
$bucket = array_fill(0, $max + 1, 0);

// 遍历需排序的数组，对桶数组的值进行递增
foreach ($array as $value) {
    $bucket[$value]++;
}

// 从小到大输出桶数组的值
foreach ($bucket as $key=>$value) {
    for ($i = 1; $i <= $value; $i++) {
        echo $key . ' ';
    }
}

// 输出：
// 2 5 5 5 7 7 8 10 10

```

## 5. 梳排序
### 思想
思想：梳排序改良自冒泡排序和快速排序，梳排序比较的是固定距离处的数的比较和交换，类似希尔那样。是一种不稳定的排序算法。冒泡排序中，只比较相邻的两个数，即比较的二项的间距Gap是1，梳排序的改进是该间距可以大于1，是取希尔排序中的观点。

梳排序中，开始时的间距设定为阵列长度，并在循环中以固定比率递减，通常递减率设定为1.3。在一次循环中，梳排序如同泡沫排序一样把阵列从首到尾扫描一次，比较及交换两项，不同的是两项的间距不固定于1。如果间距递减至1，梳排序假定输入阵列大致排序好，并以冒泡排序作最后检查及修正
### 代码
5_CombSort.php
```
<?php

// 需要排序的数组
$array = [10, 8, 7, 5, 2, 5, 10, 7, 5, 13, 10];
$res = CombSort($array);
print_r($res);

/**
 * 梳排序
 * @param $arr
 * @return mixed
 */
function CombSort($arr)
{
    // 数组的元素个数
    $length = count($arr);

    // 递减率，原作者以随机数作实验，得到最有效递减率为1.3的。如果此比率太小，则导致一循环中有过多的比较，如果比率太大，则未能有效进行交换
    $rate = 1.3;

    // 间距
    $step = (int)floor($length / $rate);

    // 进行每一次的递减循环
    while ($step >= 1) {
        for ($i = 0; $i < $length; $i++) {
            // 如果数组第i个的值大于数组的第i+step个的值，则交换
            if ($i + $step < $length && $arr[$i] > $arr[$i + $step]) {
                // 交换两个的值
                $temp = $arr[$i];
                $arr[$i] = $arr[$i + $step];
                $arr[$i + $step] = $temp;
            }

            if ($i + $step > $length) {
                break;
            }
        }
        // 间距递减
        $step = (int)floor($step / 1.3);
    }
    return $arr;
}
```

## 6. 计数排序
计数排序是一个非基于比较的排序算法，类似于桶排序的线性时间排序算法。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。当然这是一种牺牲空间换取时间的做法，而且当O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(n*log(n)), 如归并排序，堆排序）

### 思想
对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数 。一旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上。它创建一个长度为这个数据范围的数组C，C中每个元素记录要排序数组中对应记录的出现个数，比如，要排序的数为 7 4 2 1 5 3 1 5，则比7小的有7个数，所有7应该在排序好的数列的第八位

假设要排序的数组为 A = [1,0,3,1,0,1,1] 这里最大值为3，最小值为0，那么我们创建一个数组C，长度为4。然后一趟扫描数组A，得到A中各个元素的总数，并保持到数组C的对应单元中。比如0 的出现次数为2次，则 C[0] = 2;1 的出现次数为4次，则C[1] = 4。由于C 是以A的元素为下标的，所以这样一做，A中的元素在C中自然就成为有序的了，这里我们可以知道 顺序为 0,1,3 (2 的计数为0)，然后我们把这个在C中的记录按每个元素的计数展开到输出数组B中，排序就完成了

这种排序算法，依靠一个辅助数组来实现，不基于比较，但由于要一个辅助数组C，所以空间复杂度要大一些，由于计算机的内存有限，所以这种算法不适合范围很大的数的排序

### 步骤
* 1.找出待排序的数组中最大和最小的元素
* 2.统计数组中每个值为i的元素出现的次数，存入数组C的第i项
* 3.对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
* 4.反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个 元素就将C(i)减去1

代码

6_CountingSort.php
```
<?php

// 需要排序的数组
$array = [10, 8, 7, 5, 2, 5, 10, 7, 5, 13, 10];
$res = CountingSort($array);
print_r($res);

/**
 * 计数排序
 * @param $arr
 * @return mixed
 */
function CountingSort($arr)
{
    // 数组的元素个数
    $length = count($arr);

    if ($length <= 1) {
        return $arr;
    }

    // 数组的最大值
    $max = max($arr);

    // 数组的最小值
    $min = min($arr);

    // 设置一个计数数组，用来储存元素出现次数的数组，长度为需要排序数组的最大值，并且初始化都为0
    $time_arr = array_fill($min, $max - $min + 1, 0);

    // 统计每个元素出现次数并保存到计数数组中
    foreach ($arr as $value) {
        $time_arr[$value]++;
    }

    // 相邻的两个值相加，即对所有的计数累加
    for ($i = $min + 1; $i <= $max; $i++) {
        $time_arr[$i] += $time_arr[$i - 1];
    }

    // 逆向遍历源数组（保证稳定性），根据计数数组中对应的值填充到先的数组中
    for ($i = $length - 1; $i >= 0; $i--) {
        $result[$time_arr[$arr[$i]]] = $arr[$i];

        // 前一个数找到位置后，那么和它值相同的数位置往前一步
        $time_arr[$arr[$i]]--;
    }

    // 整理数组
    ksort($result);

    return $result;
}
```

## 7. 插入排序
### 思路
插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间

### 步骤
* <1>.从第一个元素开始，该元素可以认为已经被排序；
* <2>.取出下一个元素，在已经排序的元素序列中从后向前扫描；
* <3>.如果该元素（已排序）大于新元素，将该元素移到下一位置；
* <4>.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
* <5>.将新元素插入到该位置后；
* <6>.重复步骤2~5。

代码

7_InsertSort.php
```
<?php
// 需要排序的数组
$array = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8];

$res = InsertSort($array);
print_r($res);

/**
 * 插入排序
 * @param $arr
 * @return array
 */
function InsertSort($arr)
{
    $length = count($arr);
    if ($length <= 1) {
        return $arr;
    }
    for ($i = 1; $i < $length; $i++) {
        $tmp = $arr[$i];
        // 内层循环控制，比较并插入
        for ($j = $i - 1; $j >= 0; $j--) {
            // 发现插入的元素要小，交换位置，将后边的元素与前面的元素互换
            if ($tmp < $arr[$j]) {
                $arr[$j + 1] = $arr[$j];
            } else {
                // 如果碰到不需要移动的元素，由于是已经排序好是数组，则前面的就不需要再次比较了
                break;
            }
        }
        $arr[$j + 1] = $tmp;
        print_r($arr);
    }
    return $arr;
}
```