基础排序算法(二)——插入排序

发表于

      之前写了一个冒泡排序算法，这里再加一个插入排序算法，链接里讲得也比较详细，不过为了熟练，还是自己亲自敲一遍，再次贴出来，分享一下

      还是先上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void InsertSort(int[] array)
{
    int j = 0,temp;
    int count = array.Length;
    for (int i = 1; i < count; i++)
    {
        temp = array[i];
        j = i;
        while (j > 0 && array[j - 1] >= temp)
        {
            array[j] = array[j - 1];
            j -= 1;
        }
        array[j] = temp;
    }
}

      同样在Program的Main函数里New一个（一）中写的那个CSharpArray类，调用其中的方法测试：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace BasicStructure
{
    class Program
    {
        static void Main(string[] args)
        {
            CSharpArray csharArray = new CSharpArray(8);
            int[] array = csharArray.getArray();
            Console.WriteLine("排序前:");
            Console.WriteLine();
            csharArray.PrintArray(array);
            Console.WriteLine();
            Console.WriteLine("排序后:");
            csharArray.InsertSort(array);
            csharArray.PrintArray(array);

            Console.ReadKey();
        }
    }
}

      输出结果：
      排序前:

0       4       0       1       1       4       5       7

      排序后:

0       0       1       1       4       4       5       7

      为了显示for循环中的每次执行结果，在InsertSort方法里加一句输出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void InsertSort(int[] array)
{  
    int j = 0,temp;  
    int count = array.Length;  
    for (int i = 1; i < count; i++)  
    {  
        temp = array[i];  
        j = i;  
        while (j > 0 && array[j - 1] >= temp)  
        {  
            array[j] = array[j - 1];  
            j -= 1;  
        }  
        array[j] = temp;  
        PrintArray(array);  
    }  
}

      再次编译运行即得以下结果：
      排序前:

4       6       0       5       0       3       1       3

      排序后:

4       6       0       5       0       3       1       3
0       4       6       5       0       3       1       3
0       4       5       6       0       3       1       3
0       0       4       5       6       3       1       3
0       0       3       4       5       6       1       3
0       0       1       3       4       5       6       3
0       0       1       3       3       4       5       6
0       0       1       3       3       4       5       6

      由此可见，插入排序算法的基本思想是从左到右找出最小的一个往左移插入到合适的位置，遍历完整个数组之后，真个数组就变为有序啦！

      同样，为了将以上的升序排序算法改为降序，也只需将while括号里的大于号改为小于号即可。

      这里，既然将其封装在一个类里，自然要提高其通用性，因此，我可以再给改排序算法添加一个参数，用来标记是升序排序还是降序排序。如：用“0”表示升序，用“1”表示降序，在不降低代码运行效率时以牺牲代码简洁性来修改一下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/// <summary>
/// 插入排序算法
 /// </summary>
/// <param name="array">待排序的数组</param>
/// <param name="orderType">排序类型 0：升序；1：降序</param>
public void InsertSort(int[] array,int orderType)
{
    int j = 0,temp;
    int count = array.Length;
    if (orderType == 0)
    {
        for (int i = 1; i < count; i++)
        {
            temp = array[i];
            j = i;
            while (j > 0 && array[j - 1] >= temp)
            {
                array[j] = array[j - 1];
                j -= 1;
            }
            array[j] = temp;
            PrintArray(array);
        }
    }
    else if (orderType == 1)
    {
        for (int i = 1; i < count; i++)
        {
            temp = array[i];
            j = i;
            while (j > 0 && array[j - 1] <= temp)
            {
                array[j] = array[j - 1];
                j -= 1;
            }
            array[j] = temp;
            PrintArray(array);
        }
    }
}

      再修改Main函数里代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace BasicStructure
{
    class Program
    {
        static void Main(string[] args)
        {
            CSharpArray csharArray = new CSharpArray(8);
            int[] array = csharArray.getArray();
            Console.WriteLine("排序前:");
            Console.WriteLine();
            csharArray.PrintArray(array);
            Console.WriteLine();
            Console.WriteLine("升序排序后:");
            csharArray.InsertSort(array,0);
            csharArray.PrintArray(array);
            Console.WriteLine("降序排序后:");
            csharArray.InsertSort(array, 1);
            csharArray.PrintArray(array);

            Console.ReadKey();
        }
    }
}

      编译运行结果如下所示：

      排序前:

