`

数据结构-算法: 插入排序(希尔排序法)

阅读更多

数据结构-算法: 插入排序(希尔排序法)

希尔排序法基本思想
希尔排序(Shell Sort)又称为“缩小增量排序”。是1959年由D.L.Shell提出来的。该方法的基本思想是:先将整个待排元素序列分割成若干个子序列(由相隔某 个“增量”的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插 入排序。因为直接插入排序在元素基本有序的情况下(接近最好情况),效率是很高的,因此希尔排序在时间效率上比前两种方法有较大提高。
具体做法:首先确定一组增量d0,d1,d2,d3,...,dt-1()其中n>d0>d1>...>dt-1=1),对于 i=0,1,2,...,t-1,依次进行下面的各趟处理:根据当前增量di将n个元素分成di个组,每组中元素的下标相隔为di;再对各组中元素进行直 接插入排序.
2、下面给出希尔排序算法的执行过程。

(1)采用希尔排序法排序的各趟的结果如下:
初始:503,17,512,908,170,897,275,653,426,154,509,612,677,765,703,94
第1趟{d1=8}:426,17,509,612,170,765,275,94,503,154,512,908,677,897,703,653
第2趟(d2=4):170,17,275,94,426,154,509,612,503,765,512,653,677,897,703,908
第3趟(d3=2):170,17,275,94,426,154,503,612,509,653,512,765,677,897,703,908
第4趟(d1=1):17,94,154,170,275,426,503,509,512,612,653,677,703,765,897,908
(2)例如,n=8,数组a的八个元素分别为:17,3,30,25,14,17,20,9。

给定实例的shell排序的排序过程

 假设待排序文件有10个记录,其关键字分别是:
49,38,65,97,76,13,27,49,55,04。
 增量序列的取值依次为:
5,3,1
 排序过程如【动画模拟演示】。

Shell排序的算法实现

1. 不设监视哨的算法描述

using System;
using System.Collections.Generic;
using System.Text;

namespace ExShellSorter
{
public class ShellSorter
{
public void Sort(int[] arr)
{
int inc;
for (inc = 1; inc <= arr.Length / 9; inc = 3 * inc + 1) ;
for (; inc > 0; inc /= 3)
{
for (int i = inc + 1; i <= arr.Length; i += inc)
{
int t = arr[i - 1];
int j = i;
while ((j > inc) && (arr[j - inc - 1] > t))
{
arr[j - 1] = arr[j - inc - 1];//交换数据
j -= inc;
}
arr[j - 1] = t;
}
}
}

static void Main(string[] args)
{
int[] array = new int[] { 1, 5, 3, 6, 10, 55, 9, 2, 87, 12, 34, 75, 33, 47 };
ShellSorter s = new ShellSorter();
s.Sort(array);
foreach (int m in array)
Console.WriteLine("{0}", m);

}
}
}

注意:
  当增量d=1时,ShellPass和InsertSort基本一致,只是由于没有哨兵而在内循环中增加了一个循环判定条件"j>0",以防下标越界。

2.设监视哨的shell排序算法
 具体算法【参考书目[12] 】

算法分析

1.增量序列的选择

 Shell排序的执行时间依赖于增量序列。
 好的增量序列的共同特征:
  ① 最后一个增量必须为1;
  ② 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。
 有人通过大量的实验,给出了目前较好的结果:当n较大时,比较和移动的次数约在nl.25到1.6n1.25之间。

2.Shell排序的时间性能优于直接插入排序
 希尔排序的时间性能优于直接插入排序的原因:
  ①当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。
  ②当n值较小时,n和n2的差别也较小,即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n2)差别不大。
  ③在希尔排序开始时增量较大,分组较多,每组的记录数目少,故各组内直接插入较快,后来增量di逐渐缩小,分组数逐渐减少,而各组的记录数目逐渐增多,但由于已经按di-1作为距离排过序,使文件较接近于有序状态,所以新的一趟排序过程也较快。
 因此,希尔排序在效率上较直接插人排序有较大的改进。

3.稳定性
 希尔排序是不稳定的。参见上述实例,该例中两个相同关键字49在排序前后的相对次序发生了变化。

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics