数据结构与算法(php版)排序之选择排序

yang-pig| 阅读:535 发表时间:2018-07-29 21:00:14 算法

选择排序(Selection Sort)是一种简单直观的排序算法。它的工作原理如下,首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上,则它不会被移动。选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对n个元素的序列进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常好的一种。

selection_sort_animation.gif

实例分析

以数组 arr = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7] 为例,先直观看一下每一步的变化,后面再介绍细节

第一次从数组 [8, 5, 2, 6, 9, 3, 1, 4, 0, 7] 中找到最小的数 0,放到数组的最前面(与第一个元素进行交换):

                               min
                                ↓
8   5   2   6   9   3   1   4   0   7
↑                               ↑
└───────────────────────────────┘

交换后:

0   5   2   6   9   3   1   4   8   7

在剩余的序列中 [5, 2, 6, 9, 3, 1, 4, 8, 7] 中找到最小的数 1,与该序列的第一个个元素进行位置交换:

                       min
                        ↓
0   5   2   6   9   3   1   4   8   7
    ↑                   ↑
    └───────────────────┘

交换后:

0   1   2   6   9   3   5   4   8   7

在剩余的序列中 [2, 6, 9, 3, 5, 4, 8, 7] 中找到最小的数 2,与该序列的第一个个元素进行位置交换(实际上不需要交换):

       min
        ↓
0   1   2   6   9   3   5   4   8   7
        ↑

重复上述过程,直到最后一个元素就完成了排序。

                   min
                    ↓
0   1   2   6   9   3   5   4   8   7
            ↑       ↑
            └───────┘

                           min
                            ↓
0   1   2   3   9   6   5   4   8   7
                ↑           ↑
                └───────────┘

                       min
                        ↓
0   1   2   3   4   6   5   9   8   7
                    ↑   ↑
                    └───┘

                       min
                        ↓
0   1   2   3   4   5   6   9   8   7
                        ↑   

                                   min
                                    ↓
0   1   2   3   4   5   6   9   8   7
                            ↑       ↑
                            └───────┘  

                               min
                                ↓
0   1   2   3   4   5   6   7   8   9
                                ↑      

                                   min
                                    ↓
0   1   2   3   4   5   6   7   8   9
                                    ↑

Selection-Sort-Animation.gif


<?php
/**
 * 选择排序
 * ----------------------------------------------------------
 * 选择排序(Selection Sort)是一种简单直观的排序算法。它的工作原理如下,
 * 首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,
 * 然后,再从剩余未排序元素中继续寻找最小(大)元素,
 * 然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。
 *
 */

function selectionSort(array &$arr) {

    $end = count($arr);
    for ($i = 0; $i < $end; $i++) {
        $minIndex = $i;
        $minValue = $arr[$minIndex];
        for ($j = $i + 1;$j < $end;$j++) {
            if ($arr[$j] < $minValue) {
                $minIndex = $j;
                $minValue = $arr[$minIndex];
            }
        }
        $temp = $arr[$i];
        $arr[$i] = $minValue;
        $arr[$minIndex] = $temp;
    }


}
$arr = array(10,6,8,23,4,1,17,56,32,50,11,9);
selectionSort($arr);
var_dump($arr);