15.冒泡排序

CSharp > CSharp基础 > CSharp基础语法知识 CSharp 语法知识 CSharp基础 排序算法
发布时间 :
字数:2.6k 阅读 : 评论:
  1. 15.排序-冒泡排序
    1. 15.1 知识点
      1. 排序的基本概念
      2. 冒泡排序的基本原理
      3. 冒泡排序代码实现过程
        1. 第一步：每轮遍历比较数组中两两相邻的数
        2. 第二步：满足条件时交换位置
        3. 第三步：比较的轮数
        4. 第四步：优化
      4. 冒泡排序最终代码
      5. 打印出排序后的数组
      6. 总结
    2. 15.2 知识点代码
    3. 15.3 练习题
      1. 定义一个数组，长度为20，每个元素值随机0~100的数，使用冒泡排序进行升序排序或降序排序并打印
      2. 写一个函数，实现一个数组的排序，并返回结果。可以根据参数决定是升序还是降序
    4. 15.4 练习题代码

15.排序-冒泡排序

15.1 知识点

排序的基本概念

排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。常用的排序例子如下：

无序序列：8, 7, 1, 5, 4, 2, 6, 3, 9

有序序列（升序）：1, 2, 3, 4, 5, 6, 7, 8, 9

有序序列（降序）：9, 8, 7, 6, 5, 4, 3, 2, 1

在程序中，序列一般存储在数组中，因此排序往往是对数组进行排序：

int[] arr = new int[] { 8, 7, 1, 5, 4, 2, 6, 3, 9 };

冒泡排序的基本原理

冒泡排序的基本原理是通过两两比较相邻的元素，不停交换，比较多轮，将最大（或最小）的元素慢慢“冒泡”到正确的位置。

冒泡排序代码实现过程

第一步：每轮遍历比较数组中两两相邻的数

for (int n = 0; n < arr.Length - 1; n++)
{
    // 比较第n个数和第n+1个数
}

第二步：满足条件时交换位置

for (int n = 0; n < arr.Length - 1; n++)
{
    if (arr[n] > arr[n + 1])
    {
        // 如果第n个数比第n+1个数大，交换位置
        int temp = arr[n];
        arr[n] = arr[n + 1];
        arr[n + 1] = temp;
    }
}

第三步：比较的轮数

for (int m = 0; m < arr.Length; m++)
{
    for (int n = 0; n < arr.Length - 1 - m; n++)
    {
        // 在每一轮中，比较相邻的元素
    }
}

第四步：优化

  1. 确定位置的数字不用比较了： 每轮遍历后，本轮的极值（最大或最小）已经放到了对应的位置，所以下一轮不需要再比较。

  2. 特殊情况的优化： 外面声明一个标识 isSort，用于表示该轮是否进行了交换。每一轮开始时默认没有进行过交换，当一轮结束后，如果 isSort 还是 false，说明已经是最终的序列了，不需要再判断交换了。

bool isSort = false;
for (int m = 0; m < arr.Length; m++)
{
    isSort = false;
    for (int n = 0; n < arr.Length - 1 - m; n++)
    {
        if (arr[n] > arr[n + 1])
        {
            isSort = true;
            int temp = arr[n];
            arr[n] = arr[n + 1];
            arr[n + 1] = temp;
        }
    }
    if (!isSort)
    {
        break;
    }
}

冒泡排序最终代码

bool isSort = false;
for (int m = 0; m < arr.Length; m++)
{
    isSort = false;
    for (int n = 0; n < arr.Length - 1 - m; n++)
    {
        if (arr[n] > arr[n + 1])
        {
            isSort = true;
            int temp = arr[n];
            arr[n] = arr[n + 1];
            arr[n + 1] = temp;
        }
    }
    if (!isSort)
    {
        break;
    }
}

打印出排序后的数组

for (int i = 0; i < arr.Length; i++)
{
    Console.Write(arr[i] + " "); // 输出：1 2 3 4 5 6 7 8 9
}

总结

  • 基本概念： 两两相邻，不停比较，不停交换，比较多轮。
  • 套路写法： 两层循环，外层轮数，内层比较，两值比较，满足交换。
  • 优化写法： 比过不比，加入 bool 标识。

15.2 知识点代码

using System;

