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

/**
 * 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));

/*
* 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));

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))

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