常见排序

时间复杂度是指执行算法所需要的计算工作量
而空间复杂度是指执行这个算法所需要的内存空间。

分类
排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是指在排序期间全部对象太多，不能同时存放在内存中，必须根据排序过程的要求，不断在内，外存间移动的排序。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等

image

冒泡排序

• 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
• 针对所有的元素重复以上的步骤，除了最后一个。

• 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

  
  冒泡排序

$nums = [3,44,2,9,12,56,89];

function bubblesort(array $arr = []){
    $counts = count($arr);
    if ($counts < 2) {
        return $arr;
    }
    for ($i=0; $i < $counts-1; $i++) { 
        for ($j=0; $j < $counts-$i-1; $j++) { 
            if ($arr[$j] > $arr[$j+1]) {
                $tmp = $arr[$j];
                $arr[$j] = $arr[$j+1];
                $arr[$j+1] = $tmp;
            }
        }
    }
    return $arr;
}

选择排序

• 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
• 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

• 重复第二步，直到所有元素均排序完毕。

  
  选择排序

$nums = [3,44,2,9,12,56,89];

function selectSort(array $numbers = array())
{
    $count = count( $numbers );
    if( $count <= 1 ) return $numbers;
    for($i = 0; $i < $count-1; $i ++)
    {
        $min = $i;
        for( $j = $i+1; $j < $count; $j ++)
        {
            if( $numbers[$min] > $numbers[$j] )
            {
                $min = $j;
            }
        }
        if( $min != $i )
        {
            $temp = $numbers[$min];
            $numbers[$min] = $numbers[$i];
            $numbers[$i] = $temp;
        }
    }
    return $numbers;
}

插入排序

• 从第一个元素开始，该元素可以认为已经被排序
• 取出下一个元素，在已经排序的元素序列中从后向前扫描
• 如果该元素（已排序大于新元素），将该元素移动到下一位置
• 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
• 将新元素插入到该位置后

• 重复步骤2~5

  
  插入排序

function insertionSort(array $numbers = array())
{
    $count = count( $numbers );
    if( $count <= 1 ) return $numbers;
    for($i = 1; $i < $count; $i ++)
    {
        $temp = $numbers[$i];
        for($j = $i-1; $j >= 0 && $numbers[$j] > $temp; $j --)
        {
            $numbers[$j+1] = $numbers[$j];
        }
        $numbers[$j+1] = $temp;
    }
    return $numbers;
}

快速排序

• 从数列中挑出一个元素，称为"基准"。
• 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区操作。
• 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会结束，因为在每次的迭代中，它至少会把一个元素摆到它最后的位置去。

快速排序

function quickSort(array $arr = []){
    $counts = count($arr);
    if ($counts < 2) {
        return $arr;
    }
    $mid_value = $arr[0];
    $left_arr = $right_arr = [];
    for ($i=1; $i < $counts; $i++) { 
        if ( $mid_value > $arr[$i] ) {
            $left_arr[] = $arr[$i];
        } else {
            $right_arr[] = $arr[$i];
        }
    }
    return array_merge(quickSort($left_arr),(array)$mid_value,quickSort($right_arr));
}