前端学习数据结构与算法系列(六)：选择排序与插入排序

本文由图雀社区认证作者 神奇的程序员 写作而成，图雀社区将连载其前端学习数据结构与算法系列，点击阅读原文查看作者的掘金链接，感谢作者的优质输出，让我们的技术世界变得更加美好????

选择排序

前言

选择排序，作为经典的排序算法。与冒泡排序一样，在面试中也常常会被问到，如果你没有掌握，那面试也就结束了????

本文采用图文的方式讲解选择排序的特点，分步骤讲解js的实现思路以及相对应的代码，欢迎各位感兴趣的开发者阅读本文????

概念

从待排序的数据中寻找最小值，将其与序列最左边的数字进行交换，重复这一操作的算法即选择排序。

特点

• 线性查找数组中的最小值

• 找到最小值后与序列中的比较值进行交换

• 交换完毕后1轮结束

• 新的一轮比较值的位置为当前轮数

• 重复上述操作，直至比较到序列的最后一个元素。

图解示例

如图所示，将下列数据按照从小到大的顺序进行排列。

• 用序列的1号元素与其之后的元素进行线性比较，找到最小值1。

• 将找到的最小值与序列的1号元素进行位置调换，1轮操作完成。

• 开始新一轮的比较，用序列的2号元素与其之后的元素进行线性比较，找到最小值2

• 将将找到的最小值与序列的2号元素进行位置调换。

• 重复上述操作，新一轮比较的元素位置为当前轮数，直至比较到序列的最后一个元素，则排序完成。

实现思路

• 声明一个函数，参数为一个数组

• 遍历数组，将数组中的值与其之后的元素进行比较，找到最小值

• 找到最小值后，将当前比较的值与最小值进行位置互换

• 直至遍历到最后一个元素，排序结束。

接下来，我们用JavaScript根据实现思路来实现下选择排序。

/**
 * 1. 从数组的0号元素开始和之后的元素进行大小比较
 * 2. 找到最小值后，将最小值与当前比较值进行位置互换
 * 3. 重复上述操作，当前轮数则为比较元素的位置，直至最后一轮的比较
 */

const selectSort = function (arr) {
    for (let i = 0; i < (arr.length-1); i++){
        // 最小值
        let min = arr[i];
        // 最小值位置
        let minIndex = i;
        // 比较次数
        let round = 0;
        for (let j = i+1; j<arr.length; j++){
            round ++;
            if(min>arr[j]){
                // 如果最小值大于当前比较值，则进最小值赋值当前遍历到的值
                min = arr[j];
                minIndex = j;
            }
        }
        console.log(`第${i+1}轮结束: ${arr},最小值${min},最小值位置${minIndex},共比较${round}次`);
        // 位置互换
        [arr[i],arr[minIndex]] = [min,arr[i]];
    }
    return arr;
};

const arrData = [4,6,7,8,9,1,2,3,4];
console.log(selectSort(arrData));

执行结果

插入排序

概念

从序列左端开始依次对数据进行排序的算法称为插入排序。

特点

• 序列中的数据分为两个区域：已排序区域和未排序区域

• 从序列的最左侧开始定义排序区域

• 已排序区域的数据按照从小到达的顺序进行排列

• 元素比较时，首先用未排序区域的第一个元素与已排序区域的最后一个元素进行比较

图解示例

如图所示，对下列数据进行排序

• 假设，最左边的数字5已完成排序，将5归入已排序区域

• 从未排序区域中，取出最左侧的数字3，将它与已排序区域的数字进行比较。

• 若左边的数字更大，就交换这两个数字，重复该操作，直到左边已归位的数字比取出的数字更小，或者取出的数字已经被移到整个序列的最左边为止。

• 操作结束，此时已排序区域的数字为3和5

• 重复步骤2，取出数字4，将它先和已排序区域的数字5进行比较

• 5>4，所以交换这两个数字。交换后再把4和左边的3进行比较，发现3<4，符合了步骤3中描述的左边已归位的数字比取出的数字更小，所以操作结束

• 操作结束，此时已排序区域的数字:3,4,5

• 重复步骤2，取出数字7，将它先和已排序区域的数字5进行比较，发现5<7

