冒泡排序的原理及优化

算法原理：

冒泡排序的基本思想是通过相邻元素的比较和交换，将最大（或最小）的元素逐步 “冒泡” 到数组的末尾（或开头）。

对未排序的各元素从头到尾依次比较相邻的两个元素大小，若顺序错误则进行交换，这样一趟比较下来，最大的元素就会被交换到最后位置。然后对除了最后一个元素之外的其他元素重复上述过程，直到整个数组有序。

升序排序的冒泡排序算法：

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;namespace _008冒泡排序
{class Program{static void Main(string[] args){//获取用户输入并存在数组里string str = Console.ReadLine();string[] strArray = str.Split(' ');int[] intArray = new int[strArray.Length];for(int i=0;i<strArray.Length;i++){int number = Convert.ToInt32(strArray[i]);intArray[i] = number;}for (int j=0;j<intArray.Length -1;j++)//进行比较的轮数{//进行比较for(int i=0;i<intArray.Length -1;i++){//判断大小if(intArray[i]>intArray[i+1])//升序排序{int temp = intArray[i];intArray[i] = intArray[i + 1];intArray[i + 1] = temp;}}}foreach (int temp in intArray ){Console.WriteLine(temp + " ");}Console.ReadKey();}}
}

但此时该算法还不是最好的，需要进行优化。此时的算法会进行不必要的比较，优化后的算法如下：

1、减少内层循环最后一位的比较次数，因为经过第一轮比较，数组的最后一位数已经是最大的了，不需要进行第二次比较，优化此时的比较次数。

2、设置一个标识位，用来判断数组内是否发生了数据交换。

        冒泡排序的基本原理是重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。在某些情况下，可能在完成所有预定的比较轮数之前，数组就已经有序了。

        例如，当输入的数组本身就接近有序，或者在排序过程中较早地就使数组达到了有序状态。如果没有标识位，冒泡排序会继续执行后续的比较轮数，即使数组已经有序。而使用标识位，一旦发现某一轮比较中没有发生任何交换，就意味着数组已经有序，此时可以提前终止排序过程，避免不必要的比较操作，从而提高算法的效率。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;namespace _008冒泡排序
{class Program{static void Main(string[] args){//获取用户输入并存在数组里string str = Console.ReadLine();string[] strArray = str.Split(' ');int[] intArray = new int[strArray.Length];for(int i=0;i<strArray.Length;i++){int number = Convert.ToInt32(strArray[i]);intArray[i] = number;}//优化算法，需要一个变量记录当前比较是否发生交换bool isChange = false;for (int j=0;j<intArray.Length -1;j++)//进行比较的轮数{//进行比较for(int i=0;i<intArray.Length -1-j;i++)//优化算法，减少不必要的比较次数{//判断大小if (intArray[i]>intArray[i+1])//升序排序{int temp = intArray[i];intArray[i] = intArray[i + 1];intArray[i + 1] = temp;isChange = true;}}if(isChange ==false ){break;}}foreach (int temp in intArray ){Console.WriteLine(temp + " ");}Console.ReadKey();}}
}