Data Structures and Algorithms DotNet － 3、基础排序算法

Created at 2016-09-15 Updated at 2018-05-01 Category Data Structures and Algorithms Tag Data Structures and Algorithms / DotNet

数据结构与算法－3、基础排序算法

排序，查找，是最常用的两种数据操作，所以也是计算机科学领域最值得研究的两种操作。
下面的许多数据结构的主要设计目的，是使排序和查找更加简单，同时也让数据在结构中的存储更加有效。
简单算法有：

• 插入排序算法
• 冒泡排序算法，最慢的排序算法之一
• 选择排序算法

它们对少量数据的集合非常有效。

1、冒泡排序

最慢的排序算法之一。多次遍历整个列，比较相邻的值，如果是升序排列的话，就将大的值换到右边。这里举的例子，是最差的情况，完全倒序的数组，需要做升序排列。

可以看出来，冒泡排序的关键，是在第一圈，将最大的那个值，一个位置一个位置地移到最右边。第二圈，将第二大的值，一个位置一个位置地移动到倒数第二的位置上。以此类推。
并且，冒泡排序的圈数是固定的，即使运气好第一圈就完成了排序，接下来的几圈依然会继续跑。

1.1、冒泡算法

算法上，主要靠两层循环来完成，过程如下：

1. 5个数，外层循环就是4，内层循环循环比较4次，交换4次。将最大值一个位置一个位置地移到索引4的位置
2. 最大数放倒最右边后，外层循环变为3，内层循环循环比较3次，交换3次，将第二大值一个位置一个位置地移到索引3的位置
3. 外层循环2，内层循环2，交换2次
4. 外层循环1，内存循环1，交换1次，对比最左边两个数，将大的值放到索引1的位置，结束

1.2、冒泡算法性能

这个举的例子是最差的情况：

• 总共比较了4+3+2+1=10次。
• 总共交换了4+3+2+1=10次。

稍微好点的情况，是比较10次，交换小于10次。

1.3、核心算法实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

int[] bobble = new int[5] {9,8,7,6,5 };
int temp;
for (int outer = bobble.GetUpperBound(0); outer >= 1; outer--)
{
	for (int inner = 0; inner <= outer - 1; inner++)
	{
		if (bobble[inner] > bobble[inner + 1])
		{
			temp = bobble[inner];
			bobble[inner] = bobble[inner + 1];
			bobble[inner + 1] = temp;
		}
	}
	Console.WriteLine(string.Join(",", bobble));
}

2、选择排序

选择排序，在第一圈，从左边第一个位置开始，找到那个最小值的索引，将最小值与第一个值进行交换，这样最小值就在最左边了。在第二圈，从左边第二个位置开始，找到那个最小值的索引，与左边第二个位置的值进行交换。
并且，冒泡排序的圈数是固定的，即使运气好第一圈就完成了排序，接下来的几圈依然会继续跑。

2.1、选择排序算法

算法上，主要靠两层循环来完成，过程如下：

1. 5个数，外层循环是0，内层循环循环比较4次，移动1次。从第0个索引开始找，找到那个最小值的索引，将最小值与索引0的值进行交换。
2. 外层循环是1，内层循环循环比较3次，移动1次。从第1个索引开始找，找到那个最小值的索引，将最小值与索引1的值进行交换。
3. 外层循环是2，内层循环循环比较2次，移动1次。从第2个索引开始找，找到那个最小值的索引，将最小值与索引2的值进行交换。
4. 外层循环是3，内层循环循环比较1次，移动1次。从第3个索引开始找，找到那个最小值的索引，将最小值与索引3的值进行交换。

2.2、选择排序算法性能

• 总共比较了4+3+2+1=10次。
• 总共交换了1+1+1+1=4次。

2.3、核心算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

static void Selection(int[] arr)
{
	int min, temp;
	int upper = arr.GetUpperBound(0);
	for (int outer = 0; outer <= upper; outer++)
	{
		min = outer;
		for (int inner = outer + 1; inner <= upper; inner++)
		{
			if (arr[inner] < arr[min])
			{
				min = inner;
			}
		}


		temp = arr[outer];
		arr[outer] = arr[min];
		arr[min] = temp;
		Console.WriteLine(string.Join(",", arr));

	}
}

3、插入排序

插入排序是这三个简单排序算法当中，性能最好的。

插入排序，在第一圈，把左边第二个位置的值取出来，与左边第一个位置的值比较，如果左边第一个第二个大的话，交换位置。在第二圈，把左边第三个位置的值取出来，依次与左边的值比较，一个位置一个位置地移动到合适的位置。

3.1、插入算法

算法上，需要两层循环来完成，过程如下：

1. 外层循环是1，内层循环比较1次，移动1次。将索引1的值取出来，与左边的值做比较。将索引0的值向右移，将索引1的值放在索引0的位置。
2. 外层循环是2，内层循环比较2次，移动2次。将索引2的值取出来，与左边的值依次做比较。将索引0到索引1的值向右移，将索引2的值放在索引0的位置。
3. 外层循环是3，内层循环比较3次，移动3次。将索引3的值取出来，与左边的值依次做比较。将索引0到索引2的值向右移，将索引3的值放在索引0的位置。
4. 外层循环是4，内层循环比较4次，移动4次。将索引4的值取出来，与左边的值依次做比较。将索引0到索引3的值向右移，将索引4的值放在索引0的位置。

   3.2、选择排序算法性能

• 总共比较了4+3+2+1=10次。
• 总共交换了4+3+2+1=10次。

  3.3、核心算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

static void Insert(int[] arr)
{
	int inner, temp;
	int upper = arr.GetUpperBound(0);

	for (int outer = 1; outer <= upper; outer++)
	{
		temp = arr[outer];
		inner = outer;
		while (inner > 0 && arr[inner - 1] >= temp)
		{
			arr[inner] = arr[inner - 1];
			inner -= 1;
		}
		arr[inner] = temp;
		Console.WriteLine(string.Join(",", arr));
	}
}

4、性能测试

4.1、随机数组测试

5w随机数组测试耗时：

1
2
3

冒泡	15.76s
选择	6.3s
插入	4.3s

10w随机数组测试耗时：

1
2
3

冒泡	59.43s
选择	24.42s
插入	16.39s

随机数组测试排名：

1. 插入
2. 选择
3. 冒泡

4.2、升序数组测试

5w升序数组测试耗时：

1
2
3

冒泡	7.86s
选择	7.87s
插入	0.1169s

10w升序数组测试耗时：

1
2
3

冒泡	29.28s
选择	30.57s
插入	0.1264s

升序数组测试排名：

1. 插入
2. 冒泡，选择

4.3、降序数组测试

5w降序数组测试耗时：

1
2
3

冒泡	13.61s
选择	9.60s
插入	7.73s

10w降序数组测试耗时：

1
2
3

冒泡	53.44s
选择	37.13s
插入	30.38s

随机数组测试排名：

1. 插入
2. 选择
3. 冒泡

可以看出，插入排序算法性能最好。但是，这三个简单排序算法，没有一个适合处理庞大数据集的，效率都太低。