基础数据结构(一)——冒泡排序

发表于

      最近为了准备找工作，数据结构这块必须得恶补。
      首先，一个很基础的东东就是基础排序算法和查找算法了。

      这里，先说说排序吧。
      为了做好准备工作，在此先弄一个数组生成器吧，把它封装为一个类，同时也为了后续其他的测试提供方便，免得拷贝过来拷贝过去。

      一个简单的数组类：

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
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace BasicStructure
{
    class CSharpArray
    {
        private int[] array;
        public void 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();
            }
        }
    }
}

      第一个要说的排序算法当属冒泡排序算法了，链接里有比较详细的介绍，在此就不罗嗦了。
      冒泡排序的基本实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void BubbleSort(int []array)
{
  int temp;
  int count = array.Length;
  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;
          }
      }
  }
}

      测试如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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(100);
            int[] array = csharArray.getArray();
            Console.WriteLine("排序前:");
            Console.WriteLine();
            csharArray.PrintArray(array);
            Console.WriteLine();
            Console.WriteLine("排序后:");
            csharArray.BubbleSort(array);
            csharArray.PrintArray(array);
            Console.ReadKey();
        }
    }
}

      为了展示一下它的实现原理，这里需要稍微修改一下冒泡排序方法，同时得减少一点数据，以便于对比观察。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void BubbleSort(int []array)
{
  int temp;
  int count = array.Length;
  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);
  }
}

      以下为输出结果：
      排序前:

1       7       7       0       5       2       1       3

      排序后:

1       7       0       5       2       1       3       7
1       0       5       2       1       3       7       7
0       1       2       1       3       5       7       7
0       1       1       2       3       5       7       7
0       1       1       2       3       5       7       7
0       1       1       2       3       5       7       7
0       1       1       2       3       5       7       7
0       1       1       2       3       5       7       7
0       1       1       2       3       5       7       7

      右上可以看到，每一轮排序，每行都会有个数字由前向后想冒泡一样移动，因此这种排序正是得名于像“气泡一样”从序列的一段浮动到另一端。

      以上为升序排序，若采用降序排序，则只需稍微改动一点点，即将BubbleSort方法中的“>”号改为“<”即可。

      好了，本篇到此结束！

反馈请点击: