<?php
class Sort{
/**
* 一挂谍、冒泡排序：
* 思路：
* 1. 循環(huán) n-1 個位置，對于每個位置 i迷帜，都和 [i+1,n] 的每個位置 j 上的數(shù)對比
* 2. 如果位置 i 上的數(shù)大于（小于）位置 j 上的數(shù)输吏，交換這兩個位置上的數(shù)
* 3. 使得對比完成后权旷，第 i 個位置上存放了第 i 小（大）的數(shù)
* 分析：
* 1. 時間復(fù)雜度 O(n^2)贯溅，空間復(fù)雜度 O(1)
* 2. 由于大小相同的數(shù)并沒有交換位置拄氯，因此屬于：穩(wěn)定排序
* @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 的待排序數(shù)組它浅，將數(shù)組分為兩部分：排好序的和未排好序的坤邪，即：(1, i) 和 (i+1, n)
* 2. 選擇排序過程是：不斷增大排序好的部分，減小未排序號的部分罚缕，直接全部排序好。
* 3. 不斷增大排序好的部分的過程是：每次從未排好序的部分中怎静，選擇最杏实（最大）的一個，放在排好序的部分的末尾蚓聘，也是未排好序的部分的開頭
* 4. 與冒泡排序不同的是：在不斷增大排序好的部分的過程中腌乡，交換只發(fā)生一次，即：未排好序的第一個位置和未排好序本分的最幸鼓怠（最大）的位置交換与纽。
* 分析：
* 1. 時間復(fù)雜度 O(n^2)，空間復(fù)雜度 O(1)
* 2. 由于大小相同的數(shù)并沒有交換位置塘装，因此屬于：穩(wěn)定排序
* @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 的待排序數(shù)組分成：已排序的 (1, i) 和 未排序的 (i+1, n)
* 2. 對于未排序部分中的第一個元素，在已排序的部門中蹦肴，找到一個合適的位置
* 3. 將已排序部門中這個位置及以后的元素后移一位僚碎，然后將未排序部分中的第一個元素放在這個位置
* 4. 增加已排序部門的長度，縮短未排序排序的長度阴幌，直到未排序部門長度為0
* 分析：
* 1. 時間復(fù)雜度 O(n^2)勺阐，空間復(fù)雜度 O(1)
* 2. 穩(wěn)定排序卷中。即：大小相同的數(shù)從未排序部門轉(zhuǎn)移到已經(jīng)排序部分的過程中，未改變其相對位置渊抽。
* @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;
}
/**
* 四蟆豫、希爾排序
* 希爾排序是基于插入排序優(yōu)化過后的、一種時間復(fù)雜度小于 O(n^2) 的插入排序
* 思路：
* 1. 將整個待排序數(shù)組進行分組懒闷，每次保證：組內(nèi)有序
* 2. 不斷的縮短《每組》的長度十减，直到為 1，即：完成排序毛雇。
* 3. 依舊使用插入排序的排序方法：計算待排序元素的位置嫉称，后移這個位置及以后的元素，將待排序元素放到這個位置上灵疮，直到待排序部分的長度為 0
* 分析：
* 1. 時間復(fù)雜度 O(nlog2n)织阅，空間復(fù)雜度 O(1)
* * while1 - for1 - while2
* * while1 的時間復(fù)雜度是 O(log2n)
* * for1 - while2 的時間復(fù)雜度是：n/2 + 3n/4*3 + 7n/8 * 7，即：O(n)
* 2. 不穩(wěn)定震捣。相等元素分到不同組后荔棉，排序過程打亂了原本的相對位置
* @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 的待排序數(shù)組蒿赢，分為兩個長度為 n/2 的子數(shù)組润樱，當(dāng)子數(shù)組長度為 1 時，不再二分（遞歸）
* 2. 保證每個子數(shù)組有序后羡棵，合并成一個大數(shù)組
* 3. 合并兩個有序的子數(shù)組成為一個有序的大數(shù)組壹若，思路是：
* * 分別記錄兩個子數(shù)組的待合并元素位置
* * 當(dāng)其中一個子數(shù)組中的元素全部合入大數(shù)組時，直接合并另外一個子數(shù)組中的元素
* * 當(dāng)兩個子數(shù)組都還有元素未合入大數(shù)組時皂冰，取兩個子數(shù)組待合入元素中較械暾埂（升序）或者較大（降序）排列
* @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. 找到一個基準(zhǔn)值（數(shù)組第一個元素）秃流，將所有元素分成兩組赂蕴，使得左邊的元素都比基準(zhǔn)值小，右邊的元素都比基準(zhǔn)值大
* 2. 以基準(zhǔn)值的位置為分隔點舶胀，將左右兩邊的子數(shù)組進行相同操作概说，直到子數(shù)組的長度為 1，表示所有元素都已經(jīng)有序
* 3. 尋找基準(zhǔn)值得位置嚣伐，且使得：基準(zhǔn)值位置左邊的元素小于基準(zhǔn)值糖赔，基準(zhǔn)值位置右邊的元素大于基準(zhǔn)值
* * 以第一個元素為基準(zhǔn)值
* * 以第二個元素為左邊第一個元素，以最后一個元素作為右邊第一個元素
* * 左邊指針不斷右移轩端，直到指針位置上的元素大于（小于）基準(zhǔn)值
* * 右邊指針不斷左移挂捻，直到指針位置上的元素小于（大于）基準(zhǔn)值
* * 交換左邊指針和右邊指針上的元素
* * 直到左邊指針和右邊指針重合，此時已經(jīng)：左邊全小于，右邊全大于
* * 此時的左指針或者右指針即為基準(zhǔn)值的位置刻撒，交換第一個元素和基準(zhǔn)值位置上的元素
* 分析：
* 1. 時間復(fù)雜度 O(nlog2n)骨田，空間復(fù)雜度 O(log2n)
* 2. 不穩(wěn)定
* 3. 遞歸的層級是 log2n
* 4. while - while1 - while2 - swap: 時間復(fù)雜度為 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
)
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
