前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >数据结构和算法——选择排序

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

作者头像
Lemon黄
发布2019-11-28 15:08:07
5650
发布2019-11-28 15:08:07
举报
文章被收录于专栏:Lemon黄
1、要解决的问题

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

代码语言:javascript
复制
$numbers = [21,25,100,98,89,77];

要求

  • 对数字进行排序时,需要使用插入选择算法
  • 用PHP实现该算法
2、伪代码说明

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

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

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

代码语言:javascript
复制
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循环从主列表中找到最小的项。

代码语言:javascript
复制
<?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开始。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-11-26,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 Lemon黄 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1、要解决的问题
  • 2、伪代码说明
  • 3、PHP实现快速排序
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档