fcedu/daily-question

不积跬步，无以至千里。不积小流，无以成江海。丰橙学院，每天一个问题，强化基础。

daily-question's Issues

基础算法：快速排序

问题

给定下面的数组，请使用 快速排序 算法使其按从小到大的顺序排列？

const list = [1, 7, 9, 8, 3, 2, 10];

...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔

丰橙解答

/**
 * 快速排序
 * @param {*} list 待排序数组
 */
function quickSort (list) {
    if (list.length < 2) { // 基线条件，当元素为空或一个时直接返回
        return list;
    } else {
        const pivot = list[0];
        
        let less = [];     // 对数据进行分区，所有小于 pivot 的放在 less 里面
        let greater = [];  // 所有大于 pivot 的放在 greater 里面

        for (let i = 1; i < list.length; i++) {
            const item = list[i];
            if (item <= pivot) {
                less.push(item);
            } else if (item > pivot) {
                greater.push(item);
            }
        }

        // 递归调用
        // 对两边分区再次分解
        return quickSort(less).concat(pivot, quickSort(greater));
    }
}

// test
const list = [1, 7, 9, 8, 3, 2, 10];
console.log(quickSort(list)); // [ 1, 2, 3, 7, 8, 9, 10 ]

时间复杂度

O(n log n)

可视化链接

https://algorithm-visualizer.org/divide-and-conquer/quicksort

测试链接

因为 leetcode 测试用例很多，所以在 leetcode 测试通过就行了:
https://leetcode-cn.com/problems/sort-an-array/

扩展阅读

快速排序使用了分治的**，参考文档 : https://zh.wikipedia.org/wiki/%E5%88%86%E6%B2%BB%E6%B3%95
这种把问题缩小的**起源于 欧几里得 算法，参考文档：https://zh.wikipedia.org/wiki/%E8%BC%BE%E8%BD%89%E7%9B%B8%E9%99%A4%E6%B3%95

基础算法：计数排序

问题

给定下面的数组，请使用 计数排序 算法使其按从小到大的顺序排列？

const list = [1, 7, 9, 8, 3, 2, 10];

...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔

丰橙解答

/**
 * 计数排序
 * @param {Array} list 待排序数组
 */
function countingSort (list) {
    // 取到最小值，后面处理负数情况
    const min = Math.abs(Math.min(...list));

    // 遍历数据，以数组的值为索引存入 countList
    const countList = [];
    list.forEach((item) => {
        // 对所有的数据执行加上 min 的操作，使得负数情况也支持
        const countIndex = item + min;
        countList[countIndex] >= 1 ? countList[countIndex]++ : (countList[countIndex] = 1)
    });

    // 对结果进行拼接
    return countList.reduce((rs, count, index) => {
        let result = rs;
        if (count >= 1) {
            // 对值进行减 min 操作恢复其原始值，出现几次便构造几个
            result = result.concat(new Array(count).fill(index - min));
        }
        return result;
    }, []);
}

// test
const list = [1, 7, 9, 8, 3, 2, 10];
console.log(countingSort(list)); // [ 1, 2, 3, 7, 8, 9, 10 ]

时间复杂度

O(n + k)

可视化链接

https://algorithm-visualizer.org/divide-and-conquer/counting-sort

测试链接

因为 leetcode 测试用例很多，所以在 leetcode 测试通过就行了:
https://leetcode-cn.com/problems/sort-an-array/

基础算法：归并排序

问题

给定下面的数组，请使用 归并排序 算法使其按从小到大的顺序排列？

const list = [1, 7, 9, 8, 3, 2, 10];

...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔

丰橙解答

/**
 *  合并函数
 * @param {Array} left 
 * @param {Array} right 
 */
