定义
排序是我们生活中经常会面对的问题。同学们做操时会按照从矮到高排列；老师查看上课考勤情况时，会按学生学号顺序点名；高考录取时，会按成绩总分降序依次录取等。那排序的严格定义是什么呢？
假设有n个记录的序列为{r1,r2....,rn},其相应的的关键字分别为{k1,k2.....,kn},需确定1，2，....,n的一种排列p1,p2,...pn,使得其相应的关键字满足kp1<=kp2<=....<=kpn(非递减或递增关系),即使得序列成为一个关键字有序的序列{r1,r2,r3....rn},这样的操作称为排序。
排序的稳定性
假设ki=kj(1<=i<=n,1<=j<=n, i!=j)，且在排序前的序列中ri领先于rj即(i>j)。如果排序后ri仍领先于rj，则称所用的的排序方法是稳定的；反之若可能使得排序后的序列中rj领先ri,则称所用的排序是不稳定的。
内排序和外排序
内排序是在排序的过程中，待排序的所有记录全部被放置在内存中。外排序是由于排序的记录个数太多，不能同时放在内存，整个排序过程需要内外存多次交换数据才能进行。
对于内排序来说，排序算法的性能主要受三个方面的影响。
- 时间性能
- 辅助空间
- 算法的复杂度
常用算法的分类
按内外排序分:
内排序： 插入排序，交换排序，选择排序和归并排序。
按复杂度分：
简单算法： 冒泡排序，交换排序，选择排序，归并排序。
改进算法：希尔排序，堆排序，归并排序，快读排序。
PHP排序代码实现
冒泡排序
冒泡排序(Bubble Sort)一种交换排序，他的基本思路是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。
function BubbleSort(array $array){
if (!isset($array[1])) {
return $array;//n=1时，序列不用排序直接返回
}
$len = count($array);
for ($i = 0; $i < $len; $i++) {//主循环
for ($j = $len - 1; $j > $i; $j--) {
if ($array[$j] < $array[$j - 1]) {//相邻的比较，如果后面的小于前面的，则交换位置
$temp = $array[$j];
$array[$j] = $array[$j - 1];
$array[$j - 1] = $temp;
}
}
}
return $array;
}
冒泡排序的复杂度
最好的情况下是n-1次的比较，没有数据交换，时间复杂度是O(n)
最坏的情况下(逆序) (n∑(i=2)) (i-1)=1+2+3+...+(n-1)=n(n-1)/2次。 时间复杂度是 O(n2)
简单选择排序
简单选择排序法(Simple Selection Sort)就是通过n-i次关键字的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1≤ i ≤ n)个记录交换之。
function SelectSort(array $array){
if (!isset($array[1])) {
return $array;
}
$len = count($array);
for ($i = 0; $i < $len; $i++) {
$min = $i; //假设当前下标的值为最小值
for ($j = $i + 1; $j < $len; $j++) {
if ($array[$j] < $array[$min]) { //如果有小于当前最小值的关键字
$min = $j;//将此关键字的下标赋值给min
}
}
if ($min != $i) {//如果$min不等于$i,说明找到最小值交换
$temp = $array[$min];
$array[$min] = $array[$i];
$array[$i] = $temp;
}
}
return $array;
}
从简单选择排序的过程中，它的最大特点事交换移动数据次数相当少，这样也就节省了很多时间。无论最好最坏 情况下，其比较次数都一样多。
时间复杂度: O(n2)
直接插入排序
直接插入排序(Straight Insertion Sort)的基本操作是将一个记录插入到已经排好序的有序列表中，从而得到一个新的、记录数增1的有序表中。
function InsertSort($array){
if (!isset($array[1])) {
return $array;
}
$len = count($array);
for ($i = 1; $i < $len; $i++) {
if ($array[$i - 1] > $array[$i]) { //如果前面的值大于后面的值,就要移动后面那值得位置了
$temp = $array[$i]; //设置哨兵。
for ($j = $i - 1; $array[$j] > $temp; $j--) { // 从找到哨兵的位置开始，后移。倒序查找，如果前面还有大于哨兵的值，也要依次后移
$array[$j + 1] = $array[$j];
}
$array[$j + 1] = $temp; //
}
}
return $array;
}
最好的情况: O(n)
最坏的情况: O(n2)
希尔排序
希尔排序(Shell Sort)是有D.L.Shell与1959年提出来的一种排序算法，在这之前排序算法的时间复杂度都是O(n2),希尔算法是突破这个时间复杂度的第一批算法之一。
时间复杂度: O(n3/2次方)
堆排序
堆排序(Heap Sort)就是利用堆进行排序的方法。它的基本思想是，将待排序的序列构造成一个大顶堆。此时整个序列的最大值就是堆顶的根节点。将它移走(其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的n-1个序列重新构造成一个堆，这样就会得n个元素中的依次小值。如此反复执行，便能得到一个有序的序列了。
时间复杂度O(nlogn)
归并排序
归并排序(Merrgin Sort) 就是利用归并的思想实现的排序算法。它的原理是假设初始序列含有n个记录，则可以看成是n个有序的序列的子序列，没个子序列的长度为1，然后两两归并，得到[n/2](┌x┐表示不小于x的最小正整数）个长度为2或1的有序子序列；然后在两两归并，如此重复，知道得到一个长度为n的有序序列为止，这种排序的方法称为2路归并排序。
时间复杂度： O(nlogn)
空间复杂度: 递归版 O(n+logn) 迭代版 O{n}
快速排序
快读排序(Quick Sort)的基本思路是: 通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一个部分的关键字小，则可分别达到对着两部分记录进行排序，以达到整个序列有序的目的。
function QuickSort($array){
if (!isset($array[1])) {
return $array;
}
$leftArray = [];
$rightArray = [];
$minArray = [];
$min = $array[0];
for($i=0; $i< count($array); $i++){
if($array[$i] > $min){
$rightArray[] = $array[$i]; //将大于哨兵的值放在右边
}
if($array[$i] < $min){
$leftArray[] = $array[$i]; //将小于哨兵的值放在左边
}
if($array[$i] == $min){
$minArray[] = $array[$i]; //和哨兵相等的值放在一起
}
}
$rightArray = QuickSort($rightArray);
$leftArray = QuickSort($leftArray);
return array_merge($leftArray, $minArray, $rightArray);
}
时间复杂度: O(nlongn)
空间复杂度: O(logn)
参考资料 《大话数据结构》