• 当遇到取出的数字首次与比较，排序区域的数字小于取出的数字时，不需要任何操作，直接将取出的数字放入已排序区域即可。

• 重复上述操作，直到所有数字都放入已排序区域内，即排序完成。

实现思路

• 声明一个函数，参数为一个数组

• 声明未排序区域数组，并将传进来的参数给该数组赋值

• 声明已排序区域数组，并初始化该数组的0号元素为未排序区域数组的0号元素

• 正向遍历未排序数组，起始位置为该数组的1号元素

• 将当前遍历到的值加进已排序区域

• 对已排序区域进行反向遍历，起始位置为该数组的倒数第二个元素

• 获取当前新插入元素在已排序区域的位置

• 对已排序区域新插入进来的值与当前遍历到的元素进行大小判断

• 如果新插入的值小于当前遍历到的值则进行位置互换

接下来，我们用JavaScript根据实现思路来实现下插入排序。

/*
* 1. 已排序区域的默认值为数组的0号元素
* 2. 未排序区域为数组的1号元素至数组的末尾
* 3. 给已排序区域新增未排序区域最左侧的值
* 4. 反向遍历已排序区域的数据
* 5. 将新插入的数据和当前遍历到的数据进行大小比较
* 6. 如果新插入的数据小于当前遍历到的数据则交换位置
* */

const insertSort = function (arr) {
    // 未排序区域
    let unsortedArea = arr;
    // 已排序区域
    let sortedArea = [arr[0]];
    for (let i = 1; i < unsortedArea.length; i++){
        // 已排序区域新增当前未排序区域最左侧的值
        sortedArea.push(unsortedArea[i]);
        // 反向遍历已排序区域的值，将已排序区域的值进行排序
        for(let j = sortedArea.length - 2; j >= 0; j--){
            // 当前插入值在已排序区域的位置
            let insertIndex = sortedArea.getArrayIndex(unsortedArea[i]);
            // 对已排序区域新插入进来的值与当前循环到的元素进行大小判断
            if( unsortedArea[i] < sortedArea[j]){
                [sortedArea[insertIndex],sortedArea[j]] = [sortedArea[j],sortedArea[insertIndex]];
            }
        }
    }
    return sortedArea;
};

// 原型添加查找索引函数
Array.prototype.getArrayIndex = function (obj) {
    for(let i = 0;i < this.length;i++){
        if(this[i]===obj){
            return i;
        }
    }
    return -1;
};

const arrData = [5,8,9,2,3,6,1,0,7];
console.log(insertSort(arrData));

执行结果

上述代码执行完成后，没有问题，正确排序了，但是我换了数据后上述代码就无法正常工作了。

const arrData = [5,8,9,2,3,6,1,0,7,7,7,7];
console.log(insertSort(arrData));

正确的实现

感谢评论区 @_Dreams 的指正，我才发现了自己代码的错误，正确的代码如下所示：

const insertSortOther = function (arr) {
    const len = arr.length;
    for (let i = 1; i < len; i++) {
        let temp = arr[i];
        // 默认已排序的元素
        let j = i - 1;
        // 在已排序好的队列中从后向前扫描
        while (j >= 0 && arr[j] > temp) {
            // 已排序的元素大于新元素，将该元素移到一下个位置
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = temp;
    }
    return arr;
}

测试下上述代码是否正确执行

const data = [5,8,9,2,3,6,1,0,7,7,7,7];
console.log(insertSortOther(data))

写在最后

* 文中使用的图片源自《我的第一本算法书》，如若侵权，请联系图雀社区公众号小编，作者立即删除相关图片。

* 文中如有错误，欢迎在关注公众号加群交流，如果这篇文章帮到了你，欢迎点个在看和关注????

● 前端学习数据结构与算法系列(一)：初识数据结构与算法● 前端学习数据结构与算法系列(二)：链表与数组的基础知识● 前端学习数据结构与算法系列(四)：哈希、堆和二叉查找树

·END·

图雀社区

汇聚精彩的免费实战教程

关注公众号回复 z 拉学习交流群

喜欢本文，点个“在看”告诉我