C#算法之冒泡排序、插入排序、選擇排序

Posted on by

冒泡排序法

是數組等線性排列的數字從大到小或從小到大排序。

以從小到大排序為例。

數據 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;
                }
            }
        }

動圖如下

 到此這篇關於C#算法之冒泡排序、插入排序、選擇排序的文章就介紹到這瞭。希望對大傢的學習有所幫助，也希望大傢多多支持WalkonNet。

推薦閱讀：