2.冒泡排序
2.1 基础知识
核心思想
冒泡排序的核心思想是通过比较和交换来确定未排序区域中的最大元素，然后将其放置到未排序区域的末尾。这个过程就像在水中冒泡一样，较大的元素逐渐上浮到列表的末尾。
算法步骤
比较相邻元素：
从数组的第一个元素开始，依次比较相邻的两个元素，比如比较第一个元素和第二个元素。交换元素位置：
如果第一个元素比第二个元素大（顺序不对），则交换它们的位置；如果第一个元素比第二个元素小（顺序正确），则不进行交换。移动到下一组相邻元素：
接着，移动到数组中的下一组相邻元素，重复步骤1和步骤2。一轮结束：
当完成一轮比较和可能的交换后，数组中的最大元素就会“冒泡”到数组的最末尾。缩小未排序区域：
然后，将未排序区域缩小，不考虑已经排序好的元素。重复以上步骤：
重复上述步骤，直到整个数组都已排序。这意味着进行 n-1 轮比较和交换，其中 n 是数组的长度。
时间复杂度
冒泡排序的最坏时间复杂度是 O(n^2)，平均时间复杂度也是 O(n^2)。在最坏情况下，需要进行 n-1 轮比较和交换，每一轮的比较和交换操作都是 O(1) 的时间复杂度。最好情况下是 O(n)，即数组已经有序，只需一轮比较即可跳出循环。
空间复杂度
冒泡排序是一种原地排序算法，它只需要常数级别的额外空间用于存储临时变量，因此空间复杂度是 O(1)。
稳定性
冒泡排序是稳定的。因为只有当相邻元素的大小关系与排序要求相反时才会发生交换，相等的元素在排序过程中不会发生位置交换，它们在原始序列中的相对顺序得到保留。
优化
为了提高效率，可以使用一个标志来记录是否在一轮中发生了交换。如果一轮中没有发生交换，说明数组已经有序，可以提前结束排序，减少不必要的比较和交换操作。
代码步骤
外层循环：
通过外层循环，控制整个排序的轮数。总共有数组长度-1轮。每一轮，都能确保数组中的一个元素处于其最终排序的位置。内层循环：
在每一轮中，通过内层循环从数组的开头开始，逐个比较相邻的元素，直到未排序区域末尾。这样，每一轮都能找到当前未排序区域的最大元素，并将其交换到正确的位置。比较相邻元素：
在内层循环中，比较相邻的两个元素。如果前一个元素大于后一个元素，就交换它们的位置。这样，较大的元素就像气泡一样逐渐向上“冒”。提前结束判断：
每一轮的开始，设定一个标志，如果整个轮次中没有发生任何交换，说明数组已经有序，可以提前结束排序。重复直到完成：
通过不断重复上述步骤，直到整个数组完全有序。每一轮都会确定一个元素的最终位置，所以总共需要 array.Length - 1 轮。
总结说明
尽管冒泡排序算法简单易懂，但在实际应用中由于其时间复杂度较高，一般不推荐对大规模数据集使用。
2.2 思路框架
static void BubbleSort(ref int[] array)
{
循环：有多少元素循环多少-1轮
{
定义交换标识
循环：有多少未排序元素比较多少-1次
{
前一个元素比后一个元素大就交换并改交换标识
}
没交换就直接退出
}
}
2.3 纯净代码
static void BubbleSort(ref int[] array)
{
for (int i = 0; i < array.Length - 1; i++)
{
bool isSwap = false;
for (int j = 0; j < array.Length - i - 1; j++)
{
if (array[j] > array[j + 1])
{
SortHelpTool.Swap(ref array[j], ref array[j + 1]);
isSwap = true;
}
}
if (!isSwap)
{
return;
}
}
}
require("Lesson01_SortHelpTool")
-- 冒泡排序函数
function BubbleSort(array)
local arrayLength = #array
for i = 1, arrayLength - 1 do
local isSwap = false
for j = 1, arrayLength - i do
if array[j] > array[j + 1] then
SortHelpTool.Swap(array, j, j + 1)
isSwap = true
end
end
if not isSwap then
break
end
end
end
SortHelpTool.PrintArray(SortHelpTool.arrayToSort, "排序前")
BubbleSort(SortHelpTool.arrayToSort)
SortHelpTool.PrintArray(SortHelpTool.arrayToSort, "排序后")
2.4 带注释代码
using System;
using Lesson01_概述;
class Program
{
static void Main()
{
// 输出排序前的数组
Console.WriteLine("排序前的数组:");
SortHelpTool.PrintArray(SortHelpTool.arrayToSort);
// 调用冒泡排序函数
BubbleSort(ref SortHelpTool.arrayToSort);
// 输出排序后的数组
Console.WriteLine("排序后的数组:");
SortHelpTool.PrintArray(SortHelpTool.arrayToSort);
}
// 冒泡排序函数
static void BubbleSort(ref int[] array)
{
// 数组有多长，一共就有多少-1轮，-1是因为最后一轮已经冒出了array.Length - 1个数，最后一个数自动有序
for (int i = 0; i < array.Length - 1; i++)
{
// 重置 isSwap
bool isSwap = false;
// 每轮从头开始比较，比较到未排序区尾-1，否则 j + 1 就数组越界了
// 每比较完 i 轮，代表确定了 i 个元素的位置，未排序区的元素就会减 i
for (int j = 0; j < array.Length - i - 1; j++)
{
// 大的在前就交换，使用 ref
if (array[j] > array[j + 1])
{
SortHelpTool.Swap(ref array[j], ref array[j + 1]);
isSwap = true;
// 输出排序中的数组 i和j都+1是因为第几轮和第几个元素是从1开始 数组从0开始
Console.WriteLine($"第{i + 1}轮 第{j + 1}个元素和第{j + 2}个元素进行交换 交换后的数组:");
SortHelpTool.PrintArray(SortHelpTool.arrayToSort);
}
}
// 如果这一轮没有发生交换，说明数组已经有序，提前结束排序
if (!isSwap)
{
Console.WriteLine($"有发生交换，说明数组已经有序，提前结束排序");
return;
}
}
}
}
2.5 运行结果
排序前的数组:
5 2 8 1 7 3 10 4 6 9
第1轮 第1个元素和第2个元素进行交换 交换后的数组:
2 5 8 1 7 3 10 4 6 9
第1轮 第3个元素和第4个元素进行交换 交换后的数组:
2 5 1 8 7 3 10 4 6 9
第1轮 第4个元素和第5个元素进行交换 交换后的数组:
2 5 1 7 8 3 10 4 6 9
第1轮 第5个元素和第6个元素进行交换 交换后的数组:
2 5 1 7 3 8 10 4 6 9
第1轮 第7个元素和第8个元素进行交换 交换后的数组:
2 5 1 7 3 8 4 10 6 9
第1轮 第8个元素和第9个元素进行交换 交换后的数组:
2 5 1 7 3 8 4 6 10 9
第1轮 第9个元素和第10个元素进行交换 交换后的数组:
2 5 1 7 3 8 4 6 9 10
第2轮 第2个元素和第3个元素进行交换 交换后的数组:
2 1 5 7 3 8 4 6 9 10
第2轮 第4个元素和第5个元素进行交换 交换后的数组:
2 1 5 3 7 8 4 6 9 10
第2轮 第6个元素和第7个元素进行交换 交换后的数组:
2 1 5 3 7 4 8 6 9 10
第2轮 第7个元素和第8个元素进行交换 交换后的数组:
2 1 5 3 7 4 6 8 9 10
第3轮 第1个元素和第2个元素进行交换 交换后的数组:
1 2 5 3 7 4 6 8 9 10
第3轮 第3个元素和第4个元素进行交换 交换后的数组:
1 2 3 5 7 4 6 8 9 10
第3轮 第5个元素和第6个元素进行交换 交换后的数组:
1 2 3 5 4 7 6 8 9 10
第3轮 第6个元素和第7个元素进行交换 交换后的数组:
1 2 3 5 4 6 7 8 9 10
第4轮 第4个元素和第5个元素进行交换 交换后的数组:
1 2 3 4 5 6 7 8 9 10
有发生交换，说明数组已经有序，提前结束排序
排序后的数组:
1 2 3 4 5 6 7 8 9 10
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com
