TypeScript实现十大排序算法(一) - 冒泡排序
一. 冒泡排序的定义
冒泡排序是一种简单的排序方法。
- 基本思路是通过两两比较相邻的元素并交换它们的位置，从而使整个序列按照顺序排列。
- 该算法一趟排序后，最大值总是会移到数组最后面，那么接下来就不用再考虑这个最大值。
- 一直重复这样的操作，最终就可以得到排序完成的数组。
这种算法是稳定的，即相等元素的相对位置不会发生变化。
- 而且在最坏情况下，时间复杂度为O(n^2)，在最好情况下，时间复杂度为O(n)。
因此，冒泡排序适用于数据规模小的场景。
二. 冒泡排序的流程
冒泡排序的流程如下：
- 从第一个元素开始，逐一比较相邻元素的大小。
- 如果前一个元素比后一个元素大，则交换位置。
- 在第一轮比较结束后，最大的元素被移动到了最后一个位置。
- 在下一轮比较中，不再考虑最后一个位置的元素，重复上述操作。
- 每轮比较结束后，需要排序的元素数量减一，直到没有需要排序的元素。
- 排序结束。
- 这个流程会一直循环，直到所有元素都有序排列为止。
三. 冒泡排序的图解
image-20230219183028618
image-20230219183037940
冒泡排序
四. 冒泡排序的代码
// 定义函数，用于实现冒泡排序算法
function bubbleSort(arr: number[]): number[] {
// 外层循环，控制需要比较的轮数
for (let i = 0; i < arr.length - 1; i++) {
// 内层循环，控制每轮需要比较的次数
for (let j = 0; j < arr.length - 1 - i; j++) {
// 如果前一个元素比后一个元素大，则交换它们的位置
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
// 返回排序后的数组
return arr;
}
// 测试代码
const arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(bubbleSort(arr));
// 输出：[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
说明：
- 冒泡排序是一种暴力枚举算法，通过多次循环比较相邻的元素，把最大的元素逐渐冒泡到数组末端。
- 外层循环：控制排序的趟数，每一轮排序会把最大的元素放到最后，因此每次循环需要比较的元素个数也会逐渐减少。
- 内层循环：比较相邻元素，如果左边元素比右边元素大，则交换位置。
- 冒泡排序是一种时间复杂度较高的算法，一般不用于大数据量的排序，但它很容易理解，是一种初学者学习排序算法的好
五. 冒泡排序的时间复杂度
在冒泡排序中，每次比较两个相邻的元素，并交换他们的位置，如果左边的元素比右边的元素大，则交换它们的位置。这样的比较和交换的过程可以用一个循环实现。
-
在最好的情况下，数组已经是有序的，那么比较和交换的次数是最少的。
- 在这种情况下，比较次数是n-1次，交换次数是0次，其中n是数组的长度。
-
在最坏的情况下，数组是逆序的，那么比较和交换的次数是最多的。
- 在这种情况下，比较次数是n-1次，交换次数是n(n-1)/2次，其中n是数组的长度。
-
在平均情况下，比较和交换的次数取决于数组的排列方式。
- 一般来说，平均情况下比较次数是n-1次，交换次数是n(n-1)/4次，其中n是数组的长度。
冒泡排序的时间复杂度分析：
- 最好情况：当序列已经有序，每次比较和交换操作都不会进行，只需要进行n-1次比较，时间复杂度为O(n)。
- 最坏情况：当序列完全逆序，需要进行n-1轮比较和n-1次交换操作，时间复杂度为O(n^2)。
- 平均情况：需要进行的比较和交换操作的次数在所有情况中的平均值，时间复杂度也是O(n^2)。
由此可见，冒泡排序的时间复杂度主要取决于数据的初始顺序，最坏情况下时间复杂度是O(n^2)，不适用于大规模数据的排序。
六. 冒泡排序的总结
冒泡排序适用于数据规模较小的情况，因为它的时间复杂度为O(n^2)，对于大数据量的排序会变得很慢。
同时，它的实现简单，代码实现也容易理解，适用于学习排序算法的初学者。
但是，在实际的应用中，冒泡排序并不常用，因为它的效率较低。
此外，冒泡排序比较和交换的次数较多，占用更多的存储空间和时间，不适用于处理大数据量的情况。
因此，在实际应用中，冒泡排序通常被更高效的排序算法代替，如快速排序、归并排序等。
本文由mdnice多平台发布
