冒泡、选择、插入、快速排序算法小解
假设待排序数组$arr=array(9,5,3,6,7,1);（从小到大排序）
1、冒泡排序
冒泡排序的思想是每一趟找出最大的那个（最大的泡泡），经过count($arr)-1趟，得出最后的顺序
因为要得到最大的那个数，所以需要两层循环，外层表示进行的趟数，内层循环来进行比较、交换
即第一趟5,3,6,7,1,9
第二趟5,3,6,1,7,9
第三趟5,3,1,6,7,9
第四趟3,1,5,6,7,9
第五趟1,3,5,6,7,9
故代码为
function bubble_sort($arr){
for($i=0;$i<count($arr)-1;$i++){
for($j=0;$j<count($arr)-$i;$j++){//因为每走一趟，最大的已经在最后面，所以要减去躺数（$i）
if($arr[$j]>$arr[$j+1]){
$temp = $arr[$j];
$arr[$j] = $arr[$j+1];
$arr[$j+1] = $temp;
}
}
}
return $arr;
}
2、选择排序（打擂）
初始序列：{9 5 3 6 7 1}
第一趟1 {5 3 6 7 9} 9和1交换
第二趟1 3 {5 6 7 9} 5和3交换
第三趟1 3 5 { 6 7 9} 5不动
第四趟1 3 5 6 { 7 9} 6不动
第五趟1 3 5 6 7 {9} 7不动（完成）
选择排序的思想是先让9和其余数字进行比较，找出最小的，和9互换位置，然后让5和其余数字进行比较，找出最小的，互换位置，以此类推，直到最后两个数字比较完成后，就得到了排序完成的数组
用打擂的方式理解就是10个座位，分别对应十个人，先让第一个人和其余人比武，选出第一名，并交换位置（排名赛），然后第二个人和其余人比武，以此类推。。。
可以得出代码
function select_sort($arr){
for($i=0;$i<count($arr)-1;$i++){
$m = $i;//记录当前位置（没有交换之前）
for($j=$i+1;$j<count($arr)-1-$i;$i++){//$j=$i+1，实现第i个人和它后面的每个人比较
if($arr[$i]>$arr[$j]){
$m = $j;//记录循环比较完后（最大）的位置
}
}
if($i != $m){
$temp = $arr[$i];
$arr[$i] = $arr[$m];
$arr[$m] = $temp;
}
}
}
3、插入排序
初始序列 9 5 3 6 7 1
第一趟 [9] 5 3 6 7 1
第二趟 [5 9] 3 6 7 1
第三趟 [3 5 9] 6 7 1
第四趟 [3 5 6 9] 7 1
第五趟 [3 5 6 7 9] 1
第六趟 [1 3 5 6 7 9]
插入排序的思想是将未排序的数组插入到已经排好序的数组中（将数组中第一个元素作为初始的有序列表），和冒泡排序类似，需要和已排序的数组中的元素进行比较，确定插入元素的位置
代码为
function insert_sort($arr){
for($i=1;$i<count($arr);$i++){
$temp = $arr[$i];//获取当前需要插入到有序列表的元素
for($j=$i-1;$j>=0;$j--){
if($temp<$arr[$j]){
$arr[$j] = $arr[$j+1];
$arr[$j+1] = $temp;
}else{
break;
}
}
}
}
4、快速排序
快速排序的思想是先取出数组的第一个元素，和其余元素一一进行比较，得出两个数组，一个数组中的元素都小于它，另一个数组元素都大于它；然后分别对这两个数组继续使用这个函数（递归思想），得出排好序的数组
代码为
function quick_sort($arr){
$key = $arr[0];
$left = array();
$right = array();
for($i=1;$i<count($arr);$i++){
if($arr[$i]<$key){
$left[] = $arr[$i];
}else{
$right = $arr[$i];
}
}
$left = quick_sort($left);
$right = quick_sort($right);
return array_merge($left,array($key),$right);
}
时间复杂度算法：
1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，只保留高阶项。
3、如果最高阶项存在且不是1，则去除与这个项相乘的常数。
例如：
1 int n = 100000; //执行了1次
2 for(int i = 0; i < n; i++){ //执行了n+1次
3 for(int j = 0; j < n; j++) //执行了n*(n+1)次
4 {
5 printf("i = %d, j = %d", i, j); //执行了n*n次
6 }
7 }
8
9 for(int i = 0; i < n; i++){ //执行了n+1次
10 printf("i = %d", i); //执行了n次
11 }
12
13 printf("Done"); //执行了1次
按上面推导"大O阶"的步骤我们先来第一步："用常数1取代运行时间中的所有加法常数"，则上面的算式变为:
执行总次数 = 2n^2 + 4n + 1;
第二步："在修改后的运行次数函数中，只保留最高阶项"，这里的最高阶项是n的二次方
所以算式变为：
执行总次数 = 2n^2;
第三步："如果最高阶项存在且不是1，则去除与这个项相乘的常数"，这里n的二次方不是1所以
要去除这个项相乘的常数算式变为:
执行总次数 = n^2;
因此，最后我们得到上面的那段代码的算法时间复杂度表示为: O(n^2);
嵌套一层for循环的时间复杂度为:O(n),二层for循环为O(n^2)，二分的算法时间复杂度为:O(logn)，如果一个for循环套一个二分，那么时间复杂度为O(nlogn);
备注：这里只是通过一个数理化的形式来比较算法的时间执行效率，并不能真正推导出算法在特定机器的执行时间，这取决于具体的电脑和代码。