namespace Lesson13_冒泡排序
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("冒泡排序");

            #region 知识点一 排序的基本概念
            //排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列
            //常用的排序例子
            // 8 7 1 5 4 2 6 3 9
            // 把上面的这个无序序列 变为 有序（升序或降序）序列的过程
            // 1 2 3 4 5 6 7 8 9 （升序）
            // 9 8 7 6 5 4 3 2 1 （降序）

            //在程序中 序列一般 存储在数组当中
            //所以 排序往往是对 数组进行排序
            int[] arr = new int[] { 8, 7, 1, 5, 4, 2, 6, 3, 9, };
            //把数组里面的内容变为有序的
            #endregion

            #region 知识点二 冒泡排序基本原理
            // 8 7 1 5 4 2 6 3 9
            // 两两相邻
            // 不停比较
            // 不停交换
            // 比较n轮

            #endregion

            #region 知识点三 冒泡排序代码实现过程

            //第一步 每轮遍历比较数组中两两相邻的数
            //8, 7, 1, 5, 4, 2, 6, 3, 9
            //从头开始
            //第n个数和第n+1个数 比较

            //for (int n = 0; n < arr.Length - 1; n++)
            //{

            //}

            //第二步 满足条件时交换位置
            //如果 第n个数 比第n+1个数 大 他们就要交换位置
            // 中间商不赚差价 

            //for (int n = 0; n < arr.Length - 1; n++)
            //{
            //    if (arr[n] > arr[n + 1])
            //    {
            //        int temp = arr[n];
            //        arr[n] = arr[n + 1];
            //        arr[n + 1] = temp;
            //    }
            //}


            //第三步 比较的轮数
            //有几个数 就比较多少轮
            //进一次循环 就需要比较一轮

            //for (int m = 0; m < arr.Length; m++)
            //{
            //    for (int n = 0; n < arr.Length - 1; n++)
            //    {
            //        if (arr[n] > arr[n + 1])
            //        {
            //            int temp = arr[n];
            //            arr[n] = arr[n + 1];
            //            arr[n + 1] = temp;
            //        }
            //    }
            //}



            //第四步 优化

            //1.确定位置的数字 不用比较了 
            // 确定了一轮后 本轮的极值（最大或者最小）已经放到了对应的位置（往后放）
            // 每完成m轮 后面位置的数 就不用再参与比较了
            // 所以 每轮遍历的比较的次数从arr.Length - 1改成arr.Length - 1 - m


            //for (int m = 0; m < arr.Length; m++)
            //{
            //    for (int n = 0; n < arr.Length - 1 - m; n++)
            //    {
            //        if (arr[n] > arr[n + 1])
            //        {
            //            int temp = arr[n];
            //            arr[n] = arr[n + 1];
            //            arr[n + 1] = temp;
            //        }
            //    }
            //}

            //2.特使情况的优化
            //外面声明一个标识 来表示 该轮是否进行了交换
            //每一轮开始时 默认没有进行过交换
            //当一轮结束过后 如果isSort这个标识 还是false
            //那就意味着 已经是最终的序列了 不需要再判断交换了

            //bool isSort = false;
            //for (int m = 0; m < arr.Length; m++)
            //{
            //    isSort = false;
            //    for (int n = 0; n < arr.Length - 1 - m; n++)
            //    {
            //        if (arr[n] > arr[n + 1])
            //        {
            //            isSort = true;
            //            int temp = arr[n];
            //            arr[n] = arr[n + 1];
            //            arr[n + 1] = temp;
            //        }
            //    }
            //    if( !isSort )
            //    {
            //        break;
            //    }
            //}

            #endregion

            #region 知识点四 冒泡排序最终代码

            // 冒泡排序代码
            bool isSort = false;
            for (int m = 0; m < arr.Length; m++)
            {
                isSort = false;
                for (int n = 0; n < arr.Length - 1 - m; n++)
                {
                    if (arr[n] > arr[n + 1])
                    {
                        isSort = true;
                        int temp = arr[n];
                        arr[n] = arr[n + 1];
                        arr[n + 1] = temp;
                    }
                }
                if (!isSort)
                {
                    break;
                }
            }

            //打印出排序后的数组
            for (int i = 0; i < arr.Length; i++)
            {
                Console.Write(arr[i] + " ");//1 2 3 4 5 6 7 8 9
            }

            #endregion

            //总结
            //基本概念
            //两两相邻
            //不停比较
            //不停交换
            //比较m轮

            //套路写法
            //两层循环
            //外层轮数
            //内层比较
            //两值比较
            //满足交换

            //优化写法
            //1.比过不比 
            //2.加入bool
        }
    }
}

15.3 练习题

定义一个数组，长度为20，每个元素值随机0~100的数，使用冒泡排序进行升序排序或降序排序并打印

声明随机数组

