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