基础排序算法(三)——对半插入排序

发表于

      之前的文章介绍了冒泡排序和插入排序，这里再补充一个对半插入排序算法，它与对半查找算法（二分查找算法）有点相似之处。

      还是先上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void HalfInsertSort(int[] array)
{
    int j = 0, temp, low, high, mid;
    int count = array.Length;
    for (int i = 1; i < count; i++)
    {
        temp = array[i];
        low = 0;
        high = i - 1;
        while (low <= high)
        {
            mid = (low + high) / 2;
            if (temp < array[mid]) high = mid - 1;
            else low = mid + 1;
        }
        for (j = i - 1; j >= low; j--) array[j + 1] = array[j];
        array[low] = 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.HalfInsertSort(array);
            csharArray.PrintArray(array);

            Console.ReadKey();
        }
    }
}

      输出结果：
      排序前:

1       0       2       5       4       1       3       4

      排序后:

0       1       1       2       3       4       4       5

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public void HalfInsertSort(int[] array)
{
    int j = 0, temp, low, high, mid;
    int count = array.Length;
    for (int i = 1; i < count; i++)
    {
        temp = array[i];
        low = 0;
        high = i - 1;
        while (low <= high)
        {
            mid = (low + high) / 2;
            if (temp < array[mid]) high = mid - 1;
            else low = mid + 1;
        }
        for (j = i - 1; j >= low; j--) array[j + 1] = array[j];
        array[low] = temp;
        PrintArray(array);
    }
}

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

1       0       2       5       4       1       3       4

      排序后:

0       1       2       5       4       1       3       4
0       1       2       5       4       1       3       4
0       1       2       5       4       1       3       4
0       1       2       4       5       1       3       4
0       1       1       2       4       5       3       4
0       1       1       2       3       4       5       4
0       1       1       2       3       4       4       5
0       1       1       2       3       4       4       5

      从输出结果可以看出，遍历数组元素，利用对半查找原理找到其位置，插入，将受影响的元素一次前移。

      同样，为了将以上的升序排序算法改为降序，也只需将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
41
public void HalfInsertSort(int[] array, int orderType)
{
   int j = 0, temp,low,high,mid;
   int count = array.Length;
   if (orderType == 0)
   {
      for (int i = 1; i < count; i++)
      {
          temp = array[i];
          low = 0;
          high = i - 1;
          while (low <= high)
          {
              mid = (low + high) / 2;
              if (temp < array[mid]) high = mid - 1;
              else low = mid + 1;
          }
          for (j = i - 1; j >= low; j--) array[j + 1] = array[j];
          array[low] = temp;
          PrintArray(array);
      }
   }
   else if (orderType == 1)
   {
      for (int i = 1; i < count; i++)
      {
          temp = array[i];
          low = 0;
          high = i - 1;
          while (low < high)
          {
              mid = (low + high) / 2;
              if (temp > array[mid]) high = mid - 1;
              else low = mid + 1;
          }
          for (j = i - 1; j >= low; j--) array[j + 1] = array[j];
          array[low] = 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.HalfInsertSort(array, 0);
            csharArray.PrintArray(array);
            Console.WriteLine("降序排序后:");
            csharArray.HalfInsertSort(array, 1);
            csharArray.PrintArray(array);

            Console.ReadKey();
        }
    }
}

      编译运行结果如下所示：
      排序前:

2       4       0       3       5       6       1       1

      升序排序后:

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

      降序排序后:

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

      最后，再次贴一下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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
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);
                }
            }
        }

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

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

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

反馈请点击: