自学内容网 自学内容网

排序算法---选择排序

选择排序的思想

也是一种很简单的排序算法,它的思路也是将一组待排序的数据,分成2段,一段是“已排序”了的数据,另一段是“未排序”的数据。当然,在最开始的时候,“已排序”区段里是没有数据的。排序开始后,每次都从“未排序”的数据中取出一个最小的元素(注意,这里是取最小的元素,这一点与「 插入排序 」是不同的),然后将这个最小的元素插入到“已排序”数据中末尾元素的后面(这里其实是将这个最小元素与“已排序”数据的末尾紧邻的下一位元素进行交换),这样保持了“已排序”中的数据永远是有序的。一直这么循环的去处理,直到所有的“未排序”的数据都已交换完,则整个排序全部完成。

选择排序的代码实现

代码优化思想:

选择排序的优化引入的二分的思想,前面是找到最小的值往前面放,现在在一趟循环中同时找到最大最小值,将最小值放入头,最大值放入尾。

function selectSorting(arr) {
    for (let i = 0; i < arr.length; i++) {
        let minIndex = i;


        for (let j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
              minIndex = j;
            }
        }

        if (i < arr.length) {
          [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
        }
        
    }

    return arr;
}

选择排序的复杂度

时间复杂度:

最差情况是O(n^2)

最好情况是O(n)

空间复杂度:O(1)


原文地址:https://blog.csdn.net/weixin_47808575/article/details/140642321

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!