图片3.jpg
图片4.jpg
插入排序
它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
-----维基百科
function insertion_sort($data){
$count = count($data)-1;
for($i = 0; $i<$count; $i++){
for($j = $i; $j>=0 && $data[$j+1] < $data[$j]; $j--){
list($data[$j], $data[$j+1]) = array($data[$j+1], $data[$j]);
}
}
return $data;
}
此算法最坏的时间复杂度是O(n^2)
冒泡排序
它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成
-----维基百科
function bubble_sort(&$data){
$count = count($data);
for($i = 0; $i<$count; $i++){
for($j = 0; $j<$count-1 - $i; $j++){
if ($data[$j+1] > $data[$j]){
list($data[$j], $data[$j+1]) = array($data[$j+1], $data[$j]);
}
}
}
return $data;
}
选择排序
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
-----维基百科
function selection_sort($data){
$count = count($data)-1;
for($i = 0; $i<$count; $i++){
for($j = $i+1; $j<=$count; $j++){
if ($data[$i] < $data[$j]){
list($data[$i], $data[$j]) = array($data[$j], $data[$i]);
}
}
}
return $data;
}
快速排序
使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。
步骤为：
1、从数列中挑出一个元素，称为"基准"（pivot），
2、重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3、递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
-----维基百科
function quick_sort($data){
$length = array_count($data);
if ($length <= 1){
return $data;
}
$mid_index = $length >> 1;
$mid_value = $data[$mid_index];
$left = $right = [];
for($i = 0; $i<$length; $i++){
if ($i == $mid_index){
continue;
}
if ($data[$i] < $mid_value){
$left[] = $data[$i];
} else {
$right[] = $data[$i];
}
}
return array_merge(quick_sort($left), (array)$mid_value, quick_sort($right));
}
