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

内容纲要

 冒泡排序法

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

以从小到大排序为例。

数据 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]。

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

第二次插入:[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# 冒泡排序法、插入排序法、选择排序法》

点赞
  1. 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. 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!