C# Bubble Sort, Insertion Sort, Selection Sort

2019年12月15日 50点热度 0人点赞 2条评论

内容目录

Bubble Sort

It is a method for sorting numbers in a linear array from largest to smallest or from smallest to largest.

Taking sorting from smallest to largest as an example.

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

Use an array int [] array to store the numbers.

Process (Sorting the array from smallest to largest)

The idea is to repeatedly place the largest number at the last position, reducing the count of unordered numbers by 1.

i is the current task position, n is the remaining count of unordered numbers.

Starting from position 0, compare the two adjacent numbers. When array[i] > array[i+1], swap the values.

After one loop, the largest value is already stored at the last position of the array.

Decrement the count of unordered numbers: n-1.

　　　　for (int j = array.Length - 1; j > 0; j--)  // After each pass, decrement the count of unordered numbers
            {
                for (int i = 0; i < j; i++)　　　　// One for loop to find the maximum number
                {
                    if (array[i] > array[i + 1])　　// Swap values
                    {
                        var sap = array[i];
                        array[i] = array[i + 1];
                        array[i + 1] = sap;
                    }
                }
            }

Sorting result

The animated illustration is as follows

Insertion Sort

The insertion sort algorithm inserts a number into an already sorted array.

For example, inserting 22 into [1,5,10,17,28,39,42] results in [1,5,10,17,22,28,39,42].

Using Insertion Sort on an array

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

The elements in the array are unordered. Set a direction for sorting from largest to smallest or from smallest to largest; the first element is ordered: [ 11 ],

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

Take the second number to compare with the first. Two elements are ordered [11, 39]

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

Take the third number, [11, 39, 35], perform insertion

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

... ...

In the future, take one number each time to insert into the array.

There are many ways to implement this; the author's method is similar to bubble sort.

 public static void ReSort(ref int[] array)
        {
            for (int i = 0; i < array.Length; i++)　　　　// Which position to insert the number
            {
                for (int j = i; j > 0; j--)
                {
                    if (array[j] > array[j - 1]) break;　　// If the number to be sorted is greater than the largest value of the sorted elements, no comparison is needed; otherwise, continue comparing to find the suitable position
                    else
                    {
                        int sap = array[j];
                        array[j] = array[j - 1];
                        array[j - 1] = sap;
                    }
                }
            }
        }

Try copying the code below into the console to see the result of each sorting step.

