基于C#语言冒泡排序算法的分析研究

基于 C#语言冒泡排序算法的分析研究

李秀珍 李 芳

山东工业职业学院

潍坊工程职业学院

山东省青州市

摘要：信息时代，计算机程序的主要功能之一就是数据处理，而数据排序则是数据处理必不可少的工作。文章通过对冒泡排序算法的缺点进行分析，继而引入两个标志位以此来优化算法。最后通过实验数据对比算法优化前和优化后的交换次数和执行时间，证明了算法优化的有效性。

关键字：C#，冒泡排序，内部排序，标志位

0 引言

在当今信息时代，数据处理是计算机程序的主要工作，而数据处理过程中必不可少的步骤就是对数据进行排序。因此，排序算法的效率对数据处理有着重要的影响。笔者从排序的定义、冒泡排序算法的定义、实现以及优化等方面进行研究分析，为日常工作中的数据处理提供行之有效的参考。

1 排序

1. 1. 排序的定义及分类

排序是按关键字的非递减或非递增顺序对一组记录重新进行排列的操作。^[1]

由于数量不同，导致排序过程中占用的硬件设备不同。根据排序过程是否占用存储设备，排序可分为两类，内部排序和外部排序。内部排序是指整个排序过程在内存便能完成，不用访问外存。^[1]

外部排序是指待排序数量巨大，内存无法一次性进行全部存储，在排序过程中需要对外存进行访问的排序过程。

1. 2. 排序的稳定性

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，有r[i]，r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。^[2]

2 冒泡排序算法及实现

2.1 冒泡排序算法

冒泡排序是指不断地比较两两相邻地数据，较小者向上浮动，较大者向下浮动。^[3]

2.2 算法描述

假设待排序元素为{n1，n2，n3……nk}：

①从n1开始比较两两相邻元素，如果n1>n2,交换n2和n1的位置。接着比较n2和n3的大小，如果n2>n3，交换n2和n3的位置，剩下的以此类推，该轮结束后，nk的位置上存放的是最大数。

②仍然从n1开始比较两两相邻元素的大小，不同的是这一轮只要比较到n(k-1)的位置即可。待该轮比较结束，n(k-1)的位置上存放的就是第二大数据。

③继续从n1开始比较两两相邻元素的大小，直到所有的待排序元素有序为止。

2.3 算法实现

using System;

using System.Diagnostics;

namespace ConsoleApp17

