现有待排序序列{25,84,21,47,15,27,68,35,20},请写出利用希尔排序进行排序的过程。
时间: 2024-05-27 17:08:12 浏览: 226
希尔排序是一种改进的插入排序,相比于插入排序具有更高的效率。它的基本思想是将待排记录按下标的一定增量分组,对每组使用直接插入排序算法进行排序,随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个序列恰被分成一组,算法便终止。
以{25,84,21,47,15,27,68,35,20}为例,假设我们采用增量序列为{4,2,1},则初始时,整个序列被分成了4组,每组分别为{25,15,68},{84,27,35},{21,68,20},{47}。然后对每组进行插入排序,得到:
{15,25,68},{27,35,84},{20,21,68},{47}
此时,增量变为2,将序列分成了两组,每组分别为{15,27,20,47}和{25,35,84,21,68}。再对每组进行插入排序,得到:
{15,20,27,47},{21,25,35,68,84}
最后,增量变为1,整个序列只有一组,对其进行插入排序即可,最终得到的有序序列为{15,20,21,25,27,35,47,68,84}。
阅读全文