using System;
namespace ConsoleApp1
{
</span><span style="color: #0000ff;">class</span><span style="color: #000000;"> Program
{
    </span><span style="color: #0000ff;">public</span> <span style="color: #0000ff;">static</span> <span style="color: #0000ff;">void</span> ReSort(<span style="color: #0000ff;">ref</span> <span style="color: #0000ff;">int</span><span style="color: #000000;">[] array)
    {
        </span><span style="color: #0000ff;">for</span> (<span style="color: #0000ff;">int</span> i = <span style="color: #800080;">0</span>; i &lt; array.Length; i++<span style="color: #000000;">)
        {
            Console.WriteLine(</span><span style="color: #800000;">"</span><span style="color: #800000;">\n- - - - - - -</span><span style="color: #800000;">"</span><span style="color: #000000;">);
            Console.WriteLine(</span><span style="color: #800000;">"</span><span style="color: #800000;">\nBefore sorting：</span><span style="color: #800000;">"</span><span style="color: #000000;">);
            </span><span style="color: #0000ff;">for</span> (<span style="color: #0000ff;">int</span> sun = <span style="color: #800080;">0</span>; sun &lt;= i &amp;&amp; sun &lt; array.Length; sun++<span style="color: #000000;">)
            {
                Console.Write($</span><span style="color: #800000;">"</span><span style="color: #800000;">{array[sun]} , </span><span style="color: #800000;">"</span><span style="color: #000000;">);
            }

            </span><span style="color: #0000ff;">for</span> (<span style="color: #0000ff;">int</span> j = i; j &gt; <span style="color: #800080;">0</span>; j--<span style="color: #000000;">)
            {
                </span><span style="color: #0000ff;">if</span> (array[j] &gt; array[j - <span style="color: #800080;">1</span>]) <span style="color: #0000ff;">break</span><span style="color: #000000;">;
                </span><span style="color: #0000ff;">else</span><span style="color: #000000;">
                {
                    </span><span style="color: #0000ff;">int</span> sap =<span style="color: #000000;"> array[j];
                    array[j] </span>= array[j - <span style="color: #800080;">1</span><span style="color: #000000;">];
                    array[j </span>- <span style="color: #800080;">1</span>] =<span style="color: #000000;"> sap;
                }
            }
            Console.WriteLine(</span><span style="color: #800000;">"</span><span style="color: #800000;">\nAfter sorting： </span><span style="color: #800000;">"</span><span style="color: #000000;">);
            </span><span style="color: #0000ff;">for</span> (<span style="color: #0000ff;">int</span> sun = <span style="color: #800080;">0</span>; sun &lt;= i &amp;&amp; sun &lt; array.Length; sun++<span style="color: #000000;">)
            {
                Console.Write($</span><span style="color: #800000;">"</span><span style="color: #800000;">{array[sun]} , </span><span style="color: #800000;">"</span><span style="color: #000000;">);
            }
        }
    }
    </span><span style="color: #0000ff;">static</span> <span style="color: #0000ff;">void</span> Main(<span style="color: #0000ff;">string</span><span style="color: #000000;">[] args)
    {
        </span><span style="color: #0000ff;">int</span>[] array = <span style="color: #0000ff;">new</span> <span style="color: #0000ff;">int</span>[] { <span style="color: #800080;">11</span>, <span style="color: #800080;">35</span>, <span style="color: #800080;">39</span>, <span style="color: #800080;">30</span>, <span style="color: #800080;">7</span>, <span style="color: #800080;">36</span>, <span style="color: #800080;">22</span>, <span style="color: #800080;">13</span>, <span style="color: #800080;">1</span>, <span style="color: #800080;">38</span>, <span style="color: #800080;">26</span>, <span style="color: #800080;">18</span>, <span style="color: #800080;">12</span>, <span style="color: #800080;">5</span>, <span style="color: #800080;">45</span>, <span style="color: #800080;">32</span>, <span style="color: #800080;">6</span>, <span style="color: #800080;">21</span>, <span style="color: #800080;">42</span>, <span style="color: #800080;">23</span><span style="color: #000000;"> };
        Console.Write(</span><span style="color: #800000;">"</span><span style="color: #800000;">Original array：[</span><span style="color: #800000;">"</span><span style="color: #000000;">);
        </span><span style="color: #0000ff;">foreach</span> (<span style="color: #0000ff;">var</span> i <span style="color: #0000ff;">in</span><span style="color: #000000;"> array)
        {
            Console.Write($</span><span style="color: #800000;">"</span><span style="color: #800000;">{i} , </span><span style="color: #800000;">"</span><span style="color: #000000;">);
        }
        Console.Write(</span><span style="color: #800000;">"</span><span style="color: #800000;">]\n</span><span style="color: #800000;">"</span><span style="color: #000000;">);

        ReSort(</span><span style="color: #0000ff;">ref</span><span style="color: #000000;"> array);
        Console.Write(</span><span style="color: #800000;">"</span><span style="color: #800000;">\n- - - - -\nFinal result：[</span><span style="color: #800000;">"</span><span style="color: #000000;">);
        </span><span style="color: #0000ff;">foreach</span> (<span style="color: #0000ff;">var</span> i <span style="color: #0000ff;">in</span><span style="color: #000000;"> array)
        {
            Console.Write($</span><span style="color: #800000;">"</span><span style="color: #800000;">{i} , </span><span style="color: #800000;">"</span><span style="color: #000000;">);
        }
        Console.Write(</span><span style="color: #800000;">"</span><span style="color: #800000;">]\n</span><span style="color: #800000;">"</span><span style="color: #000000;">);
        Console.ReadKey();
    }
}

}

Animation demonstration

Comparison of Bubble Sort and Insertion Sort

Bubble sort begins from one end, comparing sizes and storing the result at the other end. Each time, it starts from the front, placing the largest or smallest result at the end.

Insertion sort always starts from the front, placing the next element without comparing the largest or smallest results.

Selection Sort

Each time, it finds the smallest or largest number from the back and performs displacement sorting.

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

First position i=0

Minimum index minIndex = 0, minimum value min=11

Look for numbers smaller than 11 from the back, find index 8, value is 1,

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

Second position i=1,

Minimum index minIndex = 1, minimum value min=39,

Look for the smallest number less than 39 from the back, find index 13, value is 5,

Swap, after swapping [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];     //Set the i-th position as the minimum value
                int minIndex = i;       //Minimum index
                for (int j = i; j < array.Length; j++)  //Find the smallest number starting from the i-th position
                {
                    if (array[j] < array[minIndex])     //Store the minimum value and index again
                    {
                        min = array[j];
                        minIndex = j;
                    }
                }
            </span><span style="color: #0000ff;">if</span> (array[i] != array[minIndex])        <span style="color: #008000;">//</span><span style="color: #008000;">If a number smaller than the i-th is found, swap. If not found, do not change</span>

                {

array[minIndex] = array[i];

array[i] = min;

}

}

}