PHP插入排序

百度百科有一段话说的很清楚，插入排序的原理其实很简单。

***假设我们输入的是 “5，1，4，2，3” 我们从第

百度百科有一段话说的很清楚，插入排序的原理其实很简单。

***假设我们输入的是 “5，1，4，2，3” 我们从第二个数字开始，这个数字是1，我们的任务只要看看1有没有正确的位置，我们的做法是和这个数字左边的数字来比，因此我们比较1和5，1比5小，所以我们就交换1和5，原来的排列就变成了“1，5，4，2，3 ”***

***接下来，我们看第3个数字有没有在正确的位置。这个数字是4，它的左边数字是5，4比5小，所以我们将4和5交换，排列变成了 “1，4，5，2，3 “我们必须继续看4有没有在正确的位置，4的左边是1，1比4小，4就维持不动了。***

***再来看第四个数字，这个数字是2，我们将2和它左边的数字相比，都比2大，所以就将2一路往左移动，一直移到2的左边是1，这时候排序变成了 “1，2，4，5，3 ”***

***最后，我们检查第五个数字，这个数字是3，3必须往左移，一直移到3的左边是2为止，所以我们的排列就变成了 “1，2，3，4，5 ”排序因此完成了。***

所以就是把这段话转换成算法

第一版

$a\[$j\]) { $a\[$j\] = $a\[$j - 1\]; $a\[$j - 1\] = $temp; $j--; if ($j == 0) { break; } } }  这一段很容易理解 首先是定义i=1,表示i从第二个数字开始，由于插入排序其实是给每个数字找到合适的位置，然后交换(插入),为了不影响外部变量i的值，所以使用内部变量j来标记前一个数字和后一个数字，然后j=i，所以a\[j\]=当前数字，a\[j-1\]就表示当前数字的前一个数字，temp变量用来存储当前数字,然后while循环条件就是判定前一个数字是否大于当前数字，如果是，那么当前数字和前一个数字通过temp变量进行交换，同时j–，之所以要j–，因为数字已经往前移了一个，所以要j–，新的a\[j\]才能表示当前数字,所以要j–,同时还要判断j是否等于0，因为如果等于0，则表示已经到了第一位，没必要继续前移了，所以退出循环。在while循环中，会一直吧当前数字交换到正确的位置才会停止循环。 但这段代码不是很简洁，可以利用短路条件来使得代码变得简洁: 第二版 0 && $a\[$j - 1\] > $a\[$j\]) { $a\[$j\] = $a\[$j - 1\]; $a\[$j - 1\] = $temp; $j--; } } return $a; } 很明显利用短路条件，如果j>0才会执行循环，如果j<=0，由于短路,所以$a\[$j – 1\]> $a\[$j\]不会执行，所以$j-1不会变成-1，因此$a\[$j – 1\] > $a\[$j\]不能放在前面。 但是每次都这样交换两次会显得效率很低，所以可以进一步优化 第三版 0 && $a\[$j - 1\] > $temp) { $a\[$j\] = $a\[$j - 1\]; $j--; } $a\[$j\] = $temp; } 这个代码可以减少交换的次数，同时while条件也修改了,每次都比较前一个数字与temp的大小，如果大则把当前数字赋前一个数字的值，此时j–，在判断前一个数字是否大于temp，一直如此，知道条件不满足，这样就不会破坏之前的顺序，最后再在合适的位置赋值temp，这样就进一步优化。 顺便下面附上qcachegrind测试三种方案的时间 这是第一种方法  这是第二种方法  这是第三种方法  可以发现第三种方法确实快一点