function merge (left, right) { 
    const result = [];

    while (left.length > 0 && right.length > 0) {
        if (left[0] < right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }

    return result.concat(left, right);
}

/**
 * 归并排序
 * @param {Array} list 待排序列表
 */
function mergeSort (list) {
    if (list.length <= 1) return list;

    // 对数组进行分组
    // 递归调用会一直对数据分组下去，直到每个组只有一个元素
    // 然后调用  merge 一步一步的进行两两合并操作，达到归并排序的效果
    const middle = Math.floor(list.length / 2);
    const left = list.slice(0, middle);
    const right = list.slice(middle);

    return merge(mergeSort(left), mergeSort(right));
}

// test
const list = [1, 7, 9, 8, 3, 2, 10];
console.log(mergeSort(list)); // [ 1, 2, 3, 7, 8, 9, 10 ]

时间复杂度

O(n log n)

可视化链接

https://algorithm-visualizer.org/divide-and-conquer/merge-sort

测试链接

因为 leetcode 测试用例很多，所以在 leetcode 测试通过就行了:
https://leetcode-cn.com/problems/sort-an-array/

基础算法：二分查找

问题

给定下面的数组，请使用 二分查找 算法查找出 5 的索引？

const list = [1, 2, 3, 4, 5]

...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔

丰橙解答

/**
 * 二分查找
 * @param {Array} list  待查找的有序数组
 * @param {Number} item 待查找的数据
 */
function binarySearch (list, item) {
    let low = 0;                 // 记录查找部分的起始位置
    let high = list.length - 1;  // 记录查找部分的结束位置

    // 只要查找部分还有元素
    while (low <= high) {
        const mid = Math.floor((low + high) / 2); // 查找部分中间元素的索引
        const guess = list[mid];                  // 猜测的值

        // 找到了待查找的元素
        if (guess === item) {
            return mid;
        }

        // 如果猜测的值大了，则继续查找开始位置到中间位置减 1的部分
        if (guess > item) {
            high = mid - 1;
        // 如果猜测的值小了，则继续查找中间位置加 1 的部分到结束位置的部分
        } else {
            low = mid + 1;
        }
    }

    // 没有找到
    return -1;
}

// test
const list = [1, 2, 3, 4, 5];
console.log(binarySearch(list, 5)); // 4
console.log(binarySearch(list, 6)); // -1

时间复杂度

O(log n)

可视化链接

https://algorithm-visualizer.org/branch-and-bound/binary-search

测试链接

因为 leetcode 测试用例很多，所以在 leetcode 测试通过就行了:
https://leetcode-cn.com/problems/binary-search/solution/

基础算法：冒泡排序

问题

给定下面的数组，请使用 冒泡排序 算法使其按从小到大的顺序排列？

const list = [1, 7, 9, 8, 3, 2, 10];

...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔

丰橙解答

/**
 * 冒泡排序
 * @param {Array} list 待排序数组
 */
function bubbleSort(list) {

    // 每次比较两个数字
    // 如果他们的顺序不是按从小到大排列就交换
    // 直到遍历完成
    for (let i = 0; i < list.length - 1; i++) {
        for (let j = 0; j < list.length - 1 - i; j++) {
            if (list[j] > list[j + 1]) {
                const temp = list[j];
                list[j] = list[j + 1];
                list[j + 1] = temp;
            }
        }
    }

    return list;
}

// test
const list = [1, 7, 9, 8, 3, 2, 10];
console.log(bubbleSort(list)); // [ 1, 2, 3, 7, 8, 9, 10 ]

时间复杂度

O(log n x n)

可视化链接

https://algorithm-visualizer.org/brute-force/bubble-sort

测试链接

因为 leetcode 测试用例很多，所以在 leetcode 测试通过就行了:
https://leetcode-cn.com/problems/sort-an-array/

基础算法：插入排序

问题

给定下面的数组，请使用 插入排序 算法使其按从小到大的顺序排列？

const list = [1, 7, 9, 8, 3, 2, 10];

...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔

丰橙解答

/**
 * 插入排序
 * @param {Array} list 待排序数组
 */
function insertionSort (list) {
    const localList = list.splice(0);

    // 每次取出一个数据，和已排序的元素进行比较
    for (let i = 1; i < localList.length; i++) {
        let temp = localList[i];
        let j = i - 1;

        // 对已排序元素从后往前逐个取出
        // 如果取出的元素大于新元素
        while (localList[j] > temp) {

            // 则将取出的元素移到靠后的位置
            localList[j + 1] = localList[j];
            j--;
        }

        // 将新元素插入到元素中
        // j + 1 位置就是对已排序元素比较完成之后确定的位置
        localList[j + 1] = temp;
    }

    return localList;
}


// test
const list = [1, 7, 9, 8, 3, 2, 10];
console.log(insertionSort(list)); // [ 1, 2, 3, 7, 8, 9, 10 ]

时间复杂度

O(n x n)

可视化链接

https://algorithm-visualizer.org/brute-force/insertion-sort

测试链接

因为 leetcode 测试用例很多，所以在 leetcode 测试通过就行了:
https://leetcode-cn.com/problems/sort-an-array/

基础算法：希尔排序

问题

给定下面的数组，请使用 希尔排序 算法使其按从小到大的顺序排列？

const list = [1, 7, 9, 8, 3, 2, 10];

...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔

丰橙解答

/**
 * 希尔排序
 * @param {Array} list 
 */
function shellSort (list) {

    // 简单的使用 希尔增量 作为增量序列
    for (let gap = list.length >> 1; gap > 0; gap >>= 1) {

        // 使用 gap 对数据进行分组
        // 对组内数据进行排序
        // 当 gap 回归到 1 时，其实就是 插入排序了，完成插入排序也就完成整个排序操作
        for (let i = gap; i < list.length; i++) {
            let temp = list[i];
            let j;
            for (j = i - gap; j >= 0 && list[j] > temp; j -= gap) {
                list[j + gap] = list[j];
            }
            list[j + gap] = temp;
        }
    }

    return list;
}


// test
const list = [1, 7, 9, 8, 3, 2, 10];
console.log(shellSort(list)); // [ 1, 2, 3, 7, 8, 9, 10 ]

时间复杂度

和增量相关，看 wiki

可视化链接

https://algorithm-visualizer.org/brute-force/shellsort

测试链接

因为 leetcode 测试用例很多，所以在 leetcode 测试通过就行了:
https://leetcode-cn.com/problems/sort-an-array/

基础算法：选择排序

问题

给定下面的数组，请使用 选择排序 算法使其按从小到大的顺序排列？

const list = [1, 7, 9, 8, 3, 2, 10];

...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔

丰橙解答

/**
 * 查找列表最小值索引
 * @param {Array} list 待查找的列表
 */
function findSmallest (list) {
    let smallest = list[0];
    let smallestIndex = 0;

    // 遍历查找，根据判断情况不断更新最小值及其索引
    for (let i = 0; i < list.length; i++) {
        if (list[i] < smallest) {
            smallest = list[i];
            smallestIndex = i;
        }
    }

    // 最后返回当前查找列表的最小值的索引
    return smallestIndex;
}

/**
 * 选择排序算法（升序）
 * @param {Array} list 待排序的列表
 */
function selectionSort (list) {
    let newList = [];

    // 每次遍历找出其中的最小值的索引从待排序列表中删除，并塞到新的列表
    // 遍历完成新的列表便是从小到大排序好的列表
    for (let i = list.length - 1; i >= 0; i--) {
        const smallestIndex = findSmallest(list);
        newList.push(list.splice(smallestIndex, 1)[0])
    }

    return newList;
}

// test
const list = [1, 7, 9, 8, 3, 2, 10];
console.log(selectionSort(list));  // [ 1, 2, 3, 7, 8, 9, 10 ]

const listTwo = [2, 3, 1, 1, 1, 1, 1];
console.log(selectionSort(listTwo));  // [ 1, 1, 1, 1, 1, 2, 3 ]

时间复杂度

O(n x n)

可视化链接

https://algorithm-visualizer.org/brute-force/selection-sort

测试链接

因为 leetcode 测试用例很多，所以在 leetcode 测试通过就行了:
https://leetcode-cn.com/problems/sort-an-array/

基础算法：基数排序

问题

给定下面的数组，请使用 基数排序 算法使其按从小到大的顺序排列？

const list = [1, 7, 9, 8, 3, 2, 10];

...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔

丰橙解答

/**
 * 基数排序(未考虑负数情况)
 * @param {Array}} list 待排序数组
 */
function radixSort (list) {
    let result = list.slice(0);
    const max = Math.max(...list);

    let digit = `${max}`.length; // 计算待排序数组中最大数的位数
    let start = 1;
    let buckets = [];

    while (digit > 0) {

        // 对待排序数据依次求余数，以 start 作为除数，每次循环对其增大十倍
        // 以余数为索引插入 buckets 中，达到相同位数的数字排序的效果
        // 每次循环因为余数的扩大，达到不同位数的数字排序的效果
        start *= 10;
        for (let i = 0; i < result.length; i++) {
            const index = result[i] % start;
            !buckets[index] && (buckets[index] = []);
            buckets[index].push(result[i]);
        }
        result = [];

        // 对每次排序结果进行合并
        for (let i = 0; i < buckets.length; i++) {
            buckets[i] && (result = result.concat(buckets[i]));
        }
        buckets = [];
        
        digit --;
    }
    return result;
} 

// test
const list = [1, 7, 9, 8, 3, 2, 10];
console.log(radixSort(list)); // [ 1, 2, 3, 7, 8, 9, 10 ]

时间复杂度

O(n * k)

可视化链接

https://algorithm-visualizer.org/divide-and-conquer/radix-sort

测试链接

因为 leetcode 测试用例很多，所以在 leetcode 测试通过就行了:
https://leetcode-cn.com/problems/sort-an-array/

基础算法：桶排序

问题

给定下面的数组，请使用桶排序算法使其按从小到大的顺序排列？

const list = [1, 7, 9, 8, 3, 2, 10];

...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔
...🤔

丰橙解答

/**
 * 桶排序
 * @param {Array} list 待排序的数组
 * @param {Number} num 桶的个数
 */
function bucketSort(list, num = 1) {
    const max = Math.max(...list);
    const min = Math.min(...list);

    // 每个桶放置的数字的范围
    const bucketsSize = Math.ceil((max - min) / num) || 1;
    // 创建一个二维数组放置元素，一维为桶的索引，二维为桶
    const buckets = Array.from(Array(num)).map(() => Array().fill(0));

    for (let i = 0; i < list.length; i++) {

        // 计算元素应该放置在哪个桶
        let index = ~~((list[i] - min) / bucketsSize)
        index = index >= num ? num - 1 : index;
        buckets[index].push(list[i]);

        // 对桶内元素进行排序
        let j = buckets[index].length - 1;
        while (j >= 0) {
            if (buckets[index][j] < buckets[index][j - 1]) {
                [buckets[index][j], buckets[index][j - 1]] = [buckets[index][j - 1], buckets[index][j]];
            }
            j--;
        }
    }

    // 拼接所有桶的结果并返回
    return [].concat.apply([], buckets);
}

// test
const list = [1, 7, 9, 8, 3, 2, 10];
console.log(bucketSort(list, 4)); // [ 1, 2, 3, 7, 8, 9, 10 ]

时间复杂度

O(log n + k) ， k 为桶的个数

可视化链接

https://algorithm-visualizer.org/divide-and-conquer/bucket-sort

测试链接

因为 leetcode 测试用例很多，所以在 leetcode 测试通过就行了:
https://leetcode-cn.com/problems/sort-an-array/