选择排序算法

学号：20021211189       姓名：赵治伟

【嵌牛导读】选择排序（Selection sort）是最简单直观的一种算法，基本思想为每一趟从待排序的数据元素中选择最小（或最大）的一个元素作为首元素，直到所有元素排完为止。

【嵌牛鼻子】选择排序算法

【嵌牛正文】

一、选择排序

1.算法原理

这是一个无序数列：1、5、4、2、6、3，我们要将它按从小到大排序。按照选择排序的思想，我们要找到最小的元素，将它移到队首

首先开始第一轮最小元素的比较

先假定最小元素为第一个元素：1

第一步：比较1和5，1比5小，最小元素为1

第二步：比较1和4，1比4小，最小元素为1

经过一轮比较后，找到1为最小的元素，将1与第一个元素交换（1已经是第一个元素，不需要再进行交换）

第二轮，从第二个元素5开始比较，发现2是最小的元素，5与2进行交换

第二轮结束后，如下所示

第三轮结束后，如下所示

第四轮结束后，如下所示

第五轮结束后，如下所示

至此所有的元素都是有序的

2.算法实现

function sort(arr) {

    let length = arr.length;

    for (let i = 0; i < length - 1; i++) {

        let minIndex = i;

        for (let j = i + 1; j < length; j++) {

            minIndex = arr[minIndex] > arr[j] ? j : minIndex;

        }

        if (i !== minIndex) {

            [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];

        }

    }

}

let arr = [1, 5, 4, 2, 6, 3];

sort(arr);

console.log(arr);

二、选择排序算法特点

1.时间复杂度

选择排序算法的每一轮要遍历所有元素，共遍历n-1轮，所以时间复杂度是O(N^2)

2.空间复杂度

选择排序算法排序过程中需要一个临时变量存储最小元素（最大元素），所需要的额外空间为1，因此空间复杂度为O(1)

3.稳定性

选择排序算法是一种不稳定排序算法，当出现相同元素的时候有可能会改变相同元素的顺序

上图例子中，绿色2在紫色2之前，但经过选择排序之后，绿色2在紫色2之后，所以选择排序是一种不稳定排序算法