冒泡排序

朱雀 2021-03-26 14:13 482阅读 0赞

### 冒泡排序 ###

> 冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

### 必须要知道的事情关于冒泡 ###

**以从小到大排序举例**

*  冒泡排序循环比较的轮数是总数-1，比如两个数排序，一轮下来就确定最大的那个值，第二大的就是另一个数
 *  每轮的排序结果是最大的跑到最后，并且之后最大的那个值位置确定不再参与比较，位置不会发生变化 --- 冒泡排序是稳定的
 *  核心点，是相邻的数据比较，如果前者大于后者就交换，否者就将后者与下一个后者比较以此类推
 *  找到每一轮结束比较的位置是难点

### 如何找到每轮结束位置的值，规律 ###

// 假如这里有个数组 arr:{2,7,6,4,11,3} 共6个值
    
    //第一轮：
    2>7?交换：不交换 ==> 不交换  ：2，7，6，4，11，3
    7>6?交换：不交换==> 交换          2，6，7，4，11，3
    7>4?交换：不交换==> 交换          2，6，4，7，11，3
    7>11?交换：不交换==> 不交换     2，6，4，7，11，3
    11>3?交换：不交换 ==>交换        2，6，4，7，3，11        
    // 到这里，第一轮结束， 比较次数是 6-1， 第二轮比较结束的位置必定是 倒数第二位，也就是 6-2  也就是轮数增加，比较次数减少 （符合线性规则：y=n-x，括号里面的仅供参考）
    第二轮，你也可以按照上面去推理一下

### 冒泡排序代码 ###

using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    
    namespace BubbleSort1
    {
        class Program
        {
            static void Main(string[] args)
            {
    
                //使用冒泡排序对数组排序
                int[] arr = new int[] { 5, 1, 7, 2, 4, 9, 3 };
                Console.WriteLine("排序之前：");
                foreach(int i in arr)
                {
                    Console.Write(i.ToString() + " ");
                }
                Console.WriteLine();
                int tmp;//临时变量，用来交换
    
                for(int i=0;i<arr.Length-1;i++)//循环让第i个元素与i+1元素比较
                {
                    //每一轮循环之后最大的值已经在最后面，下次比较结束的位置就是数组长度-1
                    for (int j=0;j<arr.Length-1-i;j++)
                    {
                        if(arr[j]>arr[j+1])//前面值比后面的大，就进行交换
                        {
                            tmp = arr[j];
                            arr[j] = arr[j + 1];
                            arr[j + 1] = tmp;
                        }
                    }
                }
                Console.WriteLine("排序之后的结果：");
                foreach (int i in arr)
                {
                    Console.Write(i.ToString() + " ");
                }
                Console.WriteLine();
            }
        }
    }

结果输出：

排序之前：
    5 1 7 2 4 9 3
    排序之后的结果：
    1 2 3 4 5 7 9
    请按任意键继续. . .