排序性能实验

由于对数据结构和算法有些生疏了, 所以最近重新拿出书本温习了一下. 

以前最薄弱的就是排序, 所以这次重点看了看, 并且实现了一下书本中提到的几种基本排序:

插入排序, 冒泡排序, 选择排序, 希尔排序,快速排序, 堆排序, 归并排序

直观的来说由于前四种排序属于O(N2)级别的, 所以他们应当最慢, 而希尔排序大约为O(N1.3-N1.7), 所以应当快一些, 而后三种属于O(NlgN)级别, 所以应当是最快的.

书中提到了几种算法变种, 同时有的算法我也有些不同思路, 所以就把其中一些算法用了几种逻辑来实现:

insert_sort_int: 标准插入排序
insert_sort_int2: 二分式查找, 而后插入
insert_sort_int3: 双路插入排序
insert_sort_int4: 链式插入排序

shell_sort_int: 希尔排序

bubble_sort_int: 冒泡排序, 先确定最后一个数
bubble_sort_int2: 冒泡排序, 先确定第一个

select_sort_int: 选择排序

quick_sort_int: 快速排序, 使用书本中提到方式来partition, 选取第一个, 最后一个, 中间一个, 三个数的中间值作为比较基点.
quick_sort_int2: 快速排序, 使用自己方式来partition, 选取第一个, 最后一个, 中间一个, 三个数的中间值作为比较基点, 
quick_sort_int3: 快速排序, 使用书本中提到方式来partition, 选取第一个值作为比较基点.
quick_sort_int4: 快速排序, 使用自己方式来partition, 选取第一个值作为比较基点.

heap_sort_int: 堆排序

merge_sort_int: 归并排序, 递归调用
merge_sort_int2: 归并排序, 无递归调用, 只有迭代.

所有排序都使用一个预先随机产生好的整数数组, 并且利用该数组重复执行若干次排序. 由于速度差异太大, 所以分为4个不同的过程:

sort_perf_slow(): 数组有4000个元素, 重复执行500次. 只运行插入排序, 冒泡排序, 选择排序和希尔排序. 其他排序太快, 基本只需要1s不到的时间.
sort_perf(): 数组有10000个元素, 重复执行500次. 只运行插入排序和希尔排序.
sort_perf_fast(): 数组有40000个元素, 重复执行500次. 运行希尔排序, 快速排序, 堆排序和归并排序.
sort_perf_superfast(): 数组有160000个元素, 重复执行500次. 只运行O(NlgN)的排序, 即快速排序, 堆排序和归并排序.

得到结果如下:

sort_perf_slow():
Time for insert_sort_int(asc): 10
Time for insert_sort_int(desc): 8
Time for insert_sort_int2(asc): 8
Time for insert_sort_int2(desc): 7
Time for insert_sort_int3(asc): 6
Time for insert_sort_int3(desc): 5
Time for shell_sort_int(asc): 1
Time for shell_sort_int(desc): 0
Time for bubble_sort_int(asc): 37
Time for bubble_sort_int(desc): 37
Time for bubble_sort_int2(asc): 35
Time for bubble_sort_int2(desc): 34
Time for select_sort_int(asc): 14
Time for select_sort_int(desc): 14

sort_perf():
Time for insert_sort_int(asc): 56
Time for insert_sort_int(desc): 56
Time for insert_sort_int3(asc): 55
Time for insert_sort_int3(desc): 56
Time for shell_sort_int(asc): 2
Time for shell_sort_int(desc): 3

sort_perf_fast():
Time for shell_sort_int(asc): 17
Time for shell_sort_int(desc): 18
Time for quick_sort_int(asc): 3
Time for quick_sort_int(desc): 4
Time for quick_sort_int2(asc): 4
Time for quick_sort_int2(desc): 5
Time for heap_sort_int(asc): 4
Time for heap_sort_int(desc): 4
Time for merge_sort_int(asc): 5
Time for merge_sort_int(desc): 4
Time for merge_sort_int2(asc): 4
Time for merge_sort_int2(desc): 3

sort_perf_superfast():
Time for quick_sort_int(asc): 15
Time for quick_sort_int(desc): 15
Time for quick_sort_int2(asc): 20
Time for quick_sort_int2(desc): 20
Time for quick_sort_int3(asc): 15
Time for quick_sort_int3(desc): 15
Time for quick_sort_int4(asc): 20
Time for quick_sort_int4(desc): 20
Time for heap_sort_int(asc): 21
Time for heap_sort_int(desc): 21
Time for merge_sort_int(asc): 19
Time for merge_sort_int(desc): 20
Time for merge_sort_int2(asc): 15
Time for merge_sort_int2(desc): 15

基本上, 得出的结果是符合时间复杂度公式的. 同时可以看出, 在merge sort时, 迭代比递归快. 在快速排序是, 书本介绍的partition方式似乎有更好的性能. 希尔排序尽快远快于插入排序和冒泡,选择排序, 但被后面的3种秒杀. 最后, 如果为简单要选择O(N2)的排序算法, 那就选择插入排序吧.