C#之冒泡排序_c#冒泡排序

冒泡排序介绍

冒泡排序，Bubble Sort      一个简单且常用的排序算法。因最大或最小的元素会经过交换慢慢出现在数列顶端，好似元素冒出来一样，得名“冒泡排序”。

冒泡排序原理

1.比较相邻的元素，若第一个比第二个大则交换他们两个。

2.对每一组相邻的元素做同样的工作（从开始的第一对到最后的最后一对）。

3.针对除最后一个元素外的所有元素重复以上的步骤。

4.重复对未定位到合适位置的元素操作上述步骤直至排序完成。

以上为升序原理，降序原理等同于升序原理。）

冒泡排序分析

冒泡排序最好的时间复杂度为O(n)；

此时数组本身有序，只需要一轮即可完成冒泡排序。因此时间复杂度为O(n)

冒泡排序最坏的时间复杂度为O(n*n)；

此时数组本身为逆序，需要n轮完成冒泡排序。因此时间复杂度为O(n*n)

冒泡排序的平均时间复杂度为O(n*n)。

由于最坏时间复杂度分析，平均时间复杂度为O(n*n)

冒泡排序是稳定的排序算法。

因为在交换中我们只交换两个元素，元素相等时不变，因此相等元素在排序前后相对位置不会发生变化，所以是稳定的排序算法。

冒泡排序C#实现

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace Bubble_Sort
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int[] data = new int[8];
            Console.WriteLine("原数组为：");
            Random random = new Random();
            for (int i = 0; i < data.Length; i++)
            {
                data[i] = random.Next(1,500);
                Console.Write(data[i] + " ");
            }
            Console.WriteLine();
            Console.WriteLine("升序后数组为：");
            // 升序
            int temp;
            for(int i = 0; i < data.Length; i++)
            {
                bool flag = true;
                for(int j = 0; j < data.Length - 1 - i; j++)
                {
                    if (data[j] > data[j + 1])
                    {
                        temp = data[j + 1];
                        data[j + 1] = data[j];
                        data[j] = temp;
                        flag = false;
                    }
                }
                if (flag)
                {
                    break;
                }
            }
            for(int i = 0; i < data.Length; i++)
            {
                Console.Write(data[i] + " ");
            }
            Console.ReadLine();
        }
    }
}