专栏首页Lemon黄数据结构和算法——选择排序

数据结构和算法——选择排序

1、要解决的问题

给定如下所示的数字列表,请按升序对它们进行排序。

$numbers = [21,25,100,98,89,77];

要求

  • 对数字进行排序时,需要使用插入选择算法
  • 用PHP实现该算法

2、伪代码说明

选择排序的工作方式是:维护已排序的子列表,从主列表中找到最小的项,然后将其交换到子列表的最后一个元素,直到对所有项进行排序为止。

每次交换后,已排序的子列表的长度增加一,而主列表的长度减小一。

描述选择排序的伪代码如下:

FOR each element of the master list indexed by i
 
    Set current element of master list as the sub-list[i] element
 
    Find the smallest item from the master list (staring from i)
 
    Swap it with the last element of sub-list
 
END FOR

3、PHP实现快速排序

我们需要一个外部FOR循环来遍历主列表,并需要一个内部FOR循环从主列表中找到最小的项。

<?php
$masterList = [21, 25, 100, 98, 89, 77];
 
$subList = [];
 
for ($i = 0; $i < count($masterList); $i++) {
 
    $subList[$i] = $masterList[$i];
 
    // Find the smallest item
    $smallestIndex = $i;
 
    for ($j = $i; $j < count($masterList); $j++) {
        if ($masterList[$j] < $masterList[$smallestIndex]) {
            $smallestIndex = $j;
        }
    }
    // 交换
    $tmp = $subList[count($subList) - 1];
    $subList[count($subList) - 1] = $masterList[$smallestIndex];
    $masterList[$smallestIndex] = $tmp;
}
 
print_r($subList);
 
// Output:
/*
Array
(
    [0] => 21
    [1] => 25
    [2] => 77
    [3] => 89
    [4] => 98
    [5] => 100
)
*/

需要注意的,内部的for循环从i开始。

本文分享自微信公众号 - Lemon黄(lemonhunag),作者:Lemon黄

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-11-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据结构和算法——插入排序

    插入排序的工作方式是:维护已排序的子列表,一一提取主列表中的项目,然后将其插入子列表中,直到所有项目都从主列表移到子列表中为止。

    Lemon黄
  • 2019年度十大Web开发趋势 - 51CTO.COM

    原文标题:Top 10 Web Development Trends to Follow in 2019,作者: Saif Sadiq

    Lemon黄
  • Mysql开发手册

    约束是一种限制,它通过对表的行或列的数据做出限制,来确保表的数据的完整性、唯一性。

    Lemon黄
  • Java 内存模型(三)-从源代码到指令序列的重排序

    在执行程序时。为了提高性能,编译器和处理器常常会对指令做重排序。重排序分为3中类型: 1 编译器优化的重排序。编译器在不改变单线程程序语义的前提下,可以重新...

    爱明依
  • 泛广电领域的卫星传输和公网传输

    大家好,我是来自安徽广播电视台的张博力,接下来我将为大家详细介绍泛广电领域的卫星传输和公网传输。

    LiveVideoStack
  • Java精确测量代码运行时间 代码执行时间 纳秒 nanoTime

    用户1258909
  • Linux常用命令速查-定时任务

    anacron是一个按天为单位周期性运行某些命令的工具,使用此工具需要指定任务的周期、延迟(分钟)、id、shell。

    Java学习录
  • Process Lasso x64 9.3.0.64 简体中文绿色破解版

    Process Lasso Pro 是一款独特的调试进程级别的系统优化工具,主要功能是基于其特别的算法动态调整各个进程的优先级并设为合理的优先级以实现为系统减负...

    萌海无涯
  • 学习C语言编译器的选择

    很多初学C语言的同学可能遇到的首要问题,就是选择编译器,用什么编程软件? 然而通过了解之后发现有那么多编程软件,什么VC6.0,Dev ,CodeBlocks,...

    编程范 源代码公司
  • 学习C语言编译器的选择

    来源:C语言网 很多初学C语言的同学可能遇到的首要问题,就是选择编译器,用什么编程软件? 然而通过了解之后发现有那么多编程软件,什么VC6.0,Dev ,Cod...

    编程范 源代码公司

扫码关注云+社区

领取腾讯云代金券

玩转腾讯云 有奖征文活动