排序分为内部排序和外部排序
内部排序：所有数据都加载到内存当中。主要方法有冒泡法、选择排序法、插入式排序法和快速排序法。
外部排序：数据量过大，无法全部加载到内存中，需要借助外部存储进行排序，将数据量分成多个文件，每个文件分别用内部排序法进行排序，排序后将文件合并。主要方法有合并排序法和直接合并排序法。
-
冒泡排序（升序排列）
思想：从第一个元素开始，对数组中两两相邻的元素比较，将值较小的元素放在前面，值较大的元素放在后面，一轮比较完毕，一个最大的数将成为数组中的最后一个元素。
冒泡排序示意图$arr = array(1, 3, 6, 2, 4); $temp = 0; for ($i = 0; $i < count($arr)-1; $i++) { // 趟数 for ($j = 0; $j < count($arr)-1-$i; $j++) { // 比较次数 if ($arr[$j] > $arr[$j+1]) { $temp = $arr[$j]; $arr[$j] = $arr[$j+1]; $arr[$j+1] = $temp; } } } print_r($arr); // Array ( [0] => 1 [1] => 2 [2] => 3 [3] => 4 [4] => 6 )Q1：趟数为什么是小于
$count($arr)-1，而不是小于count($arr)?
A1：因为$i表示趟数，同时又表示排序好的个数，$i每加1，都表示已经排好了未排列里面的最大数。当$i < count($arr)时，最后一趟，只剩最后一个数，这个数根本不用比较。只剩一个坑，跳进里面就行了，用不着再一次比较。Q2：比较次数为什么是
count($arr)-1-$i?
A2：为什么是count($arr)-1，因为$j表示的是比较次数，自己和自己不需要比较，只需要和自己后面的数比较就行了，所以是count($arr)-1；那为什么还要减去$i呢？同样的道理，$i同样表示已经排好了的个数，而且这些排好的都在最后面放着，也没有必要和排序好的再次比较。所以，最终结果就是count($arr)-1-$i。
-
选择排序法（升序排列）
思想：每一次从待排序的数据元素中选出最小的一个元素，存放在需要排列序列的起始位置，直到全部待排序的数据元素排完。
选择排序法示意图$arr = array(1, 3, 6, 2, 4); $temp = 0; for ($i = 0; $i < count($arr)-1; $i++) { $minVal = $arr[$i]; $minIndex = $i; for ($j = $i+1; $j < count($arr); $j++) { // 找出最小数 if ($minVal > $arr[$j]) { $minVal = $arr[$j]; $minIndex = $j; } } // 交换 $temp = $arr[$i]; $arr[$i] = $arr[$minIndex]; $arr[$minIndex] = $temp; } print_r($arr); // Array ( [0] => 1 [1] => 2 [2] => 3 [3] => 4 [4] => 6 )
-
插入式排序法
插入式排序法又分为插入排序法、谢尔排序法 和 二叉树排序法。这里我们只举例基本的插入排序法思想：分一个有序表（可以理解为数组）和一个无序表，开始时有序表中只包含一个元素，无序表中包含n-1个元素，排序过程每次从无序表中取出第一个元素，和有序表中的元素进行比较，插入到适当位置。
因为有序表和无序表刚好划分了一整个数组，所以在一个数组中就可以完成我们的排序。
$arr = array(1, 3, 6, 2, 4); for ($i = 0; $i < count($arr); $i++) { $insertVal = $arr[$i+1]; $sortIndex = $i-1; // 从后往前比较 while ($sortIndex >= 0 && $insertVal < $arr[$sortIndex]) { // 判断位置是否合适；只要进入while循环，表示位置还不合适 $arr[$sortIndex+1] = $arr[$sortIndex]; // 给要插入的数向后挪位置 $sortIndex--; } // 插入数据(在比较的数的后面插入) $arr[$sortIndex+1] = $insertVal; } print_r($arr); // Array ( [0] => 1 [1] => 2 [2] => 3 [3] => 4 [4] => 6 )
-
快速排序法
思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据比另外一部分的数据都小，然后再按照此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
快速排序的速度非常快，不过在排序的瞬间，内存会暴涨。快速排序是用空间来换取时间的一种思想
快速排序法示意图$arr = array(1, 3, 6, 2, 4); function quickSort ($left, $right, &$array) { $l = $left; $r = $right; $pivot = $array[($left+$right)/2]; // 基准(这里取数组中间数，可以取数组中随便一个数) $temp = 0; while ($l < $r) { while ($array[$l] < $pivot) $l++; while ($array[$r] > $pivot) $r--; if ($l >= $r) break; $temp = $array[$l]; $array[$l] = $array[$r]; $array[$r] = $temp; if ($array[$l] == $pivot) --$r; if ($array[$r] == $pivot) ++$l; } if ($l == $r) { $l++; $r--; } if ($left < $r) quickSort($left, $r, $array); if ($right > $l) quickSort($l, $right, $array); } quickSort(0, count($arr)-1, $arr); print_r($arr); // Array ( [0] => 1 [1] => 2 [2] => 3 [3] => 4 [4] => 6 )
