常见排序列表

西风烈，
长空雁叫霜晨月。
霜晨月，
马蹄声碎，
喇叭声咽。
雄关漫道真如铁，
而今迈步从头越。
从头越，
苍山如海，
残阳如血。
---------------------------------
选泡插
快归堆希桶计基，
恩方恩老恩一三，
对恩加k恩乘k，
不稳稳稳不稳稳，
不稳不稳稳稳稳！

如何验证算法的正确性-对数器

1、肉眼观察
2、产生足够多的随机样本
3、用确定正确的算法计算样本结果
4、对比被验证算法的结果

一、选择排序（基本不用，不稳）

最简单，最没用

一遍一遍过滤数组，每次选择出最小（最大）的数

$list = [3,8,5,1,9,4,7];

for ($i=0;$i<count($list)-1;$i++){
    $index = $i;

    for($j=$i+1;$j<count($list);$j++){
        if($list[$index]>$list[$j]){
            $index = $j;
        }
    }
    $tmp = $list[$i];
    $list[$i] = $list[$index];
    $list[$index] = $tmp;
}

print_r($list);

二、冒泡排序（基本不用，太慢）

$list = [3,8,5,1,9,4,7];


for($i=0;$i<count($list)-1;$i++){
    for($j=0;$j<count($list)-$i-1;$j++){
        if($list[$j]>$list[$j+1]){
            $tmp = $list[$j];
            $list[$j] = $list[$j+1];
            $list[$j+1] = $tmp;
        }
    }
}

print_r($list);

三、插入排序（样本小且基本有序的时候效率比较高）

$list = [3,8,5,1,9,4,7];


for ($i=1;$i<count($list);$i++){
    for($j=$i;$j>0;$j--){
        if($list[$j] < $list[$j-1]){
            $tmp = $list[$j-1];
            $list[$j-1] = $list[$j];
            $list[$j] = $tmp;
        }else{
            //确保最好情况下的时间复杂度为O(n)
            break;
        }
    }
}

print_r($list);

四、希尔排序（1959年改进的插入排序）

gap

在间隔大的时候，移动次数比较少。在间隔小的时候，移动距离比较短。所以希尔排序会比普通的插入排序效率要高。

由于是跳着排，所以会不稳定

for($gap=4;$gap>=1;$gap/=2){
    for($i=$gap;$i<count($list);$i++){
        for ($j=$i;$j>$gap-1;$j-=$gap){
            if($list[$j]<$list[$j-$gap]){
                $tmp = $list[$j];
                $list[$j] = $list[$j-$gap];
                $list[$j-$gap] = $tmp;
            }
        }
    }
}

//间隔问题
//Knuth
h = 1;
h = 3*h+1

$h = 1;
while ($h<=count($list)/3){
    $h = $h*3+1;
}

for($gap=$h;$gap>=1;$gap=($gap-1)/3){
    for($i=$gap;$i<count($list);$i++){
        for ($j=$i;$j>$gap-1;$j-=$gap){
            if($list[$j]<$list[$j-$gap]){
                $tmp = $list[$j];
                $list[$j] = $list[$j-$gap];
                $list[$j-$gap] = $tmp;
            }
        }
    }
}

五、归并排序

java和python对于对象的排序都是归并。

$list = [10,4,11,7,1,3,6,2];
print_r(mergerSort($list));
function mergerSort($list){
    if(count($list)>1){
        $mid = floor((count($list)-1)/2);
        $left_arr = array_slice($list,0,$mid+1);
        $right_arr = array_slice($list,$mid+1,count($list)-$mid-1);
        $left_arr = mergerSort($left_arr);
        $right_arr = mergerSort($right_arr);

        return merger($left_arr,$right_arr);
    }else{
        return $list;
    }
}


function merger($left_arr,$right_arr){
    $tmp = [];
    $i = 0;//左序列指针
    $j = 0;//有序列指针
    while($i<count($left_arr) && $j<count($right_arr)){
        if($left_arr[$i] <= $right_arr[$j]){
            $tmp[] = $left_arr[$i++];
        }else{
            $tmp[] = $right_arr[$j++];
        }
    }

    //防止左边还有剩余的
    while ($i<count($left_arr)){
        $tmp[] = $left_arr[$i++];
    }

    //防止右边还有剩余的
    while ($j<count($right_arr)){
        $tmp[] = $right_arr[$j++];
    }

    return $tmp;
}

六、快速

function quickSort($list){
    if(count($list)<=1){
        return $list;
    }


    $left = [];
    $right = [];
    $mid = floor((count($list)-1)/2);
    for($i=0;$i<count($list);$i++){
        if($i==$mid){
            continue;
        }

        if($list[$i] <= $list[$mid]){
            $left[] = $list[$i];
        }else{
            $right[] = $list[$i];
        }
    }

    $left = quickSort($left);
    $right = quickSort($right);

    return array_merge($left,[$list[$mid]],$right);
}

print_r(quickSort($list));