选择排序

选择排序

今天给大家介绍另一种算法:选择排序。选择排序是非常简单,但是并不算很快的一种排序。之所以讲这个,是为了更好的更快的入门后续的算法知识。

直接上代码

// 从小到大排序
function selectionSort(arr){
    let temp, minIndex
    for(let i = 0; i < arr.length - 1; i++){
        minIndex = i
        for(let j = i + 1; j < arr.length; j++) {
            if(arr[minIndex] > arr[j]) {
                minIndex = j
            }
        }
        temp = arr[i]
        arr[i] = arr[minIndex]
        arr[minIndex] = temp

    }
    return arr
}

代码解释

所谓选择,就是每次用当前的数字跟剩下的数字逐个进行对比,挑选出最小或者最大的数。
i = 0时,跟下标为1及后面的逐个进行比较,把最小的元素下标记录下来,与a[0]做位置交换,然后进行下一轮比较;
i = 1时,跟下标为2及后面的逐个进行比较,把最小的元素下标记录下来,与a[1]做位置交换,然后进行下一轮比较;

以此类推,如图所示:
选择排序.jpg

时间复杂度

对于这种算法,我们需要遍历数组中的每一个元素时间复杂度为O(n),并且,对于这个遍历要执行n次操作,因此时间复杂度是O(n2),如无法理解,请看下图:

选择排序时间复杂度.jpg

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。