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

2019年12月15日 1673点热度 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;
                }
            }
        }