<?php
class Sort{
/**
* 一、冒泡排序：
* 思路：
* 1. 循环 n-1 个位置，对于每个位置 i，都和 [i+1,n] 的每个位置 j 上的数对比
* 2. 如果位置 i 上的数大于（小于）位置 j 上的数，交换这两个位置上的数
* 3. 使得对比完成后，第 i 个位置上存放了第 i 小（大）的数
* 分析：
* 1. 时间复杂度 O(n^2)，空间复杂度 O(1)
* 2. 由于大小相同的数并没有交换位置，因此属于：稳定排序
* @param array $data
* @return array
*/
public static function bubbleSort(&$data=[]){
if(!is_array($data)){
return $data;
}
$data_size = count($data);
if(0 == $data_size){
return $data;
}
for($i=0; $i<$data_size-1; $i++){
for($j=$i+1; $j<$data_size; $j++){
if($data[$i] > $data[$j]){
$temp = $data[$i];
$data[$i] = $data[$j];
$data[$j] = $temp;
}
}
}
return $data;
}
/**
* 二、选择排序：
* 思路：
* 1. 对于长度为 n 的待排序数组，将数组分为两部分：排好序的和未排好序的，即：(1, i) 和 (i+1, n)
* 2. 选择排序过程是：不断增大排序好的部分，减小未排序号的部分，直接全部排序好。
* 3. 不断增大排序好的部分的过程是：每次从未排好序的部分中，选择最小（最大）的一个，放在排好序的部分的末尾，也是未排好序的部分的开头
* 4. 与冒泡排序不同的是：在不断增大排序好的部分的过程中，交换只发生一次，即：未排好序的第一个位置和未排好序本分的最小（最大）的位置交换。
* 分析：
* 1. 时间复杂度 O(n^2)，空间复杂度 O(1)
* 2. 由于大小相同的数并没有交换位置，因此属于：稳定排序
* @param $data
* @return array
*/
public static function selectionSort(&$data){
if(!is_array($data)){
return $data;
}
$data_size = count($data);
if(0 == $data_size){
return $data;
}
for($i=0; $i<$data_size-1; $i++){
$min_index = $i;
for($j=$i+1; $j<$data_size; $j++){
if($data[$min_index] > $data[$j]){
$min_index = $j;
}
}
if($min_index != $i){
$temp = $data[$i];
$data[$i] = $data[$min_index];
$data[$min_index] = $temp;
}
}
return $data;
}
/**
* 三、插入排序：
* 思路：
* 1. 还是将长度为 n 的待排序数组分成：已排序的 (1, i) 和 未排序的 (i+1, n)
* 2. 对于未排序部分中的第一个元素，在已排序的部门中，找到一个合适的位置
* 3. 将已排序部门中这个位置及以后的元素后移一位，然后将未排序部分中的第一个元素放在这个位置
* 4. 增加已排序部门的长度，缩短未排序排序的长度，直到未排序部门长度为0
* 分析：
* 1. 时间复杂度 O(n^2)，空间复杂度 O(1)
* 2. 稳定排序。即：大小相同的数从未排序部门转移到已经排序部分的过程中，未改变其相对位置。
* @param $data
* @return array
*/
public static function insertionSort(&$data){
if(!is_array($data)){
return $data;
}
$data_size = count($data);
if(0 == $data_size){
return $data;
}
for($i=0; $i<$data_size-1; $i++){
$new_item = $data[$i + 1];
$ins_index = $i;
while($ins_index >= 0 && $new_item < $data[$ins_index]){
$data[$ins_index + 1] = $data[$ins_index];
$ins_index = $ins_index - 1;
}
$data[$ins_index+1] = $new_item;
}
return $data;
}
/**
* 四、希尔排序
* 希尔排序是基于插入排序优化过后的、一种时间复杂度小于 O(n^2) 的插入排序
* 思路：
* 1. 将整个待排序数组进行分组，每次保证：组内有序
* 2. 不断的缩短《每组》的长度，直到为 1，即：完成排序。
* 3. 依旧使用插入排序的排序方法：计算待排序元素的位置，后移这个位置及以后的元素，将待排序元素放到这个位置上，直到待排序部分的长度为 0
* 分析：
* 1. 时间复杂度 O(nlog2n)，空间复杂度 O(1)
* * while1 - for1 - while2
* * while1 的时间复杂度是 O(log2n)
* * for1 - while2 的时间复杂度是：n/2 + 3n/4*3 + 7n/8 * 7，即：O(n)
* 2. 不稳定。相等元素分到不同组后，排序过程打乱了原本的相对位置
* @param $data
* @return array
*/
public static function shellSort(&$data){
if(!is_array($data)){
return $data;
}
$data_size = count($data);
if(0 == $data_size){
return $data;
}
$gap = intval($data_size / 2);
while($gap > 0){
for($i=$gap; $i<$data_size; $i++){
$temp = $data[$i];
$ins_index = $i - $gap;
while($ins_index >= 0 && $data[$ins_index] > $temp){
$data[$ins_index + $gap] = $data[$ins_index];
$ins_index -= $gap;
}
$data[$ins_index + $gap] = $temp;
}
$gap = intval($gap / 2);
}
return $data;
}
/**
* 五、归并排序
* 思路：
* 1. 将长度为 n 的待排序数组，分为两个长度为 n/2 的子数组，当子数组长度为 1 时，不再二分（递归）
* 2. 保证每个子数组有序后，合并成一个大数组
* 3. 合并两个有序的子数组成为一个有序的大数组，思路是：
* * 分别记录两个子数组的待合并元素位置
* * 当其中一个子数组中的元素全部合入大数组时，直接合并另外一个子数组中的元素
* * 当两个子数组都还有元素未合入大数组时，取两个子数组待合入元素中较小（升序）或者较大（降序）排列
* @param $data
* @return array
*/
public static function mergeSort(&$data){
if(!is_array($data)){
return $data;
}
$data_size = count($data);
if(1 >= $data_size){
return $data;
}
$half_size = intval($data_size / 2);
$data_left = array_slice($data, 0, $half_size);
$data_right = array_slice($data, $half_size, $data_size-$half_size);
return self::merge(self::mergeSort($data_left), self::mergeSort($data_right));
}
private static function merge($left, $right){
$data = [];
$li = $ri = 0;
for($i=0; $i<count($left)+count($right); $i++){
if($li >= count($left)){
$value = $right[$ri++];
}else if($ri >= count($right)){
$value = $left[$li++];
}else if($left[$li] < $right[$ri]){
$value = $left[$li++];
}else{
$value = $right[$ri++];
}
$data[$i] = $value;
}
return $data;
}
/**
* 六、快速排序
* 思路：
* 1. 找到一个基准值（数组第一个元素），将所有元素分成两组，使得左边的元素都比基准值小，右边的元素都比基准值大
* 2. 以基准值的位置为分隔点，将左右两边的子数组进行相同操作，直到子数组的长度为 1，表示所有元素都已经有序
* 3. 寻找基准值得位置，且使得：基准值位置左边的元素小于基准值，基准值位置右边的元素大于基准值
* * 以第一个元素为基准值
* * 以第二个元素为左边第一个元素，以最后一个元素作为右边第一个元素
* * 左边指针不断右移，直到指针位置上的元素大于（小于）基准值
* * 右边指针不断左移，直到指针位置上的元素小于（大于）基准值
* * 交换左边指针和右边指针上的元素
* * 直到左边指针和右边指针重合，此时已经：左边全小于，右边全大于
* * 此时的左指针或者右指针即为基准值的位置，交换第一个元素和基准值位置上的元素
* 分析：
* 1. 时间复杂度 O(nlog2n)，空间复杂度 O(log2n)
* 2. 不稳定
* 3. 递归的层级是 log2n
* 4. while - while1 - while2 - swap: 时间复杂度为 n
* @param array $data
* @param int $left
* @param bool $right
* @return array|void
*/
public static function quickSort(&$data=[], $left=0, $right=false){
if(!is_array($data)){
return $data;
}
if(false === $right){
$right = count($data) - 1;
}
if($left >= $right){
return ;
}
$base = $data[$left];
$i = $left+1;
$j = $right;
while(true){
while($i <= $j && $data[$i] <= $base){
$i++;
}
while($i <= $j && $data[$j] >= $base){
$j--;
}
if($i >= $j){
break;
}
$temp = $data[$i];
$data[$i] = $data[$j];
$data[$j] = $temp;
}
$data[$left] = $data[$j];
$data[$j] = $base;
self::quickSort($data, $left, $j-1);
self::quickSort($data, $j+1, $right);
return $data;
}
}
$data = $data1 = $data2 = $data3 = $data4 = $data5 = $data6 = [1, 3, 5, 7, 9, 0, 2, 4, 6, 8];
echo 'data before sort: '.PHP_EOL;
print_r($data);
echo 'sorted by bubble: '.PHP_EOL;
print_r(Sort::bubbleSort($data1));
echo 'sorted by selection: '.PHP_EOL;
print_r(Sort::selectionSort($data2));
echo 'sorted by insertion: '.PHP_EOL;
print_r(Sort::insertionSort($data3));
echo 'sorted by shell: '.PHP_EOL;
print_r(Sort::shellSort($data4));
echo 'sorted by merge: '.PHP_EOL;
print_r(Sort::mergeSort($data5));
echo 'sorted by quick: '.PHP_EOL;
print_r(Sort::quickSort($data6));
php Sort.php
data before sort:
Array
(
[0] => 1
[1] => 3
[2] => 5
[3] => 7
[4] => 9
[5] => 0
[6] => 2
[7] => 4
[8] => 6
[9] => 8
)
sorted by bubble:
Array
(
[0] => 0
[1] => 1
[2] => 2
[3] => 3
[4] => 4
[5] => 5
[6] => 6
[7] => 7
[8] => 8
[9] => 9
)
sorted by selection:
Array
(
[0] => 0
[1] => 1
[2] => 2
[3] => 3
[4] => 4
[5] => 5
[6] => 6
[7] => 7
[8] => 8
[9] => 9
)
sorted by insertion:
Array
(
[0] => 0
[1] => 1
[2] => 2
[3] => 3
[4] => 4
[5] => 5
[6] => 6
[7] => 7
[8] => 8
[9] => 9
)
sorted by shell:
Array
(
[0] => 0
[1] => 1
[2] => 2
[3] => 3
[4] => 4
[5] => 5
[6] => 6
[7] => 7
[8] => 8
[9] => 9
)
sorted by merge:
Array
(
[0] => 0
[1] => 1
[2] => 2
[3] => 3
[4] => 4
[5] => 5
[6] => 6
[7] => 7
[8] => 8
[9] => 9
)
sorted by quick:
Array
(
[0] => 0
[1] => 1
[2] => 2
[3] => 3
[4] => 4
[5] => 5
[6] => 6
[7] => 7
[8] => 8
[9] => 9
)
