2024年回炉计划之排序算法(一)

发布时间:2024年01月18日

算法是计算机科学和信息技术中的重要领域,涉及到问题求解和数据处理的方法。要学习算法,你可能需要掌握以下一些基本知识:

  1. 基本数据结构: 了解和熟练使用各种数据结构,如数组、链表、栈、队列、树和图等。数据结构是算法的基础,不同的问题可能需要不同的数据结构来解决。

  2. 算法的时间复杂度和空间复杂度: 理解算法的运行时间和空间占用对于选择合适的算法至关重要。学习如何分析算法的时间复杂度和空间复杂度,以便能够在不同情境下做出合理的选择。

  3. 排序和搜索算法: 排序和搜索是常见的算法问题。了解各种排序算法(如冒泡排序、快速排序、归并排序等)和搜索算法(如二分查找、深度优先搜索、广度优先搜索等)。

  4. 递归和迭代: 了解递归和迭代的概念,以及它们在算法设计中的应用。有时,递归是一种简洁而优雅的解决问题的方式。

  5. 动态规划和贪心算法: 学会应用动态规划和贪心算法解决问题。这两种方法在解决一些优化问题时非常有效。

  6. 图算法: 理解图的基本概念和算法,如深度优先搜索(DFS)、广度优先搜索(BFS)、最短路径算法(Dijkstra、Bellman-Ford)、最小生成树算法(Prim、Kruskal)等。

  7. 字符串匹配算法: 了解字符串匹配问题和相关的算法,如暴力法、KMP 算法、Boyer-Moore 算法等。

  8. 数学基础: 一些算法问题涉及到数学知识,特别是在设计和分析算法时。熟悉一些基本的数学概念和运算,可能会有助于理解某些算法的原理。

  9. 算法设计模式: 了解一些常见的算法设计模式,如分治法、贪心法、动态规划等。这有助于你在解决问题时选择合适的策略。

  10. 实践和练习: 最重要的是实践。通过解决各种算法问题,参与编程竞赛,或者在实际项目中应用算法,能够更好地理解和掌握算法。

????????回归正题,特种兵有年度演习,开发者也应有年度回炉,不然脑袋锈掉。本周开启算法训练,先从排序算法开始(使用TS编码)。

一、冒泡排序

? ? ? ? 在此之前,先弄个实现一个方法:

  • generateUniqueRandomIntegers: 函数名称。
  • count: number: 生成随机整数的个数。
  • max: number: 随机整数的最大值(包含在生成范围内)。
  • min: number = 0: 随机整数的最小值,默认为 0。
/**
 * 生成指定范围、个数、不重复的随机正整数集合。
 * @param count 范围
 * @param max 最大数
 * @param min 最小数
 */
export function generateUniqueRandomIntegers(count: number, max: number, min: number = 0): number[] {
	if (count <= 0 || max <= min || !Number.isInteger(max) || !Number.isInteger(min) || !Number.isInteger(count)) {
		throw new Error("Invalid input parameters.Please ensure count is a positive integer, min is a non-negative integer, max is a positive integer greater than min.")
	}
	if (!(count <= (max - min + 1))) {
		throw new Error("(max - min + 1) should be >= count.")
	}

	const result: number[] = [];
	const uniqueNumbers: Set<number> = new Set();

	while (uniqueNumbers.size < count) {
		const randomInteger = Math.floor(Math.random() * (max - min +1)) + min;
		uniqueNumbers.add(randomInteger);
	}

	uniqueNumbers.forEach((value) => {
		result.push(value)
	})

	return  result;
}

????????冒泡排序是最简单的排序算法之一,其基本思想是将相邻的两个元素进行比较,如果顺序不对就交换它们的位置。该算法的时间复杂度为O(n^2)。

const maopaoClickListener = () => {
    let length: number = 4;
    let array: number[] = generateUniqueRandomIntegers(length, 100, 1);
    rawData.value = JSON.stringify([...array])
    for (let i = 0; i < length - 1; i++) {
        let flag = false;
        for (let j = 0; j < length - 1 - i; j++) {
            if (array[j] > array[j + 1]) {
                let temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                flag = true;
            }
        }
        if (!flag) break;
    }
    result.value = JSON.stringify([...array])
}

二、插入排序

????????插入排序的基本思想是将未排序序列(无序)中的每个元素插入到已排序序列(有序)的合适位置。该算法的时间复杂度也为O(n^2)。

? ? ? ? 第一步,分为有序、无序两部分。

? ? ? ? 第二步,取出无序部分的首个,在有序部分从后往前比较,插入到合适的部分。

? ? ? ? 拆解: 代码部分第一个for(i=1;;i++),队列首个【3】是有序的,那么,i = 1,而非 0;

? ? ? ? 拆解: 代码部分 j = i - 1; array[i] 往前逐个比较,有序部分逐个后移,直到找到合适位置;

const charuClickListener = () => {
    let length: number = 4;
    let array: number[] = generateUniqueRandomIntegers(length,100,1);
    rawData.value = JSON.stringify([...array])
    for (let i = 1; i < length; i++) {
        let itemI = array[i]
        let j = i - 1
        // 条件:有序值 大于 无序首个
        while (j > 0 && array[j] > itemI) {
            // 往后移
            array[j + 1] = array[j]
            j--
        }
        array[j + 1] = itemI
    }
    result.value = JSON.stringify([...array])
}

三、选择排序

????????选择排序的基本思想是每次选择未排序序列中最小或最大的元素,将其放到已排序序列的末尾。该算法的时间复杂度也为O(n^2)。

????????

const xuanzeClickListener = () => {
    let length: number = 4;
    let array: number[] = getArray(length);
    rawData.value = JSON.stringify({...array})
    for (let i = 0; i < length; i++) {
        let minIndex = i
        for (let j = i + 1; j < length; j++) {
            if (array[i] > array[j]) {
                minIndex = j
            }
        }
        let temp = array[i]
        array[i] = array[minIndex]
        array[minIndex] = temp
    }
    result.value = JSON.stringify({...array})
}

文章来源:https://blog.csdn.net/hhbbeijing/article/details/135666467
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。