5       7       1       2       7       2       2       4

      升序排序后:

5       7       1       2       7       2       2       4
1       5       7       2       7       2       2       4
1       2       5       7       7       2       2       4
1       2       5       7       7       2       2       4
1       2       2       5       7       7       2       4
1       2       2       2       5       7       7       4
1       2       2       2       4       5       7       7
1       2       2       2       4       5       7       7

      降序排序后:

2       1       2       2       4       5       7       7
2       2       1       2       4       5       7       7
2       2       2       1       4       5       7       7
4       2       2       2       1       5       7       7
5       4       2       2       2       1       7       7
7       5       4       2       2       2       1       7
7       7       5       4       2       2       2       1
7       7       5       4       2       2       2       1

      最后，再次贴一下CSharpArray类的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace BasicStructure
{
    class CSharpArray
    {
        private int[] array;
        public CSharpArray(int count)
        {
            array = new int[count];
            Random random = new Random();
            for (int i = 0; i < count; i++)
            {
                array[i] = random.Next(count);
            }
        }
        public int[] getArray()
        {
            return array;
        }
        public void PrintArray(int []array)
        {
            int count=array.Length;
            for (int i = 0; i < count; i++)
            {
                Console.Write("\t{0}", array[i]);
                if ((i + 1) % 8 == 0)
                    Console.WriteLine();
            }
        }
        /// <summary>
        /// 冒泡排序算法
        /// </summary>
        /// <param name="array">待排序的数组</param>
        /// <param name="orderType">排序类型 0：升序；1：降序</param>
        public void BubbleSort(int []array,int orderType)
        {
            int temp;
            int count = array.Length;
            if(orderType==0)
            {
                for (int i = count; i >= 1; i--)
                {
                    for (int j = 0; j < i - 1; j++)
                    {
                        if (array[j] > array[j + 1])
                        {
                            temp = array[j];
                            array[j] = array[j + 1];
                            array[j + 1] = temp;
                        }
                    }
                    PrintArray(array);
                }
            }else if(orderType==1)
            {
                for (int i = count; i >= 1; i--)
                {
                    for (int j = 0; j < i - 1; j++)
                    {
                        if (array[j] < array[j + 1])
                        {
                            temp = array[j];
                            array[j] = array[j + 1];
                            array[j + 1] = temp;
                        }
                    }
                    PrintArray(array);
                }
            }
        }

        /// <summary>
        /// 插入排序算法
        /// </summary>
        /// <param name="array">待排序的数组</param>
        /// <param name="orderType">排序类型 0：升序；1：降序</param>
        public void InsertSort(int[] array,int orderType)
        {
            int j = 0,temp;
            int count = array.Length;
            if (orderType == 0)
            {
                for (int i = 1; i < count; i++)
                {
                    temp = array[i];
                    j = i;
                    while (j > 0 && array[j - 1] >= temp)
                    {
                        array[j] = array[j - 1];
                        j -= 1;
                    }
                    array[j] = temp;
                    PrintArray(array);
                }
            }
            else if (orderType == 1)
            {
                for (int i = 1; i < count; i++)
                {
                    temp = array[i];
                    j = i;
                    while (j > 0 && array[j - 1] <= temp)
                    {
                        array[j] = array[j - 1];
                        j -= 1;
                    }
                    array[j] = temp;
                    PrintArray(array);
                }
            }
        }
    }
}

      OK，插入排序算法的基本演示就到此结束！

      注：由于数组时代码里生成的随机数组，因此每次运行的结果基本不一样，可能与以上演示结果不同。

反馈请点击: