面向云技术架构 - 痴者工良

  • 首页
  • 资源导航
    • 值得收藏的网站导航
    • 本站文章导航
    • 资源下载
  • 教程文档
    • kubernetes 教程
    • 多线程和异步
    • 动态编程-反射、特性、AOP
    • 表达式树
  • 隐私政策
无虑
青山一片云雾,心安即归处,山泉水洗去来时的尘土。
听风吹过松竹,自在即归处,借一壶清茶伴日出。
  1. 首页
  2. .NET
  3. 正文

C# 冒泡排序法、插入排序法、选择排序法

2019年12月15日 1263点热度 0人点赞 2条评论
内容纲要

 冒泡排序法

是数组等线性排列的数字从大到小或从小到大排序。

以从小到大排序为例。

数据 11, 35, 39, 30, 7, 36, 22, 13, 1, 38, 26, 18, 12, 5, 45, 32, 6, 21, 42, 23

使用 数组 int [] array 存储数字。

过程 (数组从小到大排序) 

思路循环都把最大的数放在最后一位,无序数字个数减1。

i 为当前任务位置,n 剩下的无序数字个数

从第 0位开始,比较前后两位数字大大小,当 array[i] > array[i+1] 时,数值互换。

一个循环后,数值最大的已经存到数组最后一位。

无序数字个数 n-1

    for (int j = array.Length - 1; j > 0; j--)  //每排一次,剩下的无序数减一
            {
                for (int i = 0; i < j; i++)    //一个for循环获得一个最大的数
                {
                    if (array[i] > array[i + 1])  //数值互换
                    {
                        var sap = array[i];
                        array[i] = array[i + 1];
                        array[i + 1] = sap;
                    }
                }
            }

排序结果

 

 动图如下

 


插入排序法

插入排序算法是把一个数插入一个已经排序好的数组中。

例如 把 22 插入到 [1,5,10,17,28,39,42] 中,

结果  [1,5,10,17,22,28,39,42] 。

 

对数组使用插入排序法

数组 int [] array = [11, 39, 35, 30, 7, 36, 22, 13, 1, 38, 26, 18, 12, 5, 45, 32, 6, 21, 42, 23];

数组元素是无序,设定一个从大到小或从小到大的方向,第一位就是有序的 [ 11 ] ,

第一次插入: [11, 39, 35, 30, 7, 36, 22, 13, 1, 38, 26, 18, 12, 5, 45, 32, 6, 21, 42, 23]。

取第二个数跟第一个进行比较, 两位有序 [11, 39]

第二次插入:[11, 39, 35, 30, 7, 36, 22, 13, 1, 38, 26, 18, 12, 5, 45, 32, 6, 21, 42, 23]

取第三个数,[11, 39, 35],进行插入

[11, 35, 39 ,30, 7, 36, 22, 13, 1, 38, 26, 18, 12, 5, 45, 32, 6, 21, 42, 23]

... ...

以后每次取一个数,插入数组。

 

实现方法有很多种,笔者的方法跟冒泡排序法相似。

 public static void ReSort(ref int[] array)
        {
            for (int i = 0; i < array.Length; i++)    //要将第几位数进行插入
            {
                for (int j = i; j > 0; j--)
                {
                    if (array[j] > array[j - 1]) break;  //如果要排序的数大于已排序元素的最大值,就不用比较了。不然就要不断比较找到合适的位置
                    else
                    {
                        int sap = array[j];
                        array[j] = array[j - 1];
                        array[j - 1] = sap;
                    }
                }
            }
        }

试试把下面的代码复制到控制台,可以看到每次排序的结果。

using System;

namespace ConsoleApp1
{

    class Program
    {
        public static void ReSort(ref int[] array)
        {
            for (int i = 0; i < array.Length; i++)
            {
                Console.WriteLine("\n- - - - - - -");
                Console.WriteLine("\n未排序前:");
                for (int sun = 0; sun <= i && sun < array.Length; sun++)
                {
                    Console.Write($"{array[sun]} , ");
                }

                for (int j = i; j > 0; j--)
                {
                    if (array[j] > array[j - 1]) break;
                    else
                    {
                        int sap = array[j];
                        array[j] = array[j - 1];
                        array[j - 1] = sap;
                    }
                }
                Console.WriteLine("\n排序后: ");
                for (int sun = 0; sun <= i && sun < array.Length; sun++)
                {
                    Console.Write($"{array[sun]} , ");
                }
            }
        }
        static void Main(string[] args)
        {
            int[] array = new int[] { 11, 35, 39, 30, 7, 36, 22, 13, 1, 38, 26, 18, 12, 5, 45, 32, 6, 21, 42, 23 };
            Console.Write("原数组:[");
            foreach (var i in array)
            {
                Console.Write($"{i} , ");
            }
            Console.Write("]\n");

            ReSort(ref array);
            Console.Write("\n- - - - -\n最后结果:[");
            foreach (var i in array)
            {
                Console.Write($"{i} , ");
            }
            Console.Write("]\n");
            Console.ReadKey();
        }
    }
}

动图演示

 

冒泡排序法与插入排序法比较

冒泡排序是从一端开始,比较大小后存到另一端。每次都是从前开始,把最大或最小的结果放到最后。

插入排序始终是从前面开始,把下一个元素存到前面,不用比较最大最小的结果。

选择排序法

每次从后面找到最小或最大的数,进行位移排序。

数组 int [] array = [11, 39, 35, 30, 7, 36, 22, 13, 1, 38, 26, 18, 12, 5, 45, 32, 6, 21, 42, 23];

第一位 i=0

最小值下标  minIndex = 0,最小值 min=11

从后面查找比 11 小的数,找到第 下标位 8,值为1,

进行交换,交换后 [1, 39, 35, 30, 7, 36, 22, 13, 11, 38, 26, 18, 12, 5, 45, 32, 6, 21, 42, 23];

第二位 i=1,

最小值下标  minIndex = 1,最小值 min=39,

从后面查找比 39 小且最小的数,找到 下标为 13,值为 5,

进行交换,交换后 [1, 5, 35, 30, 7, 36, 22, 13, 11, 38, 26, 18, 12, 39, 45, 32, 6, 21, 42, 23];

        public static void ReSort(ref int[] array)
        {
            for (int i = 0; i < array.Length; i++)
            {
                int min = array[i];     //设定第i位为最小值
                int minIndex = i;       //最小值下标
                for (int j = i; j < array.Length; j++)  //从第i为开始找出最小的数
                {
                    if (array[j] < array[minIndex])     //重新存储最小值和下标
                    {
                        min = array[j];
                        minIndex = j;
                    }
                }

                if (array[i] != array[minIndex])        //如果到比第i为更小的数,则发生交换。找不到则不改变
                {
                    array[minIndex] = array[i];
                    array[i] = min;
                }
            }
        }

动图如下

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可
标签: c 冒泡排序 排序 插入排序 选择
最后更新:2021年2月21日

痴者工良

高级程序员劝退师

点赞
< 上一篇
下一篇 >

文章评论

取消回复
You must enable javascript to see captcha here!
目录导航

COPYRIGHT © 2022 whuanle.cn. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

粤ICP备18051778号

粤公网安备 44030902003257号