Data Structures and Algorithms DotNet - 3、基础排序算法
Created at 2016-09-15 Updated at 2018-05-01 Category Data Structures and Algorithms
数据结构与算法-3、基础排序算法
排序,查找,是最常用的两种数据操作,所以也是计算机科学领域最值得研究的两种操作。
下面的许多数据结构的主要设计目的,是使排序和查找更加简单,同时也让数据在结构中的存储更加有效。
简单算法有:
- 插入排序算法
- 冒泡排序算法,最慢的排序算法之一
- 选择排序算法
它们对少量数据的集合非常有效。
1、冒泡排序
最慢的排序算法之一。多次遍历整个列,比较相邻的值,如果是升序排列的话,就将大的值换到右边。这里举的例子,是最差的情况,完全倒序的数组,需要做升序排列。
圈数 | 9 | 8 | 7 | 6 | 5 |
---|---|---|---|---|---|
1 | 8 | 7 | 6 | 5 | 9 |
2 | 7 | 6 | 5 | 8 | 9 |
3 | 6 | 5 | 7 | 8 | 9 |
4 | 5 | 6 | 7 | 8 | 9 |
可以看出来,冒泡排序的关键,是在第一圈,将最大的那个值,一个位置一个位置地移到最右边。第二圈,将第二大的值,一个位置一个位置地移动到倒数第二的位置上。以此类推。
并且,冒泡排序的圈数是固定的,即使运气好第一圈就完成了排序,接下来的几圈依然会继续跑。
1.1、冒泡算法
算法上,主要靠两层循环来完成,过程如下:
- 5个数,外层循环就是4,内层循环循环比较4次,交换4次。将最大值一个位置一个位置地移到索引4的位置
- 最大数放倒最右边后,外层循环变为3,内层循环循环比较3次,交换3次,将第二大值一个位置一个位置地移到索引3的位置
- 外层循环2,内层循环2,交换2次
- 外层循环1,内存循环1,交换1次,对比最左边两个数,将大的值放到索引1的位置,结束
1.2、冒泡算法性能
这个举的例子是最差的情况:
- 总共比较了4+3+2+1=10次。
- 总共交换了4+3+2+1=10次。
稍微好点的情况,是比较10次,交换小于10次。
1.3、核心算法实现:
1 | int[] bobble = new int[5] {9,8,7,6,5 }; |
2、选择排序
圈数 | 9 | 8 | 7 | 6 | 5 |
---|---|---|---|---|---|
1 | 5 | 8 | 7 | 6 | 9 |
2 | 5 | 6 | 7 | 8 | 9 |
3 | 5 | 6 | 7 | 8 | 9 |
4 | 5 | 6 | 7 | 8 | 9 |
选择排序,在第一圈,从左边第一个位置开始,找到那个最小值的索引,将最小值与第一个值进行交换,这样最小值就在最左边了。在第二圈,从左边第二个位置开始,找到那个最小值的索引,与左边第二个位置的值进行交换。
并且,冒泡排序的圈数是固定的,即使运气好第一圈就完成了排序,接下来的几圈依然会继续跑。
2.1、选择排序算法
算法上,主要靠两层循环来完成,过程如下:
- 5个数,外层循环是0,内层循环循环比较4次,移动1次。从第0个索引开始找,找到那个最小值的索引,将最小值与索引0的值进行交换。
- 外层循环是1,内层循环循环比较3次,移动1次。从第1个索引开始找,找到那个最小值的索引,将最小值与索引1的值进行交换。
- 外层循环是2,内层循环循环比较2次,移动1次。从第2个索引开始找,找到那个最小值的索引,将最小值与索引2的值进行交换。
- 外层循环是3,内层循环循环比较1次,移动1次。从第3个索引开始找,找到那个最小值的索引,将最小值与索引3的值进行交换。
2.2、选择排序算法性能
- 总共比较了4+3+2+1=10次。
- 总共交换了1+1+1+1=4次。
2.3、核心算法实现
1 | static void Selection(int[] arr) |
3、插入排序
插入排序是这三个简单排序算法当中,性能最好的。
圈数 | 9 | 8 | 7 | 6 | 5 |
---|---|---|---|---|---|
1 | 8 | 9 | 7 | 6 | 5 |
2 | 8 | 7 | 9 | 6 | 5 |
3 | 7 | 8 | 9 | 6 | 5 |
4 | 7 | 8 | 6 | 9 | 5 |
5 | 7 | 6 | 8 | 9 | 5 |
6 | 6 | 7 | 8 | 9 | 5 |
7 | 6 | 7 | 8 | 5 | 9 |
8 | 6 | 7 | 5 | 8 | 9 |
9 | 6 | 5 | 7 | 8 | 9 |
10 | 5 | 6 | 7 | 8 | 9 |
插入排序,在第一圈,把左边第二个位置的值取出来,与左边第一个位置的值比较,如果左边第一个第二个大的话,交换位置。在第二圈,把左边第三个位置的值取出来,依次与左边的值比较,一个位置一个位置地移动到合适的位置。
3.1、插入算法
算法上,需要两层循环来完成,过程如下:
- 外层循环是1,内层循环比较1次,移动1次。将索引1的值取出来,与左边的值做比较。将索引0的值向右移,将索引1的值放在索引0的位置。
- 外层循环是2,内层循环比较2次,移动2次。将索引2的值取出来,与左边的值依次做比较。将索引0到索引1的值向右移,将索引2的值放在索引0的位置。
- 外层循环是3,内层循环比较3次,移动3次。将索引3的值取出来,与左边的值依次做比较。将索引0到索引2的值向右移,将索引3的值放在索引0的位置。
- 外层循环是4,内层循环比较4次,移动4次。将索引4的值取出来,与左边的值依次做比较。将索引0到索引3的值向右移,将索引4的值放在索引0的位置。
3.2、选择排序算法性能
1 | static void Insert(int[] arr) |
4、性能测试
4.1、随机数组测试
5w随机数组测试耗时:
1 | 冒泡 15.76s |
10w随机数组测试耗时:
1 | 冒泡 59.43s |
随机数组测试排名:
- 插入
- 选择
- 冒泡
4.2、升序数组测试
5w升序数组测试耗时:
1 | 冒泡 7.86s |
10w升序数组测试耗时:
1 | 冒泡 29.28s |
升序数组测试排名:
- 插入
- 冒泡,选择
4.3、降序数组测试
5w降序数组测试耗时:
1 | 冒泡 13.61s |
10w降序数组测试耗时:
1 | 冒泡 53.44s |
随机数组测试排名:
- 插入
- 选择
- 冒泡
可以看出,插入排序算法性能最好。但是,这三个简单排序算法,没有一个适合处理庞大数据集的,效率都太低。