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

2019年12月15日 2条评论 574次阅读 0人点赞
内容纲要

 冒泡排序法

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

以从小到大排序为例。

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

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

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

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

思路循环都把最大的数放在最后一位，无序数字个数减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;
                    }
                }
            }

排序结果

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

 

 动图如下

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

插入排序法

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

例如 把 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();
        }
    }
}

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

动图演示

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

 

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

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

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

选择排序法

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

数组 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;
                }
            }
        }

动图如下

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

点赞
知识共享许可协议
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
  1. tadalafil without a prescription说道：
    2021年1月7日 下午10:15

    I'm commenting to let you be aware of of the amazing discovery my child developed browsing the blog. She came to find a good number of details, including how it is like to have a great coaching character to get a number of people clearly completely grasp a number of advanced issues. You actually did more than her desires. I appreciate you for churning out such beneficial, dependable, edifying and cool guidance on that topic to Emily.

    回复
  2. hyundai key fob replacement说道：
    2021年1月5日 上午4:50

    I like this blog very much, Its a rattling nice post to read and incur information. I really love your website!

    回复

发表评论

邮箱地址不会被公开。 必填项已用*标注

You must enable javascript to see captcha here!