常见排序列表

模板网 2021-04-14

常见排序列表

中文名称 英文名称 平均时间复杂度 最坏时间复杂度 最好时间复杂度 空间复杂度 稳定性
选择排序 Selection n^2 n^2 n^2 1 不稳
冒泡排序 Bubble n^2 n^2 n 1
插入排序 Insertion n^2 n^2 n 1
堆排序 heap nlog~2n nlog~2n nlog~2n 1 不稳
希尔排序 Shell n^1.3 n^2 n 1 不稳
归并排序 Merger nlog~2n nlog~2n nlog~2n n
快速排序 Quick nlog~2n n nlog~2n log~2n 不稳
桶排序 Bucket n+k n^2 n n+k
计数排序 Counting n+k n+k n+k n+k
基数排序 Radix n*k n*k n*k n+k
西风烈,
长空雁叫霜晨月。
霜晨月,
马蹄声碎,
喇叭声咽。
雄关漫道真如铁,
而今迈步从头越。
从头越,
苍山如海,
残阳如血。
---------------------------------
选泡插
快归堆希桶计基,
恩方恩老恩一三,
对恩加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));

相关文章

  1. 编程常用词汇表

    这里整理了一些常用词汇,供在编码中使用: 通用 数学 列表 时间 图像 文件目录 执行 业务 用户相关 文章相关 商品相关 优惠券相关 订单相关 这里总结了一些软件开发中常用的词汇,如

  2. php自建邮局下邮件无法正常发送问题解决

    产生问题 自建邮局发邮件时提示错误信息:stream_set_blocking()... 这是因为PHP 5.6+版本强制要求验证服务器的有效性 PHP 5.6+特性 Stream wrappers

  3. aof恢复与rdb服务器迁移

    一、不小心flushall或flushdb了怎么办??? 只有aof还不够。 因为如果发生重写,aof文件里就什么都没有了。 所以要及时shutdown nosave,防止aof重写!!! 然后将a

  4. 递归和分治思想

    一、斐波那契数列 1 1 2 3 5 8 13 21 34 55 89 144 ...... 我们可以用数学函数来定义: |0,当n = 0 F(n) = |1,当n = 1

  5. 虚拟环境-virtualenv

    在开发Python应用程序的时候,系统安装的Python3只有一个版本:3.4。所有第三方的包都会被pip安装到Python3的site-packages目录下。 如果我们要同时开发多个应用程序,那

随机推荐

  1. 编程常用词汇表

    这里整理了一些常用词汇,供在编码中使用: 通用 数学 列表 时间 图像 文件目录 执行 业务 用户相关 文章相关 商品相关 优惠券相关 订单相关 这里总结了一些软件开发中常用的词汇,如

  2. php自建邮局下邮件无法正常发送问题解决

    产生问题 自建邮局发邮件时提示错误信息:stream_set_blocking()... 这是因为PHP 5.6+版本强制要求验证服务器的有效性 PHP 5.6+特性 Stream wrappers

  3. aof恢复与rdb服务器迁移

    一、不小心flushall或flushdb了怎么办??? 只有aof还不够。 因为如果发生重写,aof文件里就什么都没有了。 所以要及时shutdown nosave,防止aof重写!!! 然后将a

  4. 递归和分治思想

    一、斐波那契数列 1 1 2 3 5 8 13 21 34 55 89 144 ...... 我们可以用数学函数来定义: |0,当n = 0 F(n) = |1,当n = 1

  5. 虚拟环境-virtualenv

    在开发Python应用程序的时候,系统安装的Python3只有一个版本:3.4。所有第三方的包都会被pip安装到Python3的site-packages目录下。 如果我们要同时开发多个应用程序,那