2024年回炉计划之排序算法（一）

本文主要是介绍2024年回炉计划之排序算法（一），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

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 = ifor (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})
}

这篇关于2024年回炉计划之排序算法（一）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---