{

class Program

{

static void Main(string[] args)

{

int[] myArray = new int[6];

for (int i = 0; i < myArray.Length; i++)//从键盘上输入数据，为数组元素赋值

{

myArray[i] = Convert.ToInt32(Console.ReadLine());

}

Console.WriteLine("排序前数值：");

for (int p = 0; p < myArray.Length; p++)//输出排序前的数组数据

{

if (p % 10 == 0)

Console.WriteLine();

Console.Write("{0,8:d}", myArray[p]);

}

Console.WriteLine();

Stopwatch sw = new Stopwatch();

sw.Start();//记录冒泡排序的时间

for (int j = 0; j < myArray.Length; j++)//外层循环用于控制轮数

{

for (int m = 0; m < myArray.Length-j-1; m++)/*内层循环用于控制每轮中两两相邻的数据交换*/

{

if (myArray[m]

{

int t = myArray[m];

myArray[m] = myArray[m + 1];

myArray[m + 1] = t;

}

Console.WriteLine();

Console.WriteLine("第{0}趟第{1}次交换的结果是：", j, m);

for (int k=0;k

Console.Write("{0,8:d}", myArray[k]);

}

}

sw.Stop();//计时结束

TimeSpan ts = sw.Elapsed;

Console.WriteLine();

Console.WriteLine("DateTime costed for Shuffle function is: {0}ms", ts.TotalMilliseconds);//输出冒泡排序的时间

Console.WriteLine();

Console.WriteLine("排序后数值：");

for (int q = 0; q < myArray.Length; q++)//输出排序后的数据

{

if (q % 10 == 0)

Console.WriteLine();

Console.Write("{0,8:d}", myArray[q]);

}

}

}

}

2.4 过程分析

以数组{6,5，4，3，1，2}为例讲解冒泡排序程序的执行过程：

当外循环j=0时，内循环变量m的取值范围是{0，1，2，3，4}：

当m=0时，判断myArray[0]< myArray[1]是否成立，此时myArray[0]的值为6，myArray[1]的值为5，不成立，不执行交换。

当m=1时，判断myArray[1]< myArray[2]是否成立，此时myArray[1]的值为5，myArray[2]的值为4，不成立，不执行交换。

当m=2时，判断myArray[2]< myArray[3]是否成立，此时myArray[2]的值为4，myArray[3]的值为3，不成立，不执行交换。

当m=3时，判断myArray[3]< myArray[4]是否成立，此时myArray[3]的值为3，myArray[4]的值为1，不成立，不执行交换。

当m=4时，判断myArray[4]< myArray[5]是否成立，此时myArray[4]的值为1，myArray[5]的值为2，判断条件成立，交换myArray[4]和myArray[5]的值，交换后的数组顺序是{6,5，4，3，2，1}。

当m=5时，内循环条件m < myArray.Length-j-1代入相应的变量值变为5<5,不再成立，内层循环结束。

第一趟排序结束后，数组顺序是：{6,5,4,3,2,1}。

外循环变量j=1时，内循环变量m的取值范围是{0,1,2,3}，执行过程与第一趟类似，在此不再详细赘述。

2.5性能分析

时间复杂度：以待排序列长度为n为例，冒泡排序算法执行的次数为1+2+3+4+……n-1，得到的次数总和为（n-1）n／2，简记为O(n²)。

稳定性：因冒泡排序过程中，对于相等的数据不进行交换位置，所以冒泡排序算法是稳定的排序算法。^[4]

3 算法优化

3.1 第一次优化

以数组{6,5,4,3,1,2}为例，经过冒泡算法排序的过程如下：

第0趟第0次交换的结果是：

6 5 4 3 1 2

第0趟第1次交换的结果是：

6 5 4 3 1 2

第0趟第2次交换的结果是：

6 5 4 3 1 2

第0趟第3次交换的结果是：

6 5 4 3 1 2

第0趟第4次交换的结果是：

6 5 4 3 2 1

第1趟第0次交换的结果是：

6 5 4 3 2 1

第1趟第1次交换的结果是：

6 5 4 3 2 1

第1趟第2次交换的结果是：

6 5 4 3 2 1

第1趟第3次交换的结果是：

6 5 4 3 2 1

第2趟第0次交换的结果是：

6 5 4 3 2 1

第2趟第1次交换的结果是：

6 5 4 3 2 1

第2趟第2次交换的结果是：

6 5 4 3 2 1

第3趟第0次交换的结果是：

6 5 4 3 2 1

第3趟第1次交换的结果是：

6 5 4 3 2 1

第4趟第0次交换的结果是：

6 5 4 3 2 1

可以发现，数组在第一趟排序结束后就已经有序，无须在进行后续排序，但原算法仍然按照既定的程序执行，浪费大量时间。

解决这个问题，可以在外循环中设置一个标志位，若内层循环发生位置变换，那么该标志位的值发生变化，若内层循环结束，标志位的值没有发生变化，说明全部数据已经有序，无须再进行后面的外层循环，对外层循环进行强制结束。

实现代码如下：

for (int j = 0; j < myArray.Length; j++)

{

int flag = 1;//设置标志位，以此记录内层循环是否发生位置交换

for (int m = 0; m < myArray.Length-j-1; m++)

{

if (myArray[m]

{

int t = myArray[m];

myArray[m] = myArray[m + 1];

myArray[m + 1] = t;

flag = 0;//一旦发生位置交换，flag的值由1变为0

}

Console.WriteLine();

Console.WriteLine("第{0}趟第{1}次交换的结果是：", j, m);

for (int k=0;k

Console.Write("{0,8:d}", myArray[k]);

}

if (flag == 1) //如果flag的值为1，则后续的外层循环将不再执行

break ;

}

执行结果：

第0趟第0次交换的结果是：

6 5 4 3 1 2

第0趟第1次交换的结果是：

6 5 4 3 1 2

第0趟第2次交换的结果是：

6 5 4 3 1 2

第0趟第3次交换的结果是：

6 5 4 3 1 2

第0趟第4次交换的结果是：

6 5 4 3 2 1

第1趟第0次交换的结果是：

6 5 4 3 2 1

第1趟第1次交换的结果是：

6 5 4 3 2 1

第1趟第2次交换的结果是：

6 5 4 3 2 1

第1趟第3次交换的结果是：

6 5 4 3 2 1

通过运行结果对比，第一次优化后的执行次数、时间较未优化之前分别减少了7次，说明优化算法起了有效作用。

3.2 第二次优化

以数组{6，4，7，5，1，3}为例，整个冒泡排序运行结果是（该结果是在第一次优化的基础上进行的）：

第0趟第0次交换的结果是：

6 4 7 5 1 3

第0趟第1次交换的结果是：

6 7 4 5 1 3

第0趟第2次交换的结果是：

6 7 5 4 1 3

第0趟第3次交换的结果是：

6 7 5 4 1 3

第0趟第4次交换的结果是：

6 7 5 4 3 1

第1趟第0次交换的结果是：

7 6 5 4 3 1

第1趟第1次交换的结果是：

7 6 5 4 3 1

第1趟第2次交换的结果是：

7 6 5 4 3 1

第1趟第3次交换的结果是：

7 6 5 4 3 1

第2趟第0次交换的结果是：

7 6 5 4 3 1

第2趟第1次交换的结果是：

7 6 5 4 3 1

第2趟第2次交换的结果是：

7 6 5 4 3 1

通过运行结果可以发现，第2趟的比较是多余的，因为所有数据在第1趟第0次的排序后已经有序。

针对该问题，可以利用一个标志位，记录当前第m趟发生交换的最后一个位置，在进行第m+1趟比较时，内循环只要执行到标志位的位置即可。基于此想法，进一步优化冒泡排序代码：

int len = myArray.Length-1;//定义变量len，以此记录当前内循环最后的交换位置

for (int j = 0; j < myArray.Length; j++)

{

int flag = 1;

for (int m = 0; m < len; m++)

{

if (myArray[m]

{

int t = myArray[m];

myArray[m] = myArray[m + 1];

myArray[m + 1] = t;

flag = 0;

temppos = m;//变量temppos用来记录每次的交换位置

}

Console.WriteLine();

Console.WriteLine("第{0}趟第{1}次交换的结果是：", j, m);

for (int k=0;k

Console.Write("{0,8:d}", myArray[k]);

}

len = temppos;//将内循环最后的交换位置赋值给len

if (flag == 1)

break ;

}

运行结果：

第0趟第0次交换的结果是：

6 4 7 5 1 3

第0趟第1次交换的结果是：

6 7 4 5 1 3

第0趟第2次交换的结果是：

6 7 5 4 1 3

第0趟第3次交换的结果是：

6 7 5 4 1 3

第0趟第4次交换的结果是：

6 7 5 4 3 1

第1趟第0次交换的结果是：

7 6 5 4 3 1

第1趟第1次交换的结果是：

7 6 5 4 3 1

第1趟第2次交换的结果是：

7 6 5 4 3 1

第1趟第3次交换的结果是：

7 6 5 4 3 1

优化后的运行次数较未优化的程序减少3次，说明第二次优化方法有效提高了排序效率。

3.3 优化后的冒泡算法与未优化的冒泡算法的比较分析

对3.2给出的优化算法和未优化的算法用C#语言实现，用6组数据进行了对比分析，利用myArray[i] = ra.Next(1, 65500)生成65500以内的随机数，然后测试数组长度分别为10、50、100、150、200、500时两种算法的效率，记录下了两种算法下交换的总次数和执行时间，如下表1所示：

表1 未优化的算法和优化后算法的效率比较

通过表1，可以得出以下信息：

（1）优化后的算法交换次数较未优化算法交换次数较少约1/2.

（2）当数组长度为500时，优化后的算法优势较大。所以大量数据排序时可优先采用优化后的冒泡排序算法。

4 总结

数据的排序在数据处理中占据着非常重要的地位。虽然现阶段采用快速排序算法较多，但冒泡排序在稳定性方面有优势。文章通过对冒泡排序算法引入两个标志位分别用来记录内循环是否发生交换以及交换发生的位置，从而达到了减少交换次数的目的，最后通过实验证明了优化的有效性和适用性。

参考文献：

[1]严蔚敏，吴伟民.数据结构[M].北京：清华大学出版社，2001.

[2]谢婷. 基于C语言的常用排序算法比较研究[J]. 湖南城市学院学报(自然科学版), 2016, 25(004):95-96.

[3]梁建华. 基于C语言的数据结构中排序算法的分析研究[J]. 漯河职业技术学院学报, 2019, 018(003):32-34.

[4]龚佳, 刘远军. 一种双向冒泡排序算法的C语言实现及其效率分析[J]. 福建电脑, 2013, 29(011):55-56.