int[] arr = new int[20];
Random r = new Random();
for (int i = 0; i < arr.Length; i++)
{
    arr[i] = r.Next(0, 101);
    Console.Write(arr[i] + " ");
}
Console.WriteLine();

进行冒泡排序

//套路写法
//两层循环
//外层轮数
bool isSort = false;
for (int i = 0; i < arr.Length; i++)
{
    isSort = false;
    //内层比较
    for (int j = 0; j < arr.Length - 1 - i; j++)
    {
        //两值比较
        //满足交换
        //降序还是升序 改这的比较条件就行了
        //if (arr[j] > arr[j + 1])
        if (arr[j] < arr[j + 1])
        {
            isSort = true;
            int temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
        }
    }
    if (!isSort)
    {
        break;
    }
}

打印排序后的结果

for (int i = 0; i < arr.Length; i++)
{
    Console.Write(arr[i] + " ");
}

写一个函数，实现一个数组的排序，并返回结果。可以根据参数决定是升序还是降序

主函数外 class 语句块内

static int[] Sort(int[] array, bool isAscendingOrder)
{
    //小优化 在循环外声明变量 可以提高一些性能
    bool order;
    int temp;
    for (int i = 0; i < array.Length; i++)
    {
        for (int j = 0; j < array.Length - 1 - i; j++)
        {
            //根据传入的 升序降序类型 决定使用什么规则 然后返回给一个 bool 值
            order = isAscendingOrder ? array[j] > array[j + 1] : array[j] < array[j + 1];
            if (order)
            {
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
    return array;
}

主函数内

int[] arr2 = { 3, 7, 2, 1, 9, 8, 6, 5, 4 };
Console.WriteLine();
Sort(arr2, false);
for (int i = 0; i < arr2.Length; i++)
{
    Console.Write(arr2[i] + " ");
}

15.4 练习题代码

using System;

namespace Lesson13_练习题
{
    class Program
    {
        #region 练习题二
        //主函数外 class语句块内
        static int[] Sort(int[] array, bool isAscendingOrder)
        {
            //小优化 在循环外声明变量 可以提高一些性能
            bool order;
            int temp;
            for (int i = 0; i < array.Length; i++)
            {
                for (int j = 0; j < array.Length - 1 - i; j++)
                {
                    //根据传入的 升序降序类型 决定使用什么规则 然后返回给一个bool值
                    order = isAscendingOrder ? array[j] > array[j + 1] : array[j] < array[j + 1];
                    if (order)
                    {
                        temp = array[j];
                        array[j] = array[j + 1];
                        array[j + 1] = temp;
                    }
                }
            }
            return array;
        }
        #endregion
        static void Main(string[] args)
        {
            Console.WriteLine("冒泡排序练习题");

            #region 练习题一
            //定义一个数组，长度为20，每个元素值随机0~100的数，使用冒泡排序进行升序排序或降序排序并打印

            //声明随机数组
            int[] arr = new int[20];
            Random r = new Random();
            for (int i = 0; i < arr.Length; i++)
            {
                arr[i] = r.Next(0, 101);
                Console.Write(arr[i] + " ");//35 34 68 40 33 1 58 3 95 87 37 17 35 13 22 66 9 25 2 20
            }
            Console.WriteLine();

            //进行冒泡排序
            //套路写法
            //两层循环
            //外层轮数
            bool isSort = false;
            for (int i = 0; i < arr.Length; i++)
            {
                isSort = false;
                //内层比较
                for (int j = 0; j < arr.Length - 1 - i; j++)
                {
                    //两值比较
                    //满足交换
                    // 降序还是升序 改这的比较条件就行了
                    //if (arr[j] > arr[j + 1])
                    if ( arr[j] < arr[j + 1] )
                    {
                        isSort = true;
                        int temp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = temp;
                    }
                }
                if(!isSort)
                {
                    break;
                }
            }

            //打印排序后的结果
            for (int i = 0; i < arr.Length; i++)
            {
                Console.Write(arr[i] + " ");//95 87 68 66 58 40 37 35 35 34 33 25 22 20 17 13 9 3 2 1
            }

            #endregion

            #region 练习题二
            //写一个函数，实现一个数组的排序，并返回结果。可以根据参数决定是升序还是降序

            //主函数内

            int[] arr2 = { 3, 7, 2, 1, 9, 8, 6, 5, 4 };

            Console.WriteLine();

            Sort(arr2, false);

            for (int i = 0; i < arr2.Length; i++)
            {
                Console.Write(arr2[i] + " ");//9 8 7 6 5 4 3 2 1
            }
            #endregion
        }


    }
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com

赏

©2016-2024 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