排序算法学习

图片3.jpg 图片4.jpg

插入排序

它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
-----维基百科

function insertion_sort($data){
    $count = count($data)-1;
    for($i = 0; $i<$count; $i++){
        for($j = $i; $j>=0 && $data[$j+1] < $data[$j]; $j--){
            list($data[$j], $data[$j+1]) = array($data[$j+1], $data[$j]);
        }
    }
    return $data;
}

此算法最坏的时间复杂度是O(n^2)

冒泡排序

它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成
-----维基百科

function bubble_sort(&$data){
    $count = count($data);
    for($i = 0; $i<$count; $i++){
        for($j = 0; $j<$count-1 - $i; $j++){
            if ($data[$j+1] > $data[$j]){
                list($data[$j], $data[$j+1]) = array($data[$j+1], $data[$j]);
            }
        }
    }
    return $data;
}

选择排序

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
-----维基百科

function selection_sort($data){
    $count = count($data)-1;
    for($i = 0; $i<$count; $i++){
        for($j = $i+1; $j<=$count; $j++){
            if ($data[$i] < $data[$j]){
                list($data[$i], $data[$j]) = array($data[$j], $data[$i]);
            }
        }
    }
    return $data;
}

快速排序

使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。
步骤为：
1、从数列中挑出一个元素，称为"基准"（pivot），
2、重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3、递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
-----维基百科

function quick_sort($data){
    $length = array_count($data);
    if ($length <= 1){
        return $data;
    }
    
    $mid_index = $length >> 1;
    $mid_value = $data[$mid_index];
    $left = $right = [];
    for($i = 0; $i<$length; $i++){
        if ($i == $mid_index){
            continue;
        }
        
        if ($data[$i] < $mid_value){
            $left[] = $data[$i];
        } else {
            $right[] = $data[$i];
        }
    }
    return array_merge(quick_sort($left), (array)$mid_value, quick_sort($right));
}