作业 口对下列一组关键字 (46，58,15,45,90,18,10, 62, 46’,58°,15’,45’,90’,18’,10',62") (1)写出所有的逆序对 (2)写出直接插入排序过程 (3)写出希尔排序过程(自选增量序列并说明选择的原因)口（4）写出快速排序过程（自选主元并说明选择的原因）o（5）写出归并排序过程

(1) 逆序对为：(46, 15), (46, 18), (46, 10), (46, 45), (46, 46'), (58, 15), (58, 18), (58, 10), (58, 45), (58, 46'), (58, 15'), (58, 18'), (58, 10'), (58, 45'), (58, 62'), (15, 10), (45, 18), (45, 10), (45, 15'), (45, 18'), (45, 10'), (46', 15'), (46', 18'), (46', 10')

(2) 直接插入排序过程：

初始序列：46 58 15 45 90 18 10 62 46' 58' 15' 45' 90' 18' 10' 62'

第1趟排序：15 46 58 45 90 18 10 62 46' 58' 15' 45' 90' 18' 10' 62'
第2趟排序：15 46 45 58 90 18 10 62 46' 58' 15' 45' 90' 18' 10' 62'
第3趟排序：15 18 45 46 58 90 10 62 46' 58' 15' 45' 90' 18' 10' 62'
第4趟排序：10 15 18 45 46 58 90 62 46' 58' 15' 45' 90' 18' 10' 62'
第5趟排序：10 15 18 45 46 58 62 90 46' 58' 15' 45' 90' 18' 10' 62'
第6趟排序：10 15 18 45 46 58 62 90 46' 58' 10' 45' 90' 15' 18' 62'
第7趟排序：10 15 18 45 46 58 62 90 10' 46' 58' 45' 90' 15' 18' 62'
第8趟排序：10 15 18 45 46 58 62 90 10' 46' 58' 45' 90' 15' 18' 62'

排序完成：10 15 18 45 46 58 62 90 10' 15' 18' 45' 46' 58' 62' 90'

(3) 希尔排序过程：

增量序列为：5 3 1

初始序列：46 58 15 45 90 18 10 62 46' 58' 15' 45' 90' 18' 10' 62'

第1趟排序（增量为5）：18 10 15 45 46 58 10' 15' 18' 45' 46' 58' 90 62 90' 62'
第2趟排序（增量为3）：10 10' 15 15' 18 18' 45 45' 46 46' 58 58' 62 62' 90 90'
第3趟排序（增量为1）：10 10' 15 15' 18 18' 45 45' 46 46' 58 58' 62 62' 90 90'

排序完成：10 10' 15 15' 18 18' 45 45' 46 46' 58 58' 62 62' 90 90'

之所以选择增量序列为5 3 1，是因为这个序列是Donald Shell提出的经典增量序列，经过实验表明具有较好的排序性能。

(4) 快速排序过程：

以中间位置为主元：

初始序列：46 58 15 45 90 18 10 62 46' 58' 15' 45' 90' 18' 10' 62'

第1趟排序：18 10 15 45 46 58 62 90 18' 10' 15' 45' 46' 58' 62' 90'
第2趟排序：10 15 18 45 46 58 62 90 10' 15' 18' 45' 46' 58' 62' 90'
第3趟排序：10 15 18 45 46 58 62 90 10' 15' 18' 45' 46' 58' 62' 90'

排序完成：10 15 18 45 46 58 62 90 10' 15' 18' 45' 46' 58' 62' 90'

以第一个元素为主元：

初始序列：46 58 15 45 90 18 10 62 46' 58' 15' 45' 90' 18' 10' 62'

第1趟排序：10 15 18 45 46 58 90 62 46' 58' 15' 45' 90' 18' 10' 62'
第2趟排序：10 15 18 45 46 58 90 62 10' 46' 15' 45' 58' 90' 18' 62'
第3趟排序：10 15 18 45 46 58 90 62 10' 46' 15' 45' 58' 90' 18' 62'

排序完成：10 15 18 45 46 58 90 62 10' 15' 18' 45' 46' 58' 62' 90'

选择第一个元素作为主元是因为实现简单，而选择中间位置作为主元是为了避免极端情况（如已经有序的序列）下的性能问题。

(5) 归并排序过程：

初始序列：46 58 15 45 90 18 10 62 46' 58' 15' 45' 90' 18' 10' 62'

第1趟归并：15 45 46 58 10' 18' 46' 58' 15' 45' 62' 90' 10 18 62 90
第2趟归并：10 15 18 45 46 58 62 90 10' 15' 18' 45' 46' 58' 62' 90'

排序完成：10 15 18 45 46 58 62 90 10' 15' 18' 45' 46' 58' 62' 90'