C#基础（14）冒泡排序

前言

其实到上一节结构体我们就已经将c#的基础知识点大概讲完，接下来我们会讲解一些关于算法相关的东西。

我们一样来问一下gpt吧：

Q:解释算法

算法是一组有序的逻辑步骤，用于解决特定问题或执行特定任务。它可以是一个计算过程、一个计算机程序或一套规则。

算法具有以下特征：

输入：算法具有零个或多个输入变量，这些变量是算法运行时需要提供的数据。
输出：算法产生一个或多个输出结果，这些结果是通过对输入数据进行计算和处理得到的。
有穷性：算法必须在有限的步骤内停止，不会无限循环或进入死循环。
确定性：算法中的每个步骤必须明确定义，不会产生二义性或歧义。
可行性：算法必须可以实际执行，能够在有限的时间内得到结果。
通用性：算法可以用来解决一类问题，而不仅仅是特定的实例。

在计算机科学中，算法通常描述为一系列的操作、条件语句、循环结构和函数调用，用来指示计算机在进行数据处理时应遵循的步骤和规则。算法可以用伪代码、流程图、程序代码或其他可读性强的形式来描述。

算法的设计和分析是计算机科学中的重要研究领域。一个好的算法可以显著提高计算效率和资源利用率，而糟糕的算法则可能导致低效或不可接受的性能。因此，研究者和开发者在编写程序时应该选择和优化适当的算法来解决问题。

这样看上去难免还是觉得很复杂，那我们再百度一下：

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。

还是麻烦了，那博主再给你精简一点：

算法就是解决一些问题的计算方法。

这个想毕你就很快就能理解了，哦，其实就是一个方程式嘛，我带入一个值它给我一个值。

对的，算法也是这样，当然他可能输入很多个值，出来很多个值，但这些都不重要，你只要知道它是用来解决实际问题的方法，算法高不高级，就看你解决问题所需要的时间少不少。

那其实算法也并不难嘛。

当然，入门肯定不难。

而今天，我们就来讲解第一个入门的算法，冒泡排序。

排序

排序：是计算机内经常进行的一种操作，，其目的是讲一组没有顺序的记录按一定顺序排好。

程序中，经常对数组排序

冒泡排序的基本原理

看到这个图，不知道你是否有一些想法：

通过重复比较相邻两个元素的大小，并根据比较结果交换位置，将最大（或最小）的元素逐步“冒泡”到数列的末尾（或开头）。

对，就像鱼儿吐泡泡一样，这样我们就只需要反复比较n-1次（这样才能保证完全排完），就能得到最终的排列结果。

代码实现

我们先来实现从头开始，第一个数的比较。

首先我们来分析一下思路，我们先声明一个数组过后，我们就要开始遍历了，既然我们是和数组下一个元素比较，那么我们就要考虑到什么时候停止。

当然是元素如果排到最后一个就可以停止了。

那假设我们的元素会排到数组的的末尾，那他还会比较吗？显然是不用的，所以我们遍历的时候，也只用遍历到倒数第二个元素就可以了，因为在倒数第二个元素的比较就是我们最后的比较。

以下是我们实现一个数的比较的代码。

using System;
using System.Runtime.Serialization.Formatters;class Program
{static void Main(string[] args){int[] arr = new int[] { 8, 7, 1, 5, 4, 2, 6, 3, 9 };for (int i = 0; i < arr.Length-1; i++){if (arr[i] > arr[i+1]) //大于升序，小于降序{int temp = arr[i];//声明一个临时变量存储值，避免值消失arr[i] = arr[i+1];arr[i+1] = temp;}}for (int i = 0;i < arr.Length;i++){Console.WriteLine(arr[i]);}}
}

然后我们就要进行多轮比较吧，那我们假设不知道里面有个数，那我们又假设最坏的情况，就是我们必须遍历到最后一个数才能将数组完全排序完毕，那简单了：

我们有多少个数就排多少次，这样一定能排完，所以我们在外层加一个for循环。

using System;
using System.Runtime.Serialization.Formatters;class Program
{static void Main(string[] args){int[] arr = new int[] { 8, 7, 1, 5, 4, 2, 6, 3, 9 };for (int j = 0; j < arr.Length; j++){for (int i = 0; i < arr.Length - 1; i++){if (arr[i] > arr[i + 1]) //大于升序，小于降序{int temp = arr[i];//声明一个临时变量存储值，避免值消失arr[i] = arr[i + 1];arr[i + 1] = temp;}}}for (int i = 0;i < arr.Length;i++){Console.WriteLine(arr[i]);}}
}

以上就是最基本的冒泡排序的c#实现，我们运行程序，就能看到他能将我们想要的数组给排列好。

优化

我想你已经掌握了冒泡排序的基本思路，但我还想提出几点可以优化的地方，但这个相对来说比较难理解。为了方便你观察流程，博主接下来的代码将每一次遍历的结果都打印了出来。

首先，我们在一次比较中并不是一定要遍历完所有数的，在前面比较中就确定了位置的数，其实就没必要继续比较了
特殊情况的优化：排序在前面几个数的时候就完成了排序，就不用继续排序了。

废话少说，上代码，详情请看注释，不懂可以私信博主。

你可以尝试把优化点去掉，然后去感受一下原本的比较和现在的比较的差别。

当然你可能会从时间复杂度O(n2)上挑刺上说这种优化没有必要（因为时间复杂度没有变），但你要明白，性能优化，永远是程序员最大的敌人。你学习的更多是这种思路：

有没有多余的计算进行？能否简洁运算？能否更快地得出答案？

而不是死啃书本，你书本上的东西都要落实到实际。

using System;
using System.Runtime.Serialization.Formatters;class Program
{static void Main(string[] args){int[] arr = new int[] { 8, 7, 1, 5, 4, 2, 6, 3, 9 };bool isMPSort=false;for (int j = 0; j < arr.Length; j++){isMPSort = false;for (int i = 0; i < arr.Length - 1-j; i++)//第一个优化点{if (arr[i] > arr[i + 1]) //大于升序，小于降序{isMPSort = true;//第二个优化点int temp = arr[i];//声明一个临时变量存储值，避免值消失arr[i] = arr[i + 1];arr[i + 1] = temp;}}if (!isMPSort)//如果没有进行排序，其实是数组排序已经完成{break;}for (int i = 0; i < arr.Length; i++){Console.Write(" " + arr[i]);}Console.WriteLine();}for (int i = 0;i < arr.Length;i++){Console.Write(" "+arr[i]);}}
}