@TOC

排序算法

常见的排序算法可以分为两类：

• 比较类算法：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破 O(nlogn) ，因此也称为非线性时间比较类排比。
• 非比较类算法：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

参考链接: O(1), O(n), O(logn), O(nlogn) 的区别

1.冒泡排序

冒泡算法是一种简单的排序算法，通过不断的相临两个元素的比较，每轮可以比较出最大的元素，较小的元素慢慢移到前面。

1.1 算法描述

• 相邻元素比较，较大的元素后移，继续和后一个元素比较
• 每轮比较吐出一个最大的元素，不参与下一轮比较
• 下一轮元素比较会比上一次少一次比较
• 最后一轮只剩两个元素比较，完成排序

1.2 动图演示

Alt

1.3 代码实现

    $arr = [2,22,3,88,5,333,88,90];
    $count = count($arr);
    for($i=0;$i<$count-1;$i++) { // 外层控制进行几轮比较
        for($j=0;$j<$count-$i-1;$i++){ // 内层控制冒出来的元素要经过几轮比较
            if($arr[$j]>$arr[$j+1]){
                $temp = $arr[$j];
                $arr[$j] = $arr[$j+1];
                $arr[$j+1] = $temp;
            }
        }
    }

2. 插入排序

插入排序是比较典型的高低个排队，每次拿一个元素和前面的元素比较，插到合适的位置。

2.1 算法描述

• 取出第二个元素
• 跟前面的元素比较，直到找到比前面元素大的位置插入进去
• 继续下一个元素，直到最后一个元素找到插入位置，排序结束

2.2 动图演示

Alt

2.3 代码实现

    $arr = [2,22,3,88,5,333,88,90];
    $count = count($arr);
    for($i=1;$i<$count;$i++){
        $current = $arr[$i];
        $preIndex = $i-1;
        while($preIndex>=0 && $arrp[$preIndex]>$current) {
            $arr[$preIndex+1] = $arr[$preIndex];
            $preIndex--;
        }
        $arr[$preIndex+1] = $current;
    }

3. 选择排序

选择排序就是寻找最小或者最大的数，假设第一个位置放最小的元素，通过比较找到最小元素，和当前位置元素换位，依次执行下去。

3.1 算法描述

• 指定第一个位置存放最小元素
• 寻找最小元素所在的位置,和第一个位置的元素交换位置
• 继续下一个最小元素选择，
• 持续确定每一个位置的元素，到倒数第二个位置，排序结束

3.2 动图演示

Alt

3.3 代码实现

    $arr = [2,22,3,88,5,333,88,90];
    $count = count($arr);
    for($i=0;$i<$count-1;$i++) {
        $minIndex = $i;
        for($j=$i+1;$j<$count;$j++) {
            if($arr[$i]<$arr[$minIndex]){
                $minIndex = $i;
            }
        }
        if($minIndex !== $i) {
            $temp = $arr[$i];
            $arr[$i] = $arr[$minIndex];
            $arr[$minIndex] = $temp
        }
    }