本文章主要介绍常见的一些排序算法，并进行分析
插入排序
原理跟扑克牌的每次插入一张牌到合适位置类似，适合小规模的，初始数据几乎有序的数据排序。插入排序和冒泡排序类似：只和相邻的元素比（文章底部有一个不是和相邻元素比较的排序算法）。两种算法的代码非常相似。
最好的情况（完全正序），时间复杂度为：O(n)；最坏的情况（完全逆序），时间复杂度为：O(n^2)
插入排序和冒泡排序的区别在于：插入排序是将一个元素插入到一个已经排序好了的队列中；而冒泡排序是每次冒泡（每个内循环）都产生了一个“最大的泡”（元素），直到所有气泡按照顺序冒完。
PHP代码：
function insertSort($data) {
for ($i = 1, $len = count($data); $i < $len; $i++) {
$cursor = $data[$i];
for ($j = $i - 1; $j >= 0; $j--) {
if ($cursor < $data[$j]) {
$temp = $data[$j];
$data[$j] = $cursor;
$data[$j+1] = $temp;
}
}
}
return $data;
}
快速排序
快速排序跟中值排序相类似：拿一个元素出来，然后其余的小余它的放到一个数组里，大于它的放另外一个数组里，然后对这新的两个数组继续执行相同的操作，最后把这小余的、第一个元素、大于的连接起来，结果就是排序好了的数组。算是最好理解的一个排序算法了。
function quickSort($arr) {
$len = count($arr);
if ($len <= 1) {
return $arr;
}
$baseNum = $arr[0];
$leftArr = $rightArr = [];
for ($i = 1; $i < $len; $i++) {
if ($baseNum >= $arr[$i]) {
$leftArr[] = $arr[$i];
} else if ($baseNum < $arr[$i]) {
$rightArr[] = $arr[$i];
}
}
$leftArr = quickSort($leftArr);
$rightArr = quickSort($rightArr);
return array_merge($leftArr, [$baseNum], $rightArr);
}
选择排序
选择第一个元素，暂时认为是最小的元素，用他和剩余的元素比较，如果发现有比他小的，则认为这个元素是最小的，然后用这个“最小的”继续和剩余的比较，直到真正“最小的”找出来后，用它交换第一个元素的位置，这样第一个内层循环结束。然后用第二个元素继续执行相同的比较，最后所有元素就慢慢的从小到大排序好了。
选择排序和插入排序的区别是：（在内层循环中）选择排序如果发现比“自己”更小的元素时，不会立即交换数据，只是记录一下更小元素，然后用更小元素和剩余的元素比，直到最小元素（当前循环是最小的）找到之后才交换位置；并且插入排序是用一个元素和已经排序了的数组比较，而选择排序是用排序好了的数组里面的最大的那个（矮子里面挑高个），和未排序的数组比较。
/**
* 选择排序
*
* 外层循环控制比较的轮数，内层控制当前的元素($arr[$i])为这一轮最小的元素
*
* @param $arr
* @return mixed
*/
function selectSort($arr) {
for ($i = 0, $len = count($arr); $i < $len - 1; $i++) {
$p = $i; // 假定$i是当前最小元素的下标
for ($j = $i+1; $j < $len; $j++) {
if ($arr[$j] < $arr[$p]) { // 遇到比$i更小的元素，修改p为新的坐标
$p = $j;
}
}
if ($p !== $i) { // 坐标被修改，说明有比$i更小的元素，于是交换他们的位置
$temp = $arr[$i];
$arr[$i] = $arr[$p];
$arr[$p] = $temp;
}
}
return $arr;
}
冒泡排序
每次冒出最大的元素，然后次大的，然后次次大的，直到最后一个为止。冒泡排序和选择排序有什么区别呢？似乎和上面的每次取出最小一样没什么区别，其实不然，选择排序是用基准元素和所有元素比小并交换两者的位置，冒泡主要是相邻两者相比，如果左边的数字比右边的大，那么交换他们的位置，然后再用这个大的数字和他的右边比较，直到把最大的一个数字排到右边为止（完成了一轮，剩下的继续冒泡）。
function bubbleSort($arr) {
for ($i = 1, $len = count($arr); $i < $len; $i++) {
for ($j = 0; $j < $len - $i; $j++) {
if ($arr[$j] > $arr[$j+1]) {
$temp = $arr[$j];
$arr[$j] = $arr[$j+1];
$arr[$j+1] = $temp;
}
}
}
}
分析另外一个算法
来源：https://www.v2ex.com/t/287163
$len = count($arr);
for ($i = 1; $i < $len; $i++) {
for ($j = 0; $j < $i; $j++) {
if ($arr[$i] < $arr[$j]) {
$temp = $arr[$i];
$arr[$i] = $arr[$j];
$arr[$j] = $temp;
}
}
}
对于这是什么排序，网友们进行了激烈的争论。
经过自己的一番分析，应该算是插入排序，跟上面的插入排序代码稍微有些区别在于，上面的插入排序代码在每个内层循环里是用当前最后一个元素和前面的所有元素比小，但是比较的顺序是从右往左。而本算法是在内层循环里，用当前最后一个元素和前面所有元素比小，比较的顺序是从左往右，虽然这个插入排序算法不是比较临近两个元素，但是实际上还是比